दिए गए बहुभुज के अंदर या सीमा में दिए गए बिंदु की जाँच करने के लिए कार्यक्रम या नहीं अजगर में

मान लीजिए कि हमारे पास कार्तीय बिंदुओं की एक सूची है [(x1, y1), (x2, y2), ..., (xn, yn)], जो एक बहुभुज का प्रतिनिधित्व कर रहा है, और दो मान x और y भी हैं, हमें यह करना होगा जांचें कि क्या (x, y) इस बहुभुज के अंदर या सीमा पर स्थित है।

इसलिए, यदि इनपुट अंक की तरह है =[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt =(3, 1)

तो आउटपुट सही होगा

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

• उत्तर:=असत्य
• i के लिए 0 से लेकर बहुभुज के आकार के लिए - 1, do
  • (x0, y0) :=बहुभुज[i]
  • (x1, y1) :=बहुभुज[(i + 1) बहुभुज का आधुनिक आकार]
  • यदि pt[1] न्यूनतम y0, y1 और अधिकतम y0, y1 की सीमा में नहीं है, तो
    • अगले पुनरावृत्ति के लिए जाएं
  • यदि pt[0] <न्यूनतम x0 और x1, तो
    • अगले पुनरावृत्ति के लिए जाएं
  • cur_x :=x0 यदि x0, x1 के समान है अन्यथा x0 + (pt[1] - y0) *(x1 - x0) /(y1 - y0)
  • उत्तर:=उत्तर XOR (1 जब pt[0]> cur_x सत्य है, अन्यथा 0)
• वापसी उत्तर

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

उदाहरण

class Solution:
   def solve(self, polygon, pt):
      ans = False
      for i in range(len(polygon)):
         x0, y0 = polygon[i]
         x1, y1 = polygon[(i + 1) % len(polygon)]
         if not min(y0, y1) < pt[1] <= max(y0, y1):
            continue
         if pt[0] < min(x0, x1):
            continue
         cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
         ans ^= pt[0] > cur_x
      return ans

ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))

इनपुट

[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)

आउटपुट

True