पायथन में जांचने का प्रोग्राम कि पॉइंट्स कन्वेक्स हल बना रहे हैं या नहीं

मान लीजिए हमारे पास क्लॉकवाइज क्रम में पॉलीगॉन के बाहरी पॉइंट्स हैं। हमें जांचना है कि ये पॉइंट्स कन्वेक्स हल बना रहे हैं या नहीं।

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

तो, यदि इनपुट points = [(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)] है, तो आउटपुट True होगा।

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

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

उदाहरण

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

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