Polar Angle Sort · Nhóm: Hình học
Sắp các điểm theo góc cực quanh một mốc, bước tiền xử lý cho Graham scan để quét bao lồi đúng một vòng.
Chọn điểm mốc O (điểm thấp nhất) làm gốc; với mỗi điểm p tính góc cực của tia O→p bằng atan2(p.y−Oy, p.x−Ox).
Sắp các điểm theo góc cực tăng dần từ 0 tới pi; kết quả là thứ tự quét ngược chiều kim đồng hồ quanh mốc.
Vì O là điểm thấp nhất, mọi tia hướng lên nên góc nằm trong [0, pi]; sắp góc tăng dần cho một trật tự quét vòng thống nhất để bước sau giữ tính lồi.
def polar_sort(points, ox, oy):
def angle(p): # ray O -> p
return atan2(p.y - oy, p.x - ox)
order = sorted(points, key=angle) # ascending polar angle
for p in order: # placed in angular order
emit(p) # ready for Graham scan
return order
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.