Mô phỏng thuật toán Chiều quay của ba điểm

Point Orientation (Cross Product) · Nhóm: Hình học

Xác định ba điểm P, Q, R quay theo chiều nào (ngược kim, cùng kim, hay thẳng hàng) chỉ bằng dấu của tích có hướng.

Ý tưởng

Lập hai vector PQ và PR rồi tính tích có hướng cross = (Qx−Px)(Ry−Py) − (Qy−Py)(Rx−Px).

Đọc dấu: cross > 0 là rẽ trái (ngược chiều kim · CCW), cross < 0 là rẽ phải (cùng chiều kim · CW), cross = 0 là ba điểm thẳng hàng.

Vì sao đúng

Tích có hướng trong mặt phẳng bằng diện tích có dấu của hình bình hành PQ, PR; dấu diện tích cho biết R nằm bên trái hay bên phải hướng đi P→Q.

Mã Python

def orientation(px, py, qx, qy, rx, ry):
    # cross product of vectors PQ and PR
    cross = (qx - px) * (ry - py) - (qy - py) * (rx - px)
    if cross > 0:
        return "CCW"          # left turn (counter-clockwise)
    elif cross < 0:
        return "CW"           # right turn (clockwise)
    else:
        return "collinear"    # three points on one line

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