Graham Scan Convex Hull · Nhóm: Hình học
Tìm bao lồi của tập điểm (đa giác lồi nhỏ nhất chứa mọi điểm) bằng cách chọn chốt, sắp góc rồi quét ngăn xếp.
Chọn điểm thấp nhất làm chốt (chắc chắn thuộc bao), sắp các điểm còn lại theo góc cực quanh chốt tăng dần.
Duyệt lần lượt và duy trì một ngăn xếp đỉnh lồi: chừng nào ba đỉnh cuối tạo góc rẽ không sang trái (tích chéo ≤ 0) thì bật đỉnh giữa ra, sau đó đẩy điểm mới vào.
Đi vòng theo góc tăng dần thì mọi khúc phải rẽ trái mới lồi; đỉnh nào gây rẽ phải là nằm trong phần lõm nên bị bật ra, chỉ còn lại đường bao lồi.
def graham_scan(pts):
piv = min(pts, key=lambda p: (p.y, p.x)) # lowest, then leftmost
rest = sorted(p for p in pts if p != piv,
key=lambda p: polar_angle(piv, p))
hull = [piv, rest[0]] # stack of hull vertices
for p in rest[1:]: # scan remaining points
while len(hull) >= 2 and \
cross(hull[-2], hull[-1], p) <= 0: # non-left turn
hull.pop() # discard concave vertex
hull.append(p) # push current candidate
return hull # convex hull, ccw
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.