Mô phỏng thuật toán Bao lồi (Andrew)

Convex Hull · Nhóm: Hình học

Bao lồi (Andrew) (Convex Hull), nhóm Hình học.

Mã Python

def convex_hull(pts):
    pts.sort()
    def half(seq):
        h = []
        for p in seq:
            while len(h) >= 2 and cross(h[-2], h[-1], p) <= 0:
                h.pop()
            h.append(p)
        return h
    lower, upper = half(pts), half(pts[::-1])
    return lower[:-1] + upper[:-1]

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