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

回上一頁