পাইথনে একটি পয়েন্ট পলিগনের ভিতরে বা বাউন্ডারিতে আছে কিনা চেক করার প্রোগ্রাম

ধরি আমাদের কারtezিয়ান পয়েন্টের একটি লিস্ট [(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 = ০ থেকে পলিগন সাইজ - ১ পর্যন্ত, করুন
  • (x0, y0) := polygon[i]
  • (x1, y1) := polygon[(i+1) mod size]
  • যদি pt[1] min(y0, y1) এবং max(y0, y1) রেঞ্জে না থাকে, তবে
    • নেক্সট ইটেরেশন
  • যদি pt[0] < min(x0, x1), তবে
    • নেক্সট ইটেরেশন
  • cur_x := x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
  • ans := ans XOR (1 if pt[0] > cur_x else 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