পয়েন্ট চেক করার প্রোগ্রাম অবতল বহুভুজ গঠন করছে নাকি পাইথনে নয়

ধরুন আমাদের কাছে একটি বহুভুজের বাইরের বিন্দু রয়েছে ঘড়ির কাঁটার দিকে। আমাদের এই পয়েন্টগুলি একটি উত্তল বহুভুজ গঠন করছে কি না তা পরীক্ষা করতে হবে। একটি বহুভুজ অবতল বলা হয় যদি এর অভ্যন্তরীণ কোণগুলির একটি 180° এর বেশি হয়।

এই চিত্র থেকে এটা স্পষ্ট যে প্রতিটি তিনটি পরপর বিন্দুর জন্য অভ্যন্তরীণ কোণ CDE ছাড়া 180° এর বেশি নয়।

সুতরাং, ইনপুট যদি পয়েন্টের মত হয় =[(3,4), (4,7), (7,8),(8,4),(12,3),(10,1),(5,2 )], তাহলে আউটপুট হবে True।

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

• n :=পয়েন্টের আকার
• আমি রেঞ্জ 0 থেকে পয়েন্টের আকারের জন্য, করুন
  • p1 :=পয়েন্ট[i-2] যখন i> 1, অন্যথায় পয়েন্ট[n-2]
  • p2 :=পয়েন্ট[i-2] যখন i> 0, অন্যথায় পয়েন্ট[n-1]
  • p3 :=পয়েন্ট[i]
  • যদি বিন্দুর মধ্যে কোণ (p1, p2, p3)> 180, তাহলে
    • সত্য ফেরান
• মিথ্যে ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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