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

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