পয়েন্ট চেক করার প্রোগ্রামটি পাইথনে উত্তল হুল তৈরি করছে বা না

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

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

সুতরাং, যদি ইনপুট পয়েন্টের মত হয় =[(3,4), (4,7), (7,8),(11,6),(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 False
   return True

points = [(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)]
print(solve(points))

ইনপুট

[(3,4), (4,7),(7,8),(11,6),(12,3),(10,1),(5,2)]

আউটপুট

True