凸包

出自 MBA智库百科(https://wiki.mbalib.com/)

凸包（Convex hull）

　　在瞭解凸包之前，須先認識何謂“凸多邊形”(Convex Polygon)。從直觀上說，一個凸多邊形就是沒有任何凹陷位的多邊形。我們在低年級數學所學習的三角形、正方形、長方形、平行四邊形、正五邊形、正六邊形等等，都是凸多邊形的例子。但是以下這個“凸”字形卻並非凸多邊形，因為箭頭指著的地方實際是一個凹陷位。

　　可是上述這一定義很不嚴密，究竟何謂“凹陷位”？實在難以說清楚。因此在數學上，凸多邊形有另一個嚴格的定義。假設我們在一個多邊形上(包括多邊形的邊界及邊界圍封的範圍)任意取兩點並以一條線段連結該兩點，如果線段上的每一點均在該多邊形上，那麼我們便說這個多邊形是凸的。根據以上定義，我們便可判斷“凸”字形的確不是凸的。例如，在下圖中，連結A、B兩點的線段有一部分並不在該多邊形上。

　　認識了凸多邊形後，我們便可瞭解何謂凸包。給定平面上的一個(有限)點集(即一組點)，這個點集的凸包就是包含點集中所有點的最小面積的凸多邊形。例如，下圖的點集共包含9個點，圖中的六邊形便是該點集的凸包。其中構成六邊形的6個點稱為“凸包上的點”(Hull Point)，其餘3個點則並非“凸包上的點”。請註意上述定義中“最小面積”這個限制條件，因為除了凸包以外，還有無限多個包含點集中所有點的凸多邊形。例如，只要畫一個面積足夠大的四邊形，便可包圍任意給定的點集。因此假如沒有這個限制條件，求凸包就變成非常容易但卻沒有唯一解的運算。

　　在一個實數向量空間V中，對於給定集合X，所有包含X的凸集的交集S被稱為X的凸包。

　　X的凸包可以用X內所有點()的線性組合來構造。

　　在二維歐幾裡得空間中，凸包可想象為一條剛好包著所有點的橡皮圈。

　　增量式演算法1

　　逐次再點加入，然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點，時間複雜度為O(n²)。

　　包裹法(Jarvis步進法)

　　葛立恆掃描法

　　由最底的一點A₁開始，計算它跟其他各點的連線和x軸的角度，按小至大將這些角度排序，稱它們的對應點為。這裡的時間複雜度可達O(nlogn)。

　　考慮最小的角度對應的點A₃。若由A₂到A₃的路徑相對A₁到A₂的路徑是向右轉的（可以想象一個人沿A₁走到A₂，他站在A₂時，是向哪邊改變方向），表示A₃不可能是凸包上的一點，考慮下一點由A₂到A₄的路徑；否則就考慮A₃到A₄的路徑是否向右轉……直到回到A₁。

　　這個演算法的整體時間複雜度是O(nlogn)，註意每點只會被考慮一次，而不像Jarvis步進法中會考慮多次。

　　這個演算法由葛立恆在1972年發明。^[1]它的缺點是不能推廣到二維以上的情況。

　　單調鏈

　　將點按x坐標的值排列，再按y坐標的值排列。

　　選擇x坐標為最小值的點，在這些點中找出y坐標的值最大和y坐標的值最小的點。對於x坐標為最大值也是這樣處理。將兩組點中y坐標值較小的點連起。在這條線段下的點，找出它們之中y坐標值最大的點，又在它們之間找x坐標值再最小和最大的點……如此類推。

　　時間複雜度是O(n log n)。

　　分治法

　　將點集X分成兩個不相交子集。求得兩者的凸包後，計算這兩個凸包的凸包，該凸包就是X的凸包。時間複雜度是O(n log n)。

　　快包法(Akl-Toussaint啟髮式)

　　選擇最左、最右、最上、最下的點，它們必組成一個凸四邊形（或三角形）。這個四邊形內的點必定不在凸包上。然後將其餘的點按最接近的邊分成四部分，再進行快包法(QuickHull)。