โปรแกรมตรวจสอบว่าจุดต่างๆ สร้างเป็น Convex Hull หรือไม่ใน Python

การตรวจสอบ Convex Hull (รูปหลายเหลี่ยม凸)

กำหนดจุดมุมเรียงตามเข็มนาฬิกา ตรวจสอบว่ามุมภายในทุกมุม ≤ 180° (Convex)

อัลกอริทึม

1. วนตรวจสอบมุมของทุก 3 จุดติดต่อกัน
2. ถ้ามีมุม > 180° → ไม่ใช่ Convex → คืน False
3. ถ้าทุกมุม ≤ 180° → เป็น Convex → คืน True

ตัวอย่างโค้ด

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))

ผลลัพธ์

True

ความแตกต่างจาก Concave

Convex: ทุกมุม ≤ 180° | Concave: มีมุม > 180° อย่างน้อย 1 มุม