পাইথন প্রোগ্রাম - পয়েন্টগুলোর কনকেভ পলিগন গঠন করে কিনা তা যাচাই করুন

মনে করুন একটি পলিগনের বাহিরের পয়েন্টগুলো ঘড়ির কাঁটার দিকে অর্ডার্ড আছে। এগুলো কনভেক্স পলিগন গঠন করে কিনা তা যাচাই করতে হবে। একটি পলিগন কনকেভ হয় যদি এর যেকোনো একটি আভ্যন্তরিন কোণ ১৮০°-র চেয়ে বড় হয়।

ইনপুট points = [(3,4), (4,7), (7,8), (8,4), (12,3), (10,1), (5,2)] হলে আউটপুট হবে True।

সমাধানের ধাপসমূহ:

• n := points-এর আকার
• i = 0 থেকে points-এর আকার পর্যন্ত:
  • p1 := points[i-2] যদি i > 1, অন্যথায় points[n-2]
  • p2 := points[i-1] যদি i > 0, অন্যথায় points[n-1]
  • p3 := points[i]
  • যদি (p1, p2, p3) পয়েন্টগুলোর কোণ > 180: True ফেরত দিন
• False ফেরত দিন

উদাহরণ

বাস্তবায়ন:

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