Mô phỏng thuật toán Điểm nằm trên đoạn thẳng

Point on Segment · Nhóm: Hình học

Kiểm tra một điểm P có nằm trên đoạn thẳng AB không, bằng hai điều kiện: thẳng hàng và trong hộp bao.

Ý tưởng

Tính tích có hướng cross(A→B, A→P); nếu khác 0 thì P không thẳng hàng với AB nên chắc chắn không nằm trên đoạn.

Nếu cross = 0 (thẳng hàng), kiểm tra thêm P có kẹp trong hộp bao của A và B không (tọa độ x và y đều nằm giữa) để loại các điểm nằm trên phần kéo dài.

Vì sao đúng

Thẳng hàng đưa P về đúng đường thẳng AB, nhưng đường thẳng dài vô hạn; hộp bao giới hạn P vào đúng khúc giữa hai đầu mút A và B.

Mã Python

def on_segment(ax, ay, bx, by, px, py):
    cross = (bx - ax) * (py - ay) - (by - ay) * (px - ax)
    if cross != 0:                         # not collinear
        return False
    if not (min(ax, bx) <= px <= max(ax, bx)):   # outside x-range
        return False
    if not (min(ay, by) <= py <= max(ay, by)):   # outside y-range
        return False
    return True                            # collinear AND inside box

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