Convex Hull

Convex Hull

中文譯做「凸包」,能包住物品的最小的凸外殼,也就是能將全部東西包進去的最小凸多邊形。凸的定義是圖形內任兩點的連線不會經過圖形外部:http://mathworld.wolfram.com/Convex.html。這裡我們只討論:從二維平面上散佈的點當中找出凸包。

在所有點的外圍繞一圈可得一凸多邊形,即是凸包。

凸包所包住的區域,為各點之間做線性內插後的範圍。

UVa 109 132 218 361 681 811 819 10002 10065 10078 10135 10173 10256 11626

Convex Hull: Jarvis' March

Jarvis' March(Gift Wrapping Algorithm)

從一個凸包上的頂點開始,順著外圍繞一圈,順時針或逆時針都可以。

當要尋找下一個被包覆的點時,則窮舉平面上所有點,找出位於最外圍的一點來包覆即可(可利用外積運算來做判斷)。時間複雜度為O(N*M),M為凸包的頂點數目。

Convex Hull: Graham's Scan

Graham's Scan

由前面段落可知:凸包上的頂點們有順序的沿著外圍繞行一圈。若能照此順序來包,就不必以窮舉所有點的方式來尋找最外圍的點。Graham's Scan即是嘗試將所有點按照順序排好,再來做繞一圈的動作。

順序該如何決定呢?只要能確保凸包各頂點的前後順序是正確的,那麼便不會包錯。一個簡單的想法是依角度排序──只要將中心點設定在凸包內部或設定在凸包上面,便可以確保凸包各頂點的前後順序必定正確(讀者可自行証明此說)。

除了凸包各頂點的前後順序要正確,另外還要限制所有點依照前後順序連線起來後,不會繞成超過一個的圈圈,也不會有任何邊重疊。更精準的說法是:會形成簡單多邊形(simple polygon),不會有邊相交。如此一來,便不必理會那些不在凸包上面的點的前後順序,因為那些點會在找最外圍的點的時候被淘汰掉(讀者可自行証明此說)。

一般來說,選擇凸包上面的端點當作排序角度時的中心點是比較好的,因為最大的夾角必會小於180度,而可以使用外積運算來排序。(外積在大於180度時會得負值、等於180度時會等於零,導致排序錯誤。)

如果凸包各頂點的前後順序是錯誤的,或者所有點依照前後順序連線後產生了很多圈圈,就會發生慘劇。有時甚至會找出凹的形狀。

其他細節在演算法書籍上面皆可找到,故不細講。時間複雜度為O(NlogN),主要取決於排序的時間;若用Counting Sort之類的排序方法便可達到O(N);若已知這些點構成的簡單多邊形之後,便不需排序,就只需O(N)。

若要連凸包上面共線的點都找出來,便要小心處理剛開始包、快要包好時產生共線的情形,這些點的先後順序決不能亂。

有一個解決方法是分做左右兩邊包,當排序時遇到角度相同的情況時,令距離離中心點較短的順序較高。總之相當麻煩,就不細講了。下面這段程式碼寫出一些特別要注意的地方:

Convex Hull: Andrew's Monotone Chain

Andrew's Monotone Chain

排順序時改為依座標大小排序。這個方法非常優美,而且能處理共線的情形:http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull。我也找到了有趣的Applet:http://wind.lcs.mit.edu/~aklmiu/6.838/convexhull/index.html

時間複雜度為下述兩項總和:一、一次排序,通常為O(NlogN);二、掃描2N個點,為O(N)。

Convex Hull: Quick Hull Algorithm

演算法

這是一個運用Divide and Conquer的演算法。

一開始將所有點以X座標位置排序。
Divide:將所有點分成左半部和右半部。
Conquer:左半部和右半部分別求凸包。
Merge:將兩個凸包合併成一個凸包。
在兩凸包頂端最凸處加一條邊,
然後在兩凸包底部最凸處加一條邊,
就變成一個凸包。

令左半部凸包最左端的點為p點,令右半部凸包最右端的點為q點。
要找上方的邊,
讓p點為基準,然後移動q點在凸包上往逆時針方向走,
讓直線pq持續往逆時針方向轉,轉到底為止。
接著讓q點為基準,然後移動q點在凸包上往逆時針方向走,
讓直線pq持續往逆時針方向轉,轉到底為止。
此時的邊pq就是上方的邊。
要找下方的邊,也可以如法炮製。

另外一種比較麻煩一點的找法是,
令左半部凸包最高的點為p點,令右半部凸包最低的點為q點。
讓p點為基準,然後移動q點在凸包上往逆時針、也往順時針方向走,
總之就是讓直線pq持續往逆時針方向轉。
接著讓q點為基準做類似的事情。
要找下方的邊,也可以如法炮製。

時間複雜度為下述兩項總和:一、一次排序的時間,通常為O(NlogN);二、Divide and Conquer向下遞迴O(logN)深度,合併凸包要O(N)時間,總共需時O(NlogN)。

Convex Hull: Melkman's Algorithm

演算法

求出一簡單多邊形的凸包。

http://cgm.cs.mcgill.ca/~athens/cs601/Melkman.html

時間複雜度為O(N)。是相當優美的演算法。