顧及鄰近五點的建筑物多邊形化簡方法

李俐俐，李成名，盧小平，殷 勇，武鵬達(dá)

(1. 河南理工大學(xué)礦山空間信息技術(shù)國家測繪局重點實驗室，河南 焦作 454003；2. 中國測繪科學(xué)研究院，北京 100830)

建筑物作為地圖三大要素之一，在大比例尺地形圖的數(shù)值載負(fù)量和面積載負(fù)量中均占有很大比重，對其綜合的結(jié)果直接影響著地圖質(zhì)量及圖面效果[1]。對地圖進(jìn)行縮編時，建筑物多邊形綜合過程中選擇對制圖有用的信息進(jìn)行保留，不需要的信息則舍掉，化簡是不可缺少的一步[2]?；喴馕吨诨颈３制湫螒B(tài)特征和面積大小的同時，通過減少其輪廓線的冗余細(xì)節(jié)，使得建筑物得到更簡潔有效的表達(dá)[3]。

建筑物化簡現(xiàn)已積累了大量的算法，包括垂距法、偏角法和經(jīng)典的Douglas-Peucker算法、Lang算法[4-6]等。但這些算法只針對線狀要素，對于建筑物幾何特征的保持沒有作過多的考慮。由于建筑物輪廓普遍呈現(xiàn)直角轉(zhuǎn)折形式，因此通用的曲線化簡算法無法有效地處理建筑物化簡[7]。文獻(xiàn)[8]提出了基于鄰近四點法的建筑物多邊形化簡方法。文獻(xiàn)[9]改進(jìn)了鄰近四點法，通過對凹凸部類型判別及區(qū)別處理實現(xiàn)快速化簡，但是化簡過于注重面積均衡，導(dǎo)致特征點丟失。文獻(xiàn)[10—11]提出了模板匹配方法，用匹配成功的模板來置換原要素實現(xiàn)化簡，該方法在匹配中存在多個最相似的模板，不能處理結(jié)構(gòu)復(fù)雜的街區(qū)，模板庫的完備性也有待補充和豐富。文獻(xiàn)[12]研究了平面圖形的矩形差分化簡方法，對規(guī)則建筑物的邊界化簡比較明顯，但是并不具有普適性。建立三角網(wǎng)進(jìn)行全局控制，再對凹凸部位進(jìn)行填充、刪除操作，需要對所有特征點進(jìn)行三角剖分再對三角形逐一判別、處理，復(fù)雜度較高。文獻(xiàn)[14—15]研究了居民地的綜合策略，包括街區(qū)多邊形的化簡、直角化及夸大等操作的算子設(shè)計，并給出了街區(qū)綜合的一個可行的操作流程。

本文在研究上述算法的基礎(chǔ)上，對傳統(tǒng)的基于三點、四點的化簡算法進(jìn)行拓展和改善，提出基于鄰近五點的建筑物多邊形化簡算法。該算法通過對多邊形凹凸結(jié)構(gòu)的類型判別，判斷各類型最小可視長度兩邊圖形的面積，判斷彎曲部分是否化簡，增加線間的位置關(guān)系判定，對不同類型處理單元進(jìn)行漸進(jìn)式分類化簡。

1 鄰近五點組合的定義與結(jié)構(gòu)識別

本文對建筑物多邊形鄰近的五個節(jié)點進(jìn)行識別，通過鄰近四點組成的三邊進(jìn)行處理單元判斷，第四條邊進(jìn)行角度判斷。本文對于鄰近五點的處理可等同于對鄰近四邊的處理，對于邊數(shù)小于5的建筑物多邊形不作化簡。

處理單元組合：本文采用從局部到整體的漸進(jìn)式處理方法對建筑物進(jìn)行化簡，從最短邊開始搜索識別處理單元。將最短邊編號設(shè)置為L1，兩鄰邊分別編號為L2、L3，其中較短的為L2，另一邊為L3，與L2另一邊相連接的邊設(shè)為L4；L1、L2、L3、L4，即1、2、3、4、5點構(gòu)成一個處理單元組合，結(jié)構(gòu)如圖1所示。

Z形、U形定義：算法采用填凹部或削凸部處理手段實現(xiàn)化簡，而凹凸部形態(tài)至少要四個鄰近點才能描述，以多邊形上相鄰四點作為基本處理單元，將其分成U形和Z形。若1、4位于線段2、3兩側(cè)，則將該組合結(jié)構(gòu)稱為Z形結(jié)構(gòu)，如圖1中的1、2、3、4點組成Z形；否則為U形結(jié)構(gòu)，8、9、10、11點組成U形。在這里，對于U形結(jié)構(gòu)不作進(jìn)一步細(xì)分，僅依據(jù)該形態(tài)特征對建筑物邊界節(jié)點進(jìn)行劃分。

平行與非平行模式定義：在實際地圖上建筑物并非都是直角形態(tài)，會出現(xiàn)各種復(fù)雜形態(tài)，為進(jìn)一步化簡作準(zhǔn)備，需在區(qū)分U形和Z形后依據(jù)L2和L3位置區(qū)分平行與非平行。L2和L3延長后無交點稱為平行模式；L2和L3延長后形成交點稱為非平行模式。

L3與L4位置定義：對于鄰近五點中第四條邊在本文接下來的研究過程中，涉及該夾角的角度需判定是否為尖角，因此對其位置進(jìn)行定義，即以線段L3為基準(zhǔn)，沿逆時針方向，L3與L4形成的夾角角度。

2 基于鄰近五點的建筑物多邊形化簡

2.1 化簡原理

基于鄰近五點建筑物多邊形化簡方法的思想是通過鄰近的五點，根據(jù)不同的處理單元組合，依據(jù)相應(yīng)模式對建筑物邊界用延伸或縮進(jìn)兩邊填充或刪除面積小于閾值部分的凹凸部，實行漸進(jìn)式分類化簡。如圖2所示。

2.1.1 Z形平行模式

如圖2(a)所示，將節(jié)點4向長邊L3的延長線作垂線，垂足點為點6，同時為最大程度上減小特征點變化，同時使得圖形在某一邊能保持該邊的趨勢，對L3和L4進(jìn)行延伸，交點為點7，判斷垂足點6與交點7距離是否在給定閾值范圍內(nèi)，同時加上四邊形2347面積判斷，若該四邊形面積在閾值內(nèi)，則直接用點7代替垂足點6，刪除掉舊節(jié)點2、4，則17、75即為化簡后的邊；若不在，則該邊不作化簡。

2.1.2 U形平行模式

化簡方法同Z形平行模式，此處不再贅述，如圖2(b)所示。

2.1.3 Z形非平行模式

算法盡可能保持面積變化最小，選取刪減或填充面積較小的部分。此時需要比較L1、L3和L2相交所圍成的三角形的面積和L1、L2、L3、L4圍成圖形的面積大小(如圖2(c)所示)，選取面積較小的部分進(jìn)行填充或刪除。若三角形面積小，將L1與L3求交點8，18、84、45則為化簡后的邊。若L1、L2、L3、L4圍成圖形2347的面積小，此時化簡方法同平行模式。

2.1.4 U形非平行模式

對于U形非平行模式，為滿足算法盡可能保持面積變化最小，此時需要比較L1、L2和L3相交所圍成的三角形的面積和L1、L2、L3、L4圍成圖形的面積大小(如圖2(d)所示)，選取面積較小的部分進(jìn)行填充或刪除。若三角形面積小，將L1與L3求交點8，18、84、45則為化簡后的邊。若L1、L2、L3、L4圍成圖形2347的面積小，此時化簡方法同平行模式。

2.2 化簡特點

鄰近四點法采用面積均衡處理模式化簡，詳細(xì)見文獻(xiàn)[8]，化簡結(jié)果用灰線表示，鄰近五點法采用填充或削減模式化簡，結(jié)果用黑線表示(如圖3所示)。從最終化簡對比圖中可直觀看出，鄰近五點法基本單元化簡模式比四點法更能夠保持基本形狀且與原圖形貼合度更高?；卩徑狞c的化簡算法過于注重面積均衡，化簡時不能顧及更多局部信息，如圖3中1、2、3處。

3 建筑物多邊形削尖處理

3.1 Z形平行模式

在Z形平行模式下，當(dāng)延伸L3和L4邊進(jìn)行化簡時，L3和L4夾角位置在0～60°和300°～360°之間認(rèn)為是產(chǎn)生尖角，如圖4(a)、圖4(b)所示。化簡時若在0～60°范圍內(nèi)，連接2、4，刪除點3，此時1245即化簡后的邊(如圖4(a)所示)。夾角角度若在300°～360°范圍內(nèi)，此時將點2向L4作垂線交于點7，1275即化簡后的邊(如圖4(b)所示)。

3.2 U形平行模式

在U形平行模式下，當(dāng)L3和L4夾角位置在0～60°和300°～360°時，將L4延長與L3交于點6后，認(rèn)為該角度為尖角，如圖4(c)、圖4(d)所示，此時由點4向L3作垂線交于點7，1745或1754為化簡后的邊(如圖4(c)、圖4(d)所示)。

3.3 Z形非平行模式

當(dāng)L2和L3交點位于L2及L2延長線上時，237面積大于L1、L2、L3、L4圍起來的部分面積且L3與L4夾角為0～60°和300°～360°時會形成尖角，如圖5(a)、圖5(b)所示。此時將點2向L4作垂線，交L4于點8，12、28、85即為化簡后的邊(如圖5(a)、圖5(b)所示)。

3.4 U形非平行模式

對于U形非平行模式下，一是當(dāng)L3和L2的夾角過小時，化簡相交時產(chǎn)生尖角；二是當(dāng)L3和L4的夾角過小時，在延伸的過程中也會產(chǎn)生尖角。

(1)L1、L2、L3圍成的三角形面積大于L1、L2、L3、L4圍成多邊形的面積：當(dāng)L3與L4的夾角為0～60°和300°～360°，將L1邊的點3沿L2平移到4點，將L4沿移動后L1的趨勢交L3于點8，判斷2348的面積是否在閾值范圍內(nèi)，若在，此時1845為一個基本處理單元，如圖5(c)所示。若2348面積大于給定閾值，則該邊不作處理。若無交點8，此時直接連接1、4點。

(2)L1、L2、L3圍成的三角形面積小于L1、L2、L3、L4圍成多邊形的面積：當(dāng)L3與L2的夾角小于60°時，延長L3和L2相交于點6，此時形成尖角(如圖5(d)所示)，則需考慮L4和L3的位置關(guān)系進(jìn)行化簡，化簡方法同步驟(1)。

4 化簡過程

(1) 建筑物輪廓數(shù)據(jù)預(yù)處理，去除冗余點。

(2) 判斷邊數(shù)，若邊數(shù)n<5，不進(jìn)行輪廓化簡，化簡結(jié)束；若邊數(shù)n≥5，轉(zhuǎn)步驟(3)。

(3) 計算建筑物多邊形輪廓最短邊，設(shè)為L1；通過L1，按照上述組合結(jié)構(gòu)定義，找到L2、L3、L4,判斷基本處理單元類型。

(4) 多建筑物多邊形化簡并作化簡過程中削尖處理。

(5) 刪除舊節(jié)點，連接新節(jié)點。

(6) 更新節(jié)點，計算多邊形最短邊。

(7) 重復(fù)步驟(3)—(6)，直至該面狀建筑物輪廓均大于化簡指標(biāo)或邊數(shù)小于5，化簡結(jié)束。

5 試驗與分析

本文以Microsoft Visual Studio 2010作為開發(fā)環(huán)境，利用中國測繪科學(xué)研究院自主研制的WJ-Ⅲ無級地圖工作站，對本文方法進(jìn)行實例驗證。選取某地區(qū)1∶1萬部分建筑物多邊形數(shù)據(jù)作為試驗數(shù)據(jù)，圖6(a)為選取較為典型的一組多邊形，圖6(b)、圖6(c)分別為鄰近四點法和鄰近五點法的化簡結(jié)果，圖6(d)為鄰近四點法與鄰近五點法化簡結(jié)果的對比。

從圖6中可以得出，在同比例尺、同閾值情況下，采用鄰近四點法和鄰近五點法化簡都可以基本保持建筑物輪廓特征，但在建筑物輪廓細(xì)節(jié)特征處的保持，從圖6(b)、圖6(c)中圓圈處可對比看出鄰近五點法保持效果更好。圖6(b)、圖6(c)中輪廓2、8矩形框處，鄰近四點法由于化簡前削尖，削尖與化簡脫離，尖角不容避免；而鄰近五點法顧及尖角，削尖與化簡結(jié)合，避免尖角的產(chǎn)生。從圖6(d)可以看出，對比原始建筑物，鄰近五點法化簡后的結(jié)果更加貼合原始建筑物輪廓，保證了化簡前后建筑物的整體結(jié)構(gòu)不發(fā)生明顯變化。而鄰近四點法過于注重面積均衡，雖然保持了基本輪廓特征，但丟失掉特征點。

建筑物多邊形化簡中特征點的提取、基本形狀及面積的保持是評定各種算法精度和效率的重要標(biāo)準(zhǔn)[16]。筆者對建筑物化簡結(jié)果進(jìn)行了數(shù)據(jù)統(tǒng)計，見表1。表1中化簡方法1為鄰近四點法，方法2為鄰近五點法。保留特征點數(shù)設(shè)定為化簡后的點與原建筑物輪廓特征點一致或化簡后點在原建筑物多邊形邊上。從表1統(tǒng)計結(jié)果來看，鄰近四點法化簡后面積變化率大部分小于鄰近五點法，這與鄰近四點法注重面積均衡一致；在同比例尺化簡情況下，鄰近五點法相比四點法，化簡力度更優(yōu)，化簡后的建筑物點數(shù)多，特征保持較好，保留特征點數(shù)多，更加貼合原始建筑物，化簡效果更好。

6 結(jié) 語

本文提出了一種基于鄰近五點的建筑物多邊形化簡方法，通過對建筑物邊界特征進(jìn)行智能識別和分類，采用漸進(jìn)式化簡方法對建筑物容易產(chǎn)生尖角的部分進(jìn)行削尖處理。本文方法在保持居民地基本輪廓特征的同時，能夠很好地避免尖角的產(chǎn)生，保證了化簡前后建筑物的整體結(jié)構(gòu)不發(fā)生明顯變化，相比于鄰近四點法更好地保持了建筑物的特征，更加貼合原始建筑物。但該方法沒有注意面積均衡問題，同時角度閾值的不同設(shè)定也會影響化簡結(jié)果。在今后的研究中將進(jìn)一步探討在面積均衡的同時如何尋求合適的閾值對建筑物多邊形進(jìn)行化簡。

表1 化簡試驗數(shù)據(jù)

注：表中各變化率是指化簡前后的差值與原始值的比率。