Chương trình kiểm tra điểm nằm trong hoặc trên biên đa giác trong Python

Cho danh sách điểm Cartesian [(x1,y1), (x2,y2), ..., (xn,yn)] đại diện đa giác, và điểm (x,y). Kiểm tra điểm có nằm trong đa giác hoặc trên biên không.

Ví dụ: points=[(0,0),(1,3),(4,4),(6,2),(4,0)], pt=(3,1) → True.

Thuật toán Ray Casting (Even-Odd Rule):

• Bắn tia ngang từ điểm kiểm tra về bên phải
• Đếm số giao điểm với các cạnh đa giác
• Số lẻ → trong, số chẵn → ngoài
• Xử lý riêng trường hợp điểm trên cạnh (boundary)

Triển khai tối ưu:

• Duyệt từng cạnh (x0,y0) → (x1,y1)
• Bỏ qua nếu pt.y không trong (min(y0,y1), max(y0,y1)] (nửa mở để tránh double-count đỉnh)
• Bỏ qua nếu pt.x < min(x0,x1) (giao điểm bên trái)
• Tính cur_x = tọa độ x giao điểm cạnh với đường ngang y=pt.y
• ans ^= (pt.x > cur_x) (XOR flip khi giao điểm bên phải)

Triển khai

class Solution:
    def solve(self, polygon, pt):
        ans = False
        for i in range(len(polygon)):
            x0, y0 = polygon[i]
            x1, y1 = polygon[(i + 1) % len(polygon)]
            
            if not (min(y0, y1) < pt[1] <= max(y0, y1)):
                continue
            if pt[0] < min(x0, x1):
                continue
            
            cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
            ans ^= pt[0] > cur_x
        return ans

ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))

Đầu vào

[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)

Đầu ra

True

Lưu ý: Thuật toán giả định đa giác đơn giản (không tự giao). Điểm trên cạnh: điều kiện min(y0,y1) < pt[1] <= max(y0,y1) và pt.x == cur_x sẽ trả về False (coi là ngoài). Cần kiểm tra riêng point_on_segment nếu muốn coi điểm trên biên là "trong".