Mô phỏng thuật toán Điểm trong đa giác

Point in Polygon · Nhóm: Hình học

Kiểm tra một điểm nằm trong hay ngoài đa giác bằng cách bắn tia và đếm số lần cắt cạnh (ray casting · crossing number).

Ý tưởng

Từ điểm P bắn một tia ngang sang phải; với mỗi cạnh đa giác, xét cạnh đó có vắt qua độ cao y của P không (một đầu trên tia, một đầu dưới).

Nếu cạnh vắt qua tia và giao điểm nằm bên phải P thì tính là một lần cắt; cuối cùng số lần cắt lẻ nghĩa là P bên trong, chẵn thì bên ngoài.

Vì sao đúng

Mỗi lần tia xuyên qua biên là một lần đổi phía trong · ngoài; xuất phát từ ngoài vô cực, số lần cắt lẻ đưa tia kết thúc ở bên trong.

Mã Python

def point_in_poly(poly, px, py):
    crossings = 0                          # ray-crossing counter
    n = len(poly)
    for i in range(n):                     # each edge (a, b)
        ax, ay = poly[i]
        bx, by = poly[(i + 1) % n]
        if (ay > py) != (by > py):         # edge straddles the ray
            xcut = ax + (bx - ax) * (py - ay) / (by - ay)
            if xcut > px:                  # crossing is to the right
                crossings += 1
    return crossings % 2 == 1              # odd -> inside

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.