葛立恆掃描法 | 會動的演算法

符號表示

資料

將各點排序並決定起點
找到最左下角的點。
指向最左下角的點。
以最左下角的點為參考點 ( 基準 ),將其餘的點按「極角」(polar angle)大小排序。
建立凸包
檢查 3 個點的走向是否為逆時針。
將點的編號新增到堆疊中。st.push(head)
逐步決定凸包的邊。

演算法動畫

將各點排序並決定起點
葛立恆掃描法  | 將各點排序並決定起點

建立凸包
葛立恆掃描法  | 建立凸包