茶年 · 中文维基百科

凸包

Wikipedia · 2026-01-05 维基百科 👁 1 阅读

在一个实数向量空間V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。
: S := \bigcap_{X \subseteq K \subseteq V \atop K\ \mathrm{is\ convex}} 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\}.

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

演算法
增量式算法
逐次將點加入，然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點，時間複雜度為O(n^2)。

包裹法（Jarvis步进法）
首先由一點必定在凸包的點開始，例如最左的一點A_1。然後選擇A_2點使得所有點都在A_1A_2的右方，這步驟的時間複雜度是O(n)，要比較所有點以A_1為原點的極坐標角度。以A_2為原點，重覆這個步驟，依次找到A_3,A_4,...,A_k,A_1。這總共有k步。因此，時間複雜度為O(kn)。

葛立恒（Graham）扫描法
由最底的一點A_1開始（如果有多个这样的点，那么选择最左边的），計算它跟其他各點的連線和x軸正向的角度，按小至大將這些点排序，稱它們的對應點為A_2,A_3,...,A_n。這裡的時間複雜度可達O(n \log{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 \log{n})，注意每點只會被考慮一次，而不像Jarvis步进法中會考慮多次。

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

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

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

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

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

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

各种星形多面体的凸包
應用

  • 圖象處理
  • 模式識別
  • 地理信息系統

參考

參見

  • Carathéodory定理
  • Delaunay三角化

外部連結

#算法 #数学概念 #多胞形 #計算幾何 #凸几何

评论 (0)

  • 还没有评论，来抢沙发吧。