मान लीजिए हमारे पास कार्टेशियन पॉइंट्स की एक सूची [(x1, y1), (x2, y2), ..., (xn, yn)] है, जो एक पॉलीगोन को दर्शाती है, और हमारे पास दो मान x और y भी हैं, हमें जांचना है कि (x, y) इस पॉलीगोन के अंदर है या बाउंड्री पर।
इसलिए, यदि इनपुट इस तरह है points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt = (3, 1)

तो आउटपुट True होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ans := False
- i के लिए 0 से पॉलीगोन के आकार - 1 तक रेंज में, करें
- (x0, y0) := पॉलीगोन[i]
- (x1, y1) := पॉलीगोन[(i + 1) mod पॉलीगोन का आकार]
- यदि pt[1] y0, y1 के न्यूनतम और अधिकतम की रेंज में नहीं है, तो
- अगले इटरेशन के लिए जाएं
- यदि pt[0] x0 और x1 के न्यूनतम से कम है, तो
- अगले इटरेशन के लिए जाएं
- cur_x := x0 यदि x0, x1 के समान है अन्यथा x0 + (pt[1] - y0) *(x1 - x0) /(y1 - y0)
- ans := ans XOR (1 जब pt[0] > cur_x सत्य है, अन्यथा 0)
- ans लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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