โปรแกรมตรวจสอบว่าจุดต่างๆ สร้างเป็นรูปหลายเหลี่ยมโค้ง (Concave) หรือไม่ใน Python

การตรวจสอบรูปหลายเหลี่ยมโค้ง (Concave Polygon)

กำหนดจุดมุมของรูปหลายเหลี่ยมเรียงตามเข็มนาฬิกา ตรวจสอบว่ามีมุมภายใน > 180° หรือไม่ (Concave)

อัลกอริทึม

1. สำหรับจุด 3 จุดติดต่อกัน (p1, p2, p3) คำนวณมุมที่ p2
2. ใช้ atan2 หามุมระหว่างเวกเตอร์ p2→p1 และ p2→p3
3. ถ้ามุม > 180° → Concave → คืน True
4. วนตรวจสอบทุก 3 จุดติดต่อกัน (วนรอบ)

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

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

ผลลัพธ์

True

คำอธิบาย

จุด C-D-E (8,4), (12,3), (10,1) สร้างมุม > 180° → เป็น Concave polygon