凸包

维基百科,自由的百科全书
凸包(Convex hull):彈性繩帶的類比。

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

的凸包可以用内所有点线性组合来构造。

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

演算法[编辑]

增量式算法[编辑]

逐次將點加入,然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點,時間複雜度為

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

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

葛立恒(Graham)扫描法[编辑]

由最底的一點開始(如果有多个这样的点,那么选择最左边的),計算它跟其他各點的連線和x軸正向的角度,按小至大將這些点排序,稱它們的對應點為。這裡的時間複雜度可達

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

這個演算法的整體時間複雜度是,注意每點只會被考慮一次,而不像Jarvis步进法中會考慮多次。

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

單調鏈[编辑]

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

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

時間複雜度是

分治法[编辑]

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

快包法(Akl-Toussaint启发式)[编辑]

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

各种星形多面体的凸包[编辑]

多面体名称 凸包
小星形十二面体 正二十面体
大十二面体 正二十面体
大星形十二面体 正十二面体
大二十面体 正十二面体

應用[编辑]

參考[编辑]

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

參見[编辑]

外部連結[编辑]