凸包

维基百科，自由的百科全书

凸包（Convex hull）：彈性繩帶的類比。

在一个实数向量空間 $V$ 中，对于给定集合 $X$ ，所有包含X的凸集的交集 $S$ 被称为 $X$ 的凸包。

$S := \bigcap_{X \subseteq K \subseteq V \atop K\ \mathrm{is\ konvex}} K.$

$X$ 的凸包可以用 $X$ 内所有点 $(x_1, \ldots, x_n)$ 的线性组合来构造。

$S := \left\{ \left. \, \sum_{j=1}^n t_j x_j\, \right| x_j \in X,\, \sum_{j=1}^n t_j = 1,\, t_j \in \lbrack 0, 1 \rbrack \, \right\}.$

在二维欧几里得空间中，凸包可想象為一條剛好包著所有點的橡皮圈。

[编辑] 演算法

[编辑] 增量式算法1

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

[编辑] 包裹法(Jarvis步进法)

首先由一點必定在凸包的點開始，例如最左的一點 $A 1$ 。然後選擇 $A 2$ 點使得所有點都在 $A B$ 的右方，這步驟的時間複雜度是 $O (n)$ ，要比較所有點以 $A 1$ 為原點的極坐標角度。以 $A 2$ 為原點，重覆這個步驟，依次找到 $A 3, A 4,..., A k, A 1$ 。這總共有 $k$ 步。因此，時間複雜度為 $O (n k)$ 。

[编辑] 葛立恒扫描法

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

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

這個演算法的整體時間複雜度是 $O (n l o g n)$ ，注意每點只會被考慮一次，而不像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)。

[编辑] 應用

[编辑] 參考

↑ Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 955–956 of section 33.3: Finding the convex hull.
The Convex Hull of a 2D Point Set or Polygon, by Dan Sunday