凸包
維基百科,自由的 encyclopedia
在一個實數向量空間中,對於給定集合
,所有包含X的凸集的交集
被稱為
的凸包。
![](http://upload.wikimedia.org/wikipedia/commons/b/bc/ConvexHull.png)
的凸包可以用
內所有點
的線性組合來構造。
在二維歐幾里得空間中,凸包可想像為一條剛好包着所有點的橡皮圈。
演算法
增量式算法
逐次將點加入,然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點,時間複雜度為。
包裹法(Jarvis步進法)
首先由一點必定在凸包的點開始,例如最左的一點。然後選擇
點使得所有點都在
的右方,這步驟的時間複雜度是
,要比較所有點以
為原點的極坐標角度。以
為原點,重覆這個步驟,依次找到
。這總共有
步。因此,時間複雜度為
。
葛立恆(Graham)掃描法
![](http://upload.wikimedia.org/wikipedia/commons/1/1b/Graham_scan.png)
由最底的一點開始(如果有多個這樣的點,那麼選擇最左邊的),計算它跟其他各點的連線和x軸正向的角度,按小至大將這些點排序,稱它們的對應點為
。這裏的時間複雜度可達
。
考慮最小的角度對應的點。若由
到
的路徑相對
到
的路徑是向右轉的(可以想像一個人沿
走到
,他站在
時,是向哪邊改變方向),表示
不可能是凸包上的一點,考慮下一點由
到
的路徑;否則就考慮
到
的路徑是否向右轉……直到回到
。
這個演算法的整體時間複雜度是,注意每點只會被考慮一次,而不像Jarvis步進法中會考慮多次。
這個演算法由葛立恆在1972年發明。[1]它的缺點是不能推廣到二維以上的情況。
單調鏈
將點按x坐標的值排列,再按y坐標的值排列。
選擇x坐標為最小值的點,在這些點中找出y坐標的值最大和y坐標的值最小的點。對於x坐標為最大值也是這樣處理。將兩組點中y坐標值較小的點連起。在這條線段下的點,找出它們之中y坐標值最大的點,又在它們之間找x坐標值再最小和最大的點……如此類推。
時間複雜度是。
將點集X分成兩個不相交子集。求得兩者的凸包後,計算這兩個凸包的凸包,該凸包就是X的凸包。時間複雜度是。
快包法(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(頁面存檔備份,存於互聯網檔案館)
參見
- Carathéodory定理
- Delaunay三角化