Jarvis March (Gift Wripping)介紹:
1. 找出 y 座標最低點和角度最小的點,且此線段為 Convex Hull 線段。
2. 接著以此線段當作水平線主軸逆時針旋轉,依然找尋角度最小的點,
此點為 Convex Hull。
3. 若有許多相同角度的點,則以距離最遠的點當水平線主軸逆時針旋轉。
4. 重複以上步驟即可求出所有的 Convex Hull。
如下圖所示
1. | 2. |
|
|
3. | 4. |
|
|
5. | 6. |
|
|