QuickHull 介紹:
1. 找出 x 座標最右邊及最左邊的點,y 座標最上及最下的點,
將此四點連成一四邊形,則在此四邊形內的點皆可刪掉
(不可能是 Convex Hull),如下圖 1。
2. 分成四個部分來做,假設先考慮右上部分,找出距離線段 AB 最遠的點 C,
則在三角形 ABC 的點皆可刪掉,如圖 2。
3. 依此方法直到所有線段外再無任何點,即完成右上部分的 Convex Hull,如圖 3。
4. 重複使用找出右上部分 Convex Hull 的方法分別解決其他三個部分,
最後可找出所有的 Convex Hull,如圖 4。
圖 1 |
|
圖 2 |
|
圖 3 |
|
圖 4 |
|