बिंदुओं की जाँच करने के लिए प्रोग्राम अवतल बहुभुज बना रहे हैं या नहीं पायथन में

मान लीजिए कि हमारे पास बहुभुज के बाहरी बिंदु दक्षिणावर्त क्रम में हैं। हमें यह जांचना है कि ये बिंदु उत्तल बहुभुज बना रहे हैं या नहीं। एक बहुभुज को अवतल कहा जाता है यदि उसका कोई एक आंतरिक कोण 180° से अधिक हो।

इस आरेख से यह स्पष्ट है कि सीडीई को छोड़कर प्रत्येक तीन क्रमागत बिंदुओं के लिए आंतरिक कोण 180° से अधिक नहीं है।

तो, यदि इनपुट अंक की तरह है =[(3,4), (4,7),(7,8),(8,4),(12,3),(10,1),(5,2 )], तो आउटपुट ट्रू होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=बिंदुओं का आकार
• मैं के लिए 0 से लेकर अंकों के आकार तक, करें
  • p1 :=अंक[i-2] जब i> 1, अन्यथा अंक[n-2]
  • p2 :=पॉइंट्स[i-2] जब i> 0, अन्यथा पॉइंट्स[n-1]
  • p3:=अंक[i]
  • यदि बिंदुओं के बीच का कोण (p1, p2, p3)> 180, तो
    • सही लौटें
• झूठी वापसी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

import math
def get_angle(a, b, c):
   angle = math.degrees(math.atan2(c[1]-b[1], c[0]-b[0]) - math.atan2(a[1]-b[1], a[0]-b[0]))
   return angle + 360 if angle < 0 else angle

def solve(points):
   n = len(points)
   for i in range(len(points)):
      p1 = points[i-2]
      p2 = points[i-1]
      p3 = points[i]
      if get_angle(p1, p2, p3) > 180:
         return True
   return False

points = [(3,4), (4,7),(7,8),(8,4),(12,3),(10,1),(5,2)]
print(solve(points))

इनपुट

[(3,4), (4,7),(7,8),(8,4),(12,3),(10,1),(5,2)]

आउटपुट

True