Divide and Conquer 介紹:
1. 如果所有的點集合 |S| <=3,則直接使用暴力法解決 Convex Hull in O(1) time。
2. 否則找出一條垂直 x 軸的線,將所有點集合分成兩相同 size 集合 SL and SR。
3. Recursively compute HL = Hull(L) and HR = Hull(R)。
4. Merge the two hulls into a common convex hull, H, by computing the upper and lower
tangents for HA and HB and discarding all the points lying between these two tangents。
1. |
|
2. |
|
3. |
|
4. |
|