一種新的點集平面點集凸殼構(gòu)建算法

一種新的點集平面點集凸殼構(gòu)建算法

0凸殼構(gòu)建算法凸殼（cov博物館）也稱為凸殼，是指具有指定聚集距離的最小凸集合。在二維情況下,凸殼是由點集中部分點按一定方向順次連接形成的凸多邊形。凸殼是計算幾何中一種最普遍、最基本的結(jié)構(gòu),許多問題可以歸結(jié)為凸殼問題,凸殼在圖像處理、模式識別、計算機圖形學(xué)等領(lǐng)域有著廣泛的應(yīng)用。常見的凸殼構(gòu)建算法包括“卷包裹”算法、格雷厄姆算法、分治算法和增量算法。“卷包裹”算法時間復(fù)雜度均為O(n2);格雷厄姆算法、分治算法、增量算法時間復(fù)雜度均為O(nlogn),但這些算法計算過程都較為麻煩。近年來,又有學(xué)者提出新的凸殼構(gòu)建算法,如2000年周培德提出的Z3-2算法(稱文獻(xiàn)算法),2006年樊廣佺等提出的八方向極值快速凸殼算法(稱文獻(xiàn)算法),2007年郝建強提出的利用正負(fù)劃分性求平面點集凸包的算法(稱文獻(xiàn)算法),2010年吳文周等提出的算法(稱文獻(xiàn)算法)等。文獻(xiàn)算法簡化了凸殼計算過程,但由于該算法對凸殼特性利用仍不夠(對不參與凸殼構(gòu)建的點刪除程度不夠),計算效率仍不高,另外該算法在查找凸殼點的過程中對凸殼邊進(jìn)行不斷分裂,隨著凸殼邊的增多,點到凸殼邊距離的計算會變得越來越復(fù)雜;文獻(xiàn)算法將構(gòu)建凸殼由以往的四方向極值擴展到八方向極值,初步刪除了更多不參與凸殼構(gòu)建的點,但該算法仍具有與文獻(xiàn)算法類似的缺點;文獻(xiàn)算法本質(zhì)上是文獻(xiàn)算法的一個改進(jìn)算法,它簡化了求距離最大點過程,但整體運算過程并沒有很大程度上的優(yōu)化;文獻(xiàn)算法創(chuàng)造性地應(yīng)用了分治思想,單純利用分治減小問題規(guī)模,提高了效率,該算法對凸殼點的查找利用了格雷厄姆方法,過程較為麻煩。本文算法在深入研究前人成果的基礎(chǔ)上,充分利用凸殼特性,提出一種新的凸殼構(gòu)建算法。該算法的內(nèi)核算法極大地加快了求解進(jìn)程,在凸殼求解過程中,角域以極快的速度收斂,從而迅速逼近凸殼邊。為進(jìn)一步減少絕對運算次數(shù),算法又引入迭代處理思想,從而再次提高算法效率。本文的效率分析和實驗測試表明,新算法是一個時間效率高、空間開銷少、可行而且穩(wěn)定的算法。1理論基礎(chǔ)1.1y特征點的計算為方便算法依據(jù)定理的闡述,先引入幾個相關(guān)概念,必要時,對這些概念在算法中的運用加以說明。定義1特征點。點集中,X坐標(biāo)值或Y坐標(biāo)值具有最值特性的點稱為特征點。在二維情況下,對于任意一個給定的點集,總是存在4類特征點:X值最小點、X值最大點、Y值最小點和Y值最大點。把X值最小點和X值最大點統(tǒng)稱為X特征點;Y值最小點和Y值最大點統(tǒng)稱為Y特征點。顯然,特征點位于點集的最小外界矩形上。一個點可以既為X特征點,也為Y特征點,點集中某類特征點也可以不止一個。本文算法中,如果點集中的某點既為X特征點,也為Y特征點,則對這一點分別按X特征點和Y特征點存儲;如果點集中某類特征點不止一個,則選取其中一個作為特征點。最終的特征點總數(shù)按4個處理。定義2特征項。給特征點以最值特性的坐標(biāo)項稱為特征項。X特征點具有X特征項,Y特征點具有Y特征項。對各特征點按逆時針方向順次連接,稱位于同一條線段上的兩特征點為相鄰特征點。容易推知,相鄰特征點的特征項必然不同。定義3特征軸。過特征點,按其特征項所作的水平線或垂直線稱為特征軸,并且稱特征軸與該特征點相互關(guān)聯(lián)。對于一個特征點P,如果它具有X特征項,則它關(guān)聯(lián)X特征軸,直線方程為X=P.x;如果它具有Y特征項,則它關(guān)聯(lián)Y特征軸,直線方程為Y=P.y。定義4角域。連接相鄰特征點,并分別作過這兩個特征點的關(guān)聯(lián)特征軸,形成的直角三角形區(qū)域稱為角域。如果兩相鄰特征點對應(yīng)同一個點,則角域收斂為一個點。定義5特征角。一個點和一個特征點的連線與該特征點的關(guān)聯(lián)特征軸之間的夾角稱為該點的特征角。點與X特征點的相連形成的特征角稱為X特征角,記為α;點與Y特征點的相連形成的特征角稱為Y特征角,記為β。稱角域內(nèi)的所有點中,α值最小的點為α最小點,β值最小的點為β最小點,α最小點和β最小點統(tǒng)稱最小角點。特征角的計算方法為,設(shè)A為X特征點,B為Y特征點,P為角域內(nèi)任意一點,則:???α(P)=arctan(|P.x?A.xP.y?A.y|),P.y≠A.yβ(P)=arctan(|P.y?B.yP.x?B.x|),P.x≠B.x(1){α(Ρ)=arctan(|Ρ.x-A.xΡ.y-A.y|),Ρ.y≠A.yβ(Ρ)=arctan(|Ρ.y-B.yΡ.x-B.x|),Ρ.x≠B.x(1)上式要求對角域內(nèi)的任意點,存在P.y≠A.y且P.x≠B.x,事實上在運算中必然成立。當(dāng)某點P存在P.y=A.y或P.x=B.x時,它必然位于當(dāng)前角域邊界外部,不會納入當(dāng)前角域的考察點集(這樣的點會在之前的角域處理中被刪除)。1.2混合式的聚合點pi、pj定理1點集的特征點一定位于凸殼上。證明由于特征點位于點集的最小外界矩形上,因此,特征點一定位于凸殼上。定理2角域內(nèi)的最小角點一定位于凸殼上。證明假設(shè)角域內(nèi)的α最小點(設(shè)為M)位于凸殼內(nèi),角域的X特征點為A。根據(jù)凸殼性質(zhì),角域內(nèi)必然存在一點P,使得連接AP后,M位于AP左側(cè)。根據(jù)α最小點的定義,M為角域內(nèi)與X特征軸夾角最小的點,因此M必然位于角域內(nèi)任意點與A連線的右側(cè),矛盾。因此,α最小點必定位于凸殼上。對于β最小點可采用同樣的方法證明。定理3在角域內(nèi),設(shè)α最小點為Pi,β最小點為Pj,則:1)如果Pi=Pj,則插入Pi至凸殼后,該角域內(nèi)的凸殼邊構(gòu)建完畢;2)如果Pi≠Pj,設(shè)A為角域內(nèi)的X特征點,B為Y特征點,順次連接A、Pi、Pj、B,則在連接線左側(cè)的點不能參與凸殼構(gòu)建,可以直接刪除,且在剩余點集中,Pi是X特征點,Pj是Y特征點。證明首先證明1)。如圖1(a),由于Pi=Pj,則點Pi既是α最小點又是β最小點,因此,該角域內(nèi)不存在其他能參與凸殼構(gòu)建的點,否則,與Pi既是α最小點又是β最小點矛盾,故此時該角域內(nèi)的凸殼邊構(gòu)建完畢。接著證明2)。如圖1(b),由于在角域內(nèi),連接A、B后,A、Pi、Pj、B左側(cè)的點位于多邊形APiPjB內(nèi)部,故這些點不能參與凸殼構(gòu)建,應(yīng)予刪除。根據(jù)特征角的性質(zhì),角域內(nèi)的點必然位于按逆時針方向順次連接特征點和最小角點構(gòu)成的折線段(如圖APiPjB)的左側(cè),即剩余點集應(yīng)位于以兩最小角點的連線(如圖PiPj)為一條邊、以最小角點與相應(yīng)特征點的連線(如圖APi、BPj)之交點為另一個頂點(設(shè)為M)的三角形內(nèi)部。根據(jù)α最小點和β最小點的性質(zhì),Pi、Pj是三角形PiPjM范圍內(nèi)分別離X特征軸和Y特征軸最近的點,故Pi、Pj分別是剩余點集的X特征點和Y特征點。定理1和定理2給出了凸殼點的選取法則,定理3則回答了如何尋找滿足條件的凸殼點以及何時可以終止對凸殼點的查找。定理3是一個重要定理,它說明了新角域的形成法則、新特征點的產(chǎn)生法則以及前后兩代特征點之間的繼承法則。思考定理3不難發(fā)現(xiàn),而情形1)是情形2)的一種特例:當(dāng)情形2)退化成情形1)時,新角域退化成一個點,則新的考察點集為空集,所以這個角域內(nèi)的凸殼邊構(gòu)建完畢。2算法思想和算法描述2.1凸殼定位算法如果不考慮迭代思想,本文算法步驟應(yīng)該是:首先找到點集內(nèi)的4個特征點,分別連接相鄰個特征點并利用特征軸構(gòu)建4個(或3個或2個)角域,將點集加入角域(刪除不能加入到任何角域的點),然后對各角域逐次查找α最小點和β最小點將其插入凸殼,根據(jù)定理3刪除不會參與凸殼構(gòu)建的點同時進(jìn)行角域更新。角域不斷收斂,當(dāng)所有角域考察點集均為空集時,凸殼構(gòu)建完畢。稱上述過程描述的算法為本文算法的內(nèi)核算法。內(nèi)核算法總是會成對查找特征點,并且會最大限度地縮小問題規(guī)模點集。盡管內(nèi)核算法實際上已經(jīng)非常高效,但當(dāng)算法的問題規(guī)模n很大時,算法中α、β的絕對運算次數(shù)仍然很大。考慮到本文算法對非凸殼點的強大的快速刪除能力,將迭代思想運用于角域處理:由于凸殼上的頂點必然包含于其子凸殼頂點中,因此當(dāng)進(jìn)行角域處理時,如果角域內(nèi)的點數(shù)量大于某個常數(shù)(稱為問題規(guī)模限定數(shù)),可以先遞歸調(diào)用本文算法,得到一個子凸殼,將子凸殼的頂點作為角域的輸入點集,再執(zhí)行角域處理。2.2qp模型的建立下面采用偽代碼的形式給出算法的完整描述:算法:GetConvexHull(P)。輸入:P={pi|i=1,2,…,n};輸出:Q={qi|qi∈CH(P),i=0,1,…}。定義算法的問題規(guī)模限定數(shù)BoundNum;1)檢查P中點的數(shù)量n;if(n<4)thenQ=P,算法結(jié)束;2)在P中找到minY、maxX、maxY、minX4個特征點,依次存放于t、t、t、t、將t到t依次存放于Q;3)初始化4個數(shù)組corner、corner、corner、corner;3.1)while(P中的點沒有處理完畢)if(pi位于某兩相鄰特征點連線t[k]t[k+1]的右側(cè))then將pi加入corner[k];if(pi均位于4條相鄰特征點連線的左側(cè))then將pi從P中刪除3.2)清空P4)fori=0to3/*對各角域執(zhí)行角域處理*/4.1)將t[i]賦給T1,t[i+1]賦給T2,T1、T2為本角域兩個初始特征點4.2)while(corner[i].size>0)if(corner[i].size=1)then將corner[i]中唯一的一個點加入Q,清空corner[i]if(corner[i].size>BoundNum)then初始化一個集合Temp遞歸調(diào)用本文算法,將返回結(jié)果賦給Temp清空corner[i],并將Temp中的元素賦給corner[i]找到當(dāng)前角域的α最小點A和β最小點B將A、B按適當(dāng)?shù)捻樞蚣尤隥中,保持點按逆時針排列更新角域特征點T1、T2,使T1=A,T2=B定義變量j,初值為0while(j<corner[i].size)從corner[i]取出第j個點pjif(pj位于線段T1T2的左側(cè))then將pj從corner[i]中刪除5)算法結(jié)束。3算法的復(fù)雜性分析3.1角域的調(diào)節(jié)作用本文算法可看成是對點集進(jìn)行初始劃分然后對各角域進(jìn)行角域處理的過程,在角域處理過程中,不斷查找當(dāng)前角域的特征點并對角域進(jìn)行更新,角域不斷收斂,進(jìn)而迅速逼近凸殼邊界。由于算法在初始劃分階段對非凸殼點的刪除比例以及角域處理過程中對非凸殼點的刪除比例等都取決于點的分布情況,現(xiàn)運用概率統(tǒng)計相關(guān)方法來分析本文算法的時間復(fù)雜度。設(shè)算法初始輸入點數(shù)為N,總的運算次數(shù)為T(N);初始劃分的角域數(shù)量為k,經(jīng)過初始劃分后,剩余點數(shù)與初始輸入點總數(shù)之比為a;在角域處理過程中,對問題規(guī)模為n的點集,基本運算次數(shù)為F(n)。由于算法在初始劃分階段需要遍歷所有點以劃分角域,然后執(zhí)行角域處理,故:設(shè)角域處理時,問題規(guī)模限定數(shù)為B。對于點數(shù)為n的角域,當(dāng)n<B時,基本運算次數(shù)為f(n),由于此時的過程是先求解n次α角和β角以得到最小α點和最小β點,如果它們對應(yīng)同一個點(設(shè)這樣的概率為p),則該角域處理結(jié)束,否則,以這兩個點為新的X特征點和Y特征點對新的角域執(zhí)行角域處理(設(shè)新角域點數(shù)與原角域點數(shù)之比為b);當(dāng)n≥B時,則先遞歸調(diào)用本文算法以減小問題規(guī)模(設(shè)問題規(guī)模減小比例的平均值為c),然后執(zhí)行與n<B時的相似的處理過程。則F(n)滿足下式:F(n)={f(n),n＜BT(n)+f(cn),n≥BF(n)={f(n),n＜BΤ(n)+f(cn),n≥B;c∈(0,1)(3)f(n)滿足下列關(guān)系式:{f(n)=n+p×0+(1?p)f(bn);p,b∈(0,1)f(0)=0(4){f(n)=n+p×0+(1-p)f(bn);p,b∈(0,1)f(0)=0(4)解f(n),再將f(n)代入式(2)得:F(n)={n1?(1?p)b,n＜BT(n)+cn1?(1?p)b,n≥BF(n)={n1-(1-p)b,n＜BΤ(n)+cn1-(1-p)b,n≥B;a,b,c,p∈(0,1)(5)由于經(jīng)過初試劃分之后,各角域內(nèi)點的數(shù)量不盡相同,因此T(N)的表達(dá)式不易確定。下面考慮兩種特殊情況,并且這兩種情況下各角域內(nèi)的點均勻分布。情況1n1到nk均小于B時。各角域的表達(dá)式為:F(ni)=ni1?(1?p)bF(ni)=ni1-(1-p)b;i=1,2,…,k(6)聯(lián)立式(2)和式(6),解方程組得:T(N)=N?(1+a1?(1?p)b)Τ(Ν)=Ν?(1+a1-(1-p)b);a,b,p∈(0,1)(7)情況2n1到nk均大于或等于B且各角域內(nèi)經(jīng)過遞歸處理后,點的數(shù)量仍大于或等于B時(相當(dāng)于是各角域內(nèi)的點數(shù)均為無限多的情況)。各角域F(n)的表達(dá)式為:F(ni)=T(ni)+cni1?(1?p)bF(ni)=Τ(ni)+cni1-(1-p)b;i=1,2,…,k(8)聯(lián)立式(2)和式(7),解方程組得:T(N)=N?{1+[1+c1?(1?p)b]?a1?a};Τ(Ν)=Ν?{1+[1+c1-(1-p)b]?a1-a};a,b,c,p∈(0,1)(9)由于a、b、c、p均與點的分布特點相關(guān),而與點的數(shù)量N無關(guān),因此,從式(7)和式(9)可知,上述兩種情況下,算法時間復(fù)雜度均為線性次。由于上述兩種情況代表了點數(shù)很少和點數(shù)極多兩種極限情況,實際情況總是介于兩者之間,且算法復(fù)雜度與點的分布無關(guān),因此,本文算法時間復(fù)雜度為線性次,即O(n)。算法的具體運算次數(shù)與點的分布狀態(tài)相關(guān),不同狀態(tài)分布的點,算法運行時間線性增長的情況會有不同。3.2角域的收斂顯然,本文算法中占用空間最多的時候是剛開始時進(jìn)行角域劃分的時候,以后,隨著算法的運行,角域逐漸收斂,所需要存儲的點數(shù)也隨之減少。因此,本文算法的空間復(fù)雜度為O(n)。4材料2.2不設(shè)置在真核和弘揚競爭優(yōu)勢的同時進(jìn)行計算為評價本文算法運行效率,采用兩種不同坐標(biāo)尺度和分布特征的數(shù)據(jù)進(jìn)行了實驗,并與經(jīng)典的Graham算法進(jìn)行了對比。實驗數(shù)據(jù)均采用計算機代碼產(chǎn)生的隨機點(隨機方式不同),第一組數(shù)據(jù)坐標(biāo)范圍約為X∈(100,1600),Y∈(80,700),第二組數(shù)據(jù)坐標(biāo)范圍約為X∈(0,300000),Y∈(0,150000)。圖2(a)、2(b)分別是對兩組數(shù)據(jù)中,點數(shù)為200萬的文件點及其凸殼可視化后的效果圖,表1、2分別為對兩組數(shù)據(jù)用Graham算法和本文算法將各數(shù)據(jù)測試多次后的時間統(tǒng)計表(由于當(dāng)點數(shù)達(dá)到20萬時,Graham算法運行速度較慢,與本文算法相比已經(jīng)出現(xiàn)很大差距,對Graham算法進(jìn)一步測試意義不大,因此,對于20萬以上的數(shù)據(jù),本文沒有進(jìn)行進(jìn)一步實驗)。本試驗采用的計算機主頻為2.2GHz,內(nèi)存為2