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

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

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

तो, यदि इनपुट अंक की तरह है =[(3,4), (4,7),(7,8),(11,6),(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 False
   return True

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

इनपुट

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

आउटपुट

True