← 返回首頁

Convex Hull 凸包

或點擊畫布新增點

凸包構建

堆疊:
點數:0
凸包頂點:0

演算法說明

Graham Scan 是一種 O(n log n) 的凸包演算法。

步驟:1. 找到最下方(y 最小)的點作為起點 2. 按極角排序其餘點 3. 使用堆疊逐一加入點,利用叉積判斷方向(左轉/右轉),右轉則彈出堆疊頂端