প্রদত্ত বহুভুজের অভ্যন্তরে বা সীমানার মধ্যে প্রদত্ত পয়েন্ট চেক করার প্রোগ্রাম বা পাইথনে নয়

ধরুন আমাদের কার্টেসিয়ান বিন্দুর একটি তালিকা আছে [(x1, y1), (x2, y2), ..., (xn, yn)], যা একটি বহুভুজকে প্রতিনিধিত্ব করছে, এবং এছাড়াও দুটি মান x এবং y আছে, আমাদের করতে হবে (x, y) এই বহুভুজের ভিতরে বা সীমানায় আছে কিনা তা পরীক্ষা করুন।

সুতরাং, যদি ইনপুট পয়েন্টের মত হয় =[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt =(3, 1)

তাহলে আউটপুট হবে True

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=মিথ্যা
• আমি 0 থেকে বহুভুজের আকার - 1 এর মধ্যে, কর
  • (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