मान लीजिए हमारे पास क्लॉकवाइज क्रम में पॉलीगॉन के बाहरी पॉइंट्स हैं। हमें जांचना है कि ये पॉइंट्स कन्वेक्स पॉलीगॉन बना रहे हैं या नहीं। एक पॉलीगॉन को कॉनकेव कहा जाता है यदि उसका कोई भी आंतरिक कोण 180° से अधिक है।
इस डायग्राम से स्पष्ट है कि प्रत्येक तीन क्रमागत पॉइंट्स के लिए आंतरिक कोण 180° से अधिक नहीं है सिवाय CDE के।
तो, यदि इनपुट points = [(3,4), (4,7),(7,8),(8,4),(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, तो
- True लौटाएं
- False लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
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
