郭沛沛，李成名，殷　勇

1. 山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院，山東 青島266590； 2. 中國(guó)測(cè)繪科學(xué)研究院GIS所，北京 100830

?

建筑物合并的Delaunay三角網(wǎng)分類過(guò)濾法

郭沛沛1,2，李成名2，殷勇2

1. 山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院，山東 青島266590； 2. 中國(guó)測(cè)繪科學(xué)研究院GIS所，北京 100830

Foundationsupport：ProjectSupportedbytheNationalKeyTechnologyResearchandDevelopmentProgramoftheMinistryofScienceandTechnologyofChina(No.2015BAJ06B01);ProjectSupportedbySpecialScientificResearchFundofPublicWelfareProfessiononSurveying,MappingandGeo-Information(No. 201412003);BasicResearchSupportProjectofChinaAcademyofSurveyingandMapping(No.7771530)

建筑物面合并的方法是大比例尺地圖綜合研究的重要內(nèi)容之一，本文提出了一種借助三角網(wǎng)進(jìn)行建筑物合并的方法：針對(duì)約束Delaunay三角網(wǎng)中三角形的形態(tài)特征，提出了6種度量參數(shù)，依據(jù)這些參數(shù)進(jìn)行排除和修復(fù)篩選操作；然后自動(dòng)識(shí)別保留下來(lái)三角形的外輪廓作為建筑物之間的橋接部分，并對(duì)其進(jìn)行直角化處理；接下來(lái)通過(guò)橋接部分和建筑物面的融合實(shí)現(xiàn)建筑物的合并，同時(shí)保持其直角化特征。最后，以多樣性的實(shí)際數(shù)據(jù)進(jìn)行實(shí)際處理，驗(yàn)證了該方法的正確性和高效性。

制圖綜合；建筑物合并；約束Delaunay三角網(wǎng)；直角化

建筑物是大比例尺城市地圖的核心要素，對(duì)地圖表達(dá)的效果具有重要影響。建筑物的合并作為大比例尺地圖綜合的難點(diǎn)之一，一直是國(guó)內(nèi)外制圖綜合領(lǐng)域的研究熱點(diǎn)，出現(xiàn)了不同的方法和策略：凸包演化方法[1-2]、掃描擴(kuò)展搜索[3]及類似的基于數(shù)學(xué)形態(tài)學(xué)的方法適用于圖像數(shù)據(jù)，即柵格數(shù)據(jù)，對(duì)矢量格式的數(shù)據(jù)處理需要借助矢柵轉(zhuǎn)換的過(guò)程才能完成，合并過(guò)程略顯繁復(fù)。合并結(jié)果在形狀上可能產(chǎn)生較大彎曲且精度問(wèn)題會(huì)對(duì)合并結(jié)果產(chǎn)生影響；基于緩沖區(qū)的面合并方法[4]是對(duì)多邊形建立外側(cè)緩沖區(qū)，根據(jù)緩沖區(qū)的相交情況來(lái)實(shí)現(xiàn)合并的。但在實(shí)際應(yīng)用中，對(duì)矢量多邊形建立緩沖區(qū)及其求交運(yùn)算效率不高，難以用于大范圍數(shù)據(jù)處理中。而基于Delaunay三角網(wǎng)的方法通過(guò)對(duì)研究區(qū)域進(jìn)行三角剖分，借助三角網(wǎng)來(lái)識(shí)別多邊形的空間關(guān)系，輔助完成多邊形的合并。Delaunay三角剖分算法以其強(qiáng)大的空間鄰近探測(cè)和分析功能，引起了制圖專家的重視并將其應(yīng)用到地圖自動(dòng)綜合中[5-8]。目前使用Delaunay三角網(wǎng)進(jìn)行建筑物的合并方面的探索主要有：文獻(xiàn)[10—11]介紹了二維空間中約束Delaunay三角網(wǎng)剖分結(jié)構(gòu), 借助此結(jié)構(gòu)可以進(jìn)行形式化條件檢索，用于支持鄰近多邊形的搜索和合并。但該方法沒(méi)有具體指出搜索和合并操作的具體內(nèi)容。文獻(xiàn)[12—13]探索使用三角網(wǎng)結(jié)構(gòu)模型對(duì)包括建筑物在內(nèi)的地理要素進(jìn)行鄰近關(guān)系的搜索。文獻(xiàn)[14]使用三角網(wǎng)表達(dá)建筑物之間的空間拓?fù)潢P(guān)系，以網(wǎng)中的最短邊作為處理標(biāo)準(zhǔn)實(shí)現(xiàn)建筑物多邊形的合并。文獻(xiàn)[15]提出了利用Delaunay三角網(wǎng)生成拓?fù)湫畔⒌乃悸?，并指出可以根?jù)多邊形之間的最小距離來(lái)判斷是否聚合。但最小距離作為聚合標(biāo)準(zhǔn)并不能取得最好的效果。文獻(xiàn)[16—17]把三角網(wǎng)和城市形態(tài)學(xué)等相結(jié)合進(jìn)行建筑物的聚類和綜合。文獻(xiàn)[18]把Agent技術(shù)與TIN技術(shù)、聚類技術(shù)相結(jié)合的算法(ABTM)，這使得算法的智能性得到很大提高，但是對(duì)建筑物中空白區(qū)域無(wú)法進(jìn)行處理。

借助Delaunay三角網(wǎng)進(jìn)行面綜合為建筑物合并提供了一種解決思路，但縱觀這些研究成果，仍存在一些不足：文獻(xiàn)[9—10]重點(diǎn)介紹了使用三角網(wǎng)對(duì)空間進(jìn)行分割所要建立的數(shù)據(jù)模型，以及使用這些數(shù)據(jù)模型對(duì)面狀目標(biāo)的空間關(guān)系進(jìn)行研究，未具體介紹應(yīng)用三角網(wǎng)進(jìn)行面目標(biāo)合并的過(guò)程。文獻(xiàn)[14—15]中使用Delaunay三角網(wǎng)來(lái)確定建筑物之間的鄰近關(guān)系，進(jìn)而進(jìn)行合并。但文獻(xiàn)[14]指出由于狹長(zhǎng)三角形的存在，采用的是Delaunay三角形的最短邊和閾值進(jìn)行比較。類似的，文獻(xiàn)[15]采用的是多邊形之間的最小距離。這兩種取極小值的方式會(huì)夸大聚類結(jié)果，不夠合理。文獻(xiàn)[10—11]在探索鄰近關(guān)系時(shí)使用的是兩多邊形之間三角形的平均長(zhǎng)度，但是在對(duì)面進(jìn)行合并時(shí)探討的是一般面目標(biāo)的合并，并未顧及到建筑物作為一種特殊的面，具有直角化的特征，合并結(jié)果丟失了這一特征。

仔細(xì)探索大量實(shí)際數(shù)據(jù)，建筑物面往往具有成群分布(密集)、形狀規(guī)則(直角化特征) 、坐落有序(多有平行邊)等特點(diǎn)。本文研究發(fā)現(xiàn)使用建筑物的邊線建立約束Delaunay三角網(wǎng)，建筑物都被三角網(wǎng)所覆蓋，建筑物通過(guò)三角形進(jìn)行連接，它們之間的空隙由三角形所填充。構(gòu)建的三角網(wǎng)具有無(wú)重疊、無(wú)縫隙的全覆蓋的特點(diǎn)。為此，對(duì)于距離較近的建筑物，連接它們的三角形往往具有良好的幾何形態(tài)特征。據(jù)此，針對(duì)之前研究的不足，本文對(duì)Delaunay三角網(wǎng)中的三角形提出了6種度量參數(shù)，從多種角度對(duì)三角形進(jìn)行分類過(guò)濾以確定建筑物的空間鄰近關(guān)系。同時(shí)，借助保留下來(lái)的三角形識(shí)別出建筑物的橋接部分，并對(duì)橋接部分的進(jìn)行直角化處理。最后，通過(guò)橋接部分和建筑物面的融合實(shí)現(xiàn)建筑物的合并，保持了合并結(jié)果的直角化特征。

1　合并原理

1.1建筑物合并

建筑物的合并主要分為兩種。一種是拓?fù)溧徑暮喜?，即建筑物之間具有共邊的情況，刪除公共邊即可實(shí)現(xiàn)合并。這種實(shí)現(xiàn)比較簡(jiǎn)單，常用的方式是對(duì)建筑物構(gòu)建拓?fù)洌瑢⑼負(fù)渲型瑫r(shí)具有左右多邊形的弧段刪除掉，即可實(shí)現(xiàn)拓?fù)溧徑ㄖ锏暮喜ⅰ?/p>

另外一種是對(duì)視覺(jué)鄰近的建筑物合并。視覺(jué)鄰近是指原始建筑物之間的距離較小，當(dāng)比例尺變換為某一更小尺度下時(shí)，它們之間的距離看上去也會(huì)隨之變得更小。有時(shí)在地圖圖面上無(wú)法觀察到，出現(xiàn)建筑物部分重疊的沖突現(xiàn)象。這種情況下，需要填充建筑物之間的縫隙，使建筑物合并為一個(gè)整體從而消除空間沖突。本文主要研究視覺(jué)鄰近建筑物的合并。

圖1　建筑物合并Fig.1　Building aggregation

1.2C-Delaunay三角網(wǎng)

Delaunay三角網(wǎng)是對(duì)空間的一種特殊剖分，具備多種優(yōu)異特性：如鄰近性、最優(yōu)性、區(qū)域性、凸多邊形性等。C-Delaunay是在構(gòu)建三角網(wǎng)的過(guò)程中，要求指定的邊必須作為三角形的邊存在，不能夠被穿越。由于實(shí)際生產(chǎn)中的線、面數(shù)據(jù)也隱含著邊界不被穿越的要求，使用C-Delaunay三角網(wǎng)對(duì)空間的劃分更加理想，在實(shí)際生產(chǎn)活動(dòng)中的應(yīng)用也更廣泛[14]。圖2(a)、(b)分別是用建筑物構(gòu)建的Delaunay三角網(wǎng)和C-Delaunay三角網(wǎng)，后者保留了建筑物的邊線信息更合理。

圖2　建筑物構(gòu)建的三角網(wǎng)Fig 2　Triangulation built with buildings

1.3基于C-Delaunay的建筑物合并

三角網(wǎng)的優(yōu)良性質(zhì)對(duì)于建筑物面合并是非常重要的。使用建筑物面建立C-Delaunay，得到的三角網(wǎng)邊界輪廓為一個(gè)凸多邊形，包含所有建筑物。三角形單元遍布了整個(gè)數(shù)據(jù)區(qū)域，實(shí)現(xiàn)無(wú)重疊、無(wú)縫隙的覆蓋。相互連接的三角形很好地表達(dá)了空間對(duì)象間的鄰近特性，本文將其應(yīng)用在對(duì)需要合并建筑物對(duì)象的定性探測(cè)上。

如前所述，當(dāng)?shù)貓D比例尺發(fā)生變化時(shí)(縮小時(shí))，要對(duì)距離較近的建筑物之間的空隙進(jìn)行填充。在這一過(guò)程中，三角網(wǎng)可以精確地描述數(shù)據(jù)表達(dá)的目標(biāo)邊界，且容易進(jìn)行長(zhǎng)度、面積等幾何計(jì)算。本文將三角網(wǎng)的這個(gè)優(yōu)勢(shì)應(yīng)用在對(duì)合并過(guò)程的定量控制上。通過(guò)大量研究，本文提出了三角形形態(tài)的6種度量特征，依此對(duì)三角形進(jìn)行過(guò)濾，進(jìn)而自動(dòng)獲得橋接多邊形，實(shí)現(xiàn)建筑物的合并。6種特征具體如下。

1.3.1位置特征

考量三角形內(nèi)心在建筑物面內(nèi)部或外部。三角形的內(nèi)心點(diǎn)一定在其內(nèi)部，可以代表其位置。合并過(guò)程中關(guān)注的是位于面外的三角形。因此對(duì)三角形逐一取內(nèi)心點(diǎn)，判斷是否位于建筑物幾何面內(nèi)。

1.3.2屬性特征

考量三角形3個(gè)頂點(diǎn)連接的建筑物個(gè)數(shù)。三角形每個(gè)頂點(diǎn)至少關(guān)聯(lián)一個(gè)建筑物。對(duì)每個(gè)頂點(diǎn)賦予其關(guān)聯(lián)的建筑物面要素的唯一ID。依據(jù)頂點(diǎn)ID的情況，三角形可以分為3類：①Ⅰ類三角形：只連接一個(gè)建筑物面；②Ⅱ類三角形：連接兩個(gè)建筑物面；③Ⅲ類三角形：連接3個(gè)建筑物面的。

當(dāng)建筑物面共邊時(shí)，需要預(yù)先進(jìn)行合并；當(dāng)不同的建筑物僅僅相交于一個(gè)點(diǎn)時(shí)，點(diǎn)的ID值選擇存在二義性，這時(shí)取任一ID，同時(shí)作特殊標(biāo)記。

1.3.3關(guān)聯(lián)特征

考量鄰接三角形的個(gè)數(shù)。三角形通過(guò)邊關(guān)聯(lián)的情況可以分為4種：①A類三角形：僅有一個(gè)邊關(guān)聯(lián)；②B類三角形：有兩條邊關(guān)聯(lián)三角形；③C類三角形：3條邊都有關(guān)聯(lián)三角形；④孤立的三角形。

在對(duì)三角網(wǎng)進(jìn)行過(guò)濾過(guò)程中，當(dāng)對(duì)不符合要求的三角形作了特殊標(biāo)記后，關(guān)聯(lián)規(guī)則可以變形為另一種形式，同時(shí)需要考慮所關(guān)聯(lián)的三角形的標(biāo)記狀態(tài)或所屬的保留集合。

1.3.4高度特征

考量三角形的高度。單個(gè)三角形高度規(guī)則如下：Ⅰ類三角形存在兩頂點(diǎn)是建筑物邊線上緊相鄰的兩點(diǎn)時(shí)，取此邊上的高，否則取任意一個(gè)邊上的高；Ⅱ類三角形取ID值相同兩頂點(diǎn)組成的邊上的高；Ⅲ類三角形取3邊高度平均值。對(duì)于三角形集合，取所有或部分三角形的平均高度。當(dāng)三角形的個(gè)數(shù)不足個(gè)數(shù)閾值時(shí)，取所有三角形的平均高；否則，排除最大和最小的1/5高度值，對(duì)剩余的求平均值，以排除極值情況。

1.3.5角度特征

考量三角形是銳角還是鈍角。在三角網(wǎng)的邊界部分會(huì)出現(xiàn)狹長(zhǎng)的鈍角三角形，關(guān)聯(lián)的是距離較遠(yuǎn)的建筑物，通過(guò)角度規(guī)則可以過(guò)濾掉。

1.3.6邊長(zhǎng)特征

考量三角形邊的平均長(zhǎng)度。連接距離較近建筑物的三角形平均邊長(zhǎng)較小；而連接距離較遠(yuǎn)建筑物的三角形平均邊比較大，通過(guò)邊長(zhǎng)規(guī)則可以過(guò)濾掉。

2　合并方法

2.1合并過(guò)程

本文通過(guò)對(duì)大量、多尺度、多地區(qū)現(xiàn)實(shí)數(shù)據(jù)的分析及試驗(yàn)，提出如圖3所示的合并過(guò)程。

2.2合并方法

2.2.1加密數(shù)據(jù)，建立C-Delaunay三角網(wǎng)

(1) 確定加密閾值，對(duì)建筑物數(shù)據(jù)進(jìn)行加密。借助三角網(wǎng)進(jìn)行建筑物面的合并時(shí)，三角網(wǎng)是探測(cè)建筑物面鄰近關(guān)系以及進(jìn)行連接的關(guān)鍵所在。為了使三角形保持良好的幾何形態(tài)，加密建筑物面的邊線是非常重要的一步。加密閾值的選擇需要綜合考慮建筑物之間的距離和目標(biāo)比例尺的大小。閾值過(guò)小會(huì)造成加密點(diǎn)冗余，降低處理效率。閾值過(guò)大不能保證三角網(wǎng)的良好形態(tài)。假設(shè)加密閾值為L(zhǎng)，要加密線的長(zhǎng)度為l，本文設(shè)計(jì)的加密算法如圖4所示。

(2) 建立約束Delaunay三角網(wǎng)。使用加密后的點(diǎn)集，以建筑物邊為限制邊條件，建立約束Delaunay三角網(wǎng)的方法已經(jīng)有很多研究，這里不再贅述。

圖3　建筑物合并流程Fig.3　Blueprint for building aggregation

圖4　邊線數(shù)據(jù)加密算法流程Fig.4　Densification algorithm flow chart

2.2.2根據(jù)6種度量參數(shù)對(duì)三角形進(jìn)行過(guò)濾操作

過(guò)濾操作的主要步驟如下：

(1) 位置特征過(guò)濾。排除建筑物面內(nèi)的三角形，保留面外的。

(2) 屬性特征過(guò)濾。排除3邊均不是或只有一條是建筑物邊的Ⅰ類三角形，保留Ⅱ類三角形，預(yù)留兩邊是建筑物邊的Ⅰ類三角形和Ⅲ類三角形以備修復(fù)。

(3) 邊長(zhǎng)特征過(guò)濾。排除平均邊長(zhǎng)大于閾值的三角形，保留平均邊長(zhǎng)小于閾值的三角形。

(4) 角度特征過(guò)濾。保留鈍角對(duì)邊是建筑物邊的鈍角三角形，預(yù)留其余的鈍角三角形以備修復(fù)；保留包含建筑物邊界邊的銳角三角形，預(yù)留不含邊界邊的銳角Ⅱ類三角形以備修復(fù)。

(5) 修復(fù)預(yù)留的鈍角三角形。當(dāng)鈍角三角形存在兩條非建筑物邊，且他們關(guān)聯(lián)的三角形處于保留狀態(tài)時(shí)，把該三角形放回保留集。

(6) 高度特征過(guò)濾。對(duì)保留集中的三角形聚類，計(jì)算每一個(gè)三角形分組的平均高度，排除大于閾值的三角形集合，保留小于閾值的三角形集合。

(7) 修復(fù)預(yù)留的Ⅰ、Ⅱ、Ⅲ類三角形?？剂款A(yù)留Ⅱ、Ⅲ類三角形標(biāo)記狀態(tài)下的關(guān)聯(lián)特征，若屬于B類三角形則放回保留集?？紤]預(yù)留的Ⅰ類三角形的非建筑物邊是否關(guān)聯(lián)了保留狀態(tài)的三角形，若是則放回保留集。

圖5中星狀標(biāo)記的三角形展示了幾種修復(fù)的情況。圖(a)中的Ⅲ類三角形，3邊關(guān)聯(lián)的三角形都是保留狀態(tài)。圖(b)中的Ⅰ類三角形，頂點(diǎn)是同一邊線上的連續(xù)3點(diǎn)且唯一的關(guān)聯(lián)三角形是保留狀態(tài)。圖(c)中的鈍角三角形，兩邊關(guān)聯(lián)的三角形是保留狀態(tài)。

對(duì)過(guò)濾操作的結(jié)果有兩種形式表示：一是用集合分別存儲(chǔ)排除和保留的三角形；二是對(duì)三角形作標(biāo)記，true表示保留，false表示排除。標(biāo)記的方式可以快速查詢?nèi)切蔚呐懦Ａ魻顟B(tài)，而集合的方式能快速確定每一步過(guò)濾操作的對(duì)象?？紤]到具體應(yīng)用的需求，本文采用兩種方式結(jié)合的方法。

2.2.3自動(dòng)提取、直角化橋接多邊形

對(duì)過(guò)濾結(jié)果進(jìn)行分堆，求出外邊界形成橋接部分。分堆結(jié)果為一個(gè)三角形的是無(wú)效部分。定義如下符號(hào)：R-保留三角形集合；S-已處理三角形集合；E-當(dāng)前橋接邊界邊集合；T-當(dāng)前種子三角形集合；seedTri-當(dāng)前種子三角形；提取橋接多邊形的過(guò)程如下：①得到2.2.2中過(guò)濾操作得到的保留三角形集合R；②判斷R中的三角形是否都已經(jīng)處理過(guò)，如果都處理過(guò)進(jìn)入步驟⑥，否則取R中任一未處理過(guò)的三角形放入到T中，進(jìn)入步驟③；③從T中移出一個(gè)三角形，作為seedTri放入S中，取seedTri三邊關(guān)聯(lián)的三角形，進(jìn)入步驟④，當(dāng)T為空時(shí)，進(jìn)入步驟⑤；④如果seedTri的邊沒(méi)有關(guān)聯(lián)三角形或者關(guān)聯(lián)的三角形不屬于R時(shí)，將這個(gè)邊放入到E中，如果三邊關(guān)聯(lián)的三角形都已處理過(guò)時(shí)返回步驟③，否則將未處理過(guò)的關(guān)聯(lián)三角形放入到T中返回步驟③；⑤對(duì)E中的邊，按照點(diǎn)的關(guān)聯(lián)關(guān)系進(jìn)行連接，即為一個(gè)橋接多邊形的外輪廓，完成一個(gè)橋接多邊形的搜索，清空E，返回步驟②；⑥確定最后一個(gè)橋接多邊形的輪廓，結(jié)束搜索，即得到所有的橋接多邊形。

橋接多邊形由三角形得到，難以保證結(jié)果的直角化特征。目前有少數(shù)文獻(xiàn)[20-21]對(duì)建筑物進(jìn)行直角化處理，本文通過(guò)對(duì)橋接部分進(jìn)行處理來(lái)維持直角化特征?；驹砣缦拢旱玫降臉蚪硬糠值妮喞吘€有兩種：一種是和建筑物的公共邊，是原始建筑物邊線的一部分；另一種是連接視覺(jué)鄰近的建筑物的非公共邊，直角化調(diào)整的是后者。根據(jù)左右三角形的位置屬性特征區(qū)分公共邊和非公共邊；非公共邊的兩端點(diǎn)分別與兩條公共邊相連接，過(guò)一個(gè)端點(diǎn)可向另一端點(diǎn)關(guān)聯(lián)的公共邊作垂線，如果垂點(diǎn)在公共邊上，則稱該端點(diǎn)為短頂點(diǎn)，另一端點(diǎn)為長(zhǎng)頂點(diǎn)。直角化處理：①對(duì)橋接部分Q，根據(jù)兩側(cè)三角形的位置屬性特征，識(shí)別出它的非公共邊L；②確定L的長(zhǎng)頂點(diǎn)N1、短頂點(diǎn)N2，過(guò)N2向N1關(guān)聯(lián)的公共邊作垂線，計(jì)算垂點(diǎn)P位置；③確定N1、N2與P所形成的邊角三角形T；④從橋接部分Q中切除T。如圖6所示，圖(a)是未直角化的橋接部分，圖(b)是直角化后的橋接部分。

2.2.4合并橋接部分和建筑物

通過(guò)相鄰關(guān)系進(jìn)行聚類，自動(dòng)識(shí)別關(guān)聯(lián)在一起的建筑物面和橋接面。對(duì)每一組聚類結(jié)果進(jìn)行拓?fù)溧徑喜ⅰ＞垲愡^(guò)程中保留原始建筑物的ID信息，這樣能夠通過(guò)一定的準(zhǔn)則，來(lái)維護(hù)合并后結(jié)果建筑物的屬性，如保留面積最大或者周長(zhǎng)最長(zhǎng)建筑物的屬性。

圖6　直角化處理Fig.6　Rectangularity of bridge polygon

3　試驗(yàn)與分析

本文在NewMapWJ-Ⅲ地圖工作站底層開(kāi)發(fā)接口的支撐下，使用C、C++語(yǔ)言進(jìn)行二次開(kāi)發(fā)，生成了相關(guān)程序模塊。對(duì)多樣性的數(shù)據(jù)進(jìn)行試驗(yàn)，實(shí)現(xiàn)了基于C-Delaunay三角網(wǎng)分類的建筑物自動(dòng)化合并處理，驗(yàn)證了本文所提方法的正確性和實(shí)用性。

3.1試驗(yàn)平臺(tái)和數(shù)據(jù)

試驗(yàn)采用的計(jì)算機(jī)配置為：操作系統(tǒng)為Windows7(x64)，CPU為I7-3770型號(hào)，主頻是3.2GHz，內(nèi)存16GB，固態(tài)硬盤(pán)1024GB。試驗(yàn)數(shù)據(jù)樣本有兩個(gè)，試驗(yàn)區(qū)1是成都市60km2(中心城區(qū))、原始比例尺為1∶2000數(shù)據(jù)，將其合并綜合至1∶5000和1∶1萬(wàn)比例尺。試驗(yàn)區(qū)2是邯鄲市30km2(含城區(qū)和農(nóng)村地區(qū))、原始比例尺為1∶500數(shù)據(jù)，將其合并綜合至1∶5000和1∶1萬(wàn)比例尺。

3.2結(jié)果分析

圖7顯示的是部分試驗(yàn)結(jié)果：圖(a)為原始數(shù)據(jù)，圖(b)為合并結(jié)果。從合并結(jié)果中可以看出空間鄰近多邊形得到了合理的合并并保持了直角化特征；此外，還進(jìn)行了一組對(duì)比試驗(yàn)：圖(c)是原始建筑物；圖(d)是使用傳統(tǒng)三角網(wǎng)方式進(jìn)行合并的結(jié)果；圖(e)是使用文獻(xiàn)[22]中緩沖區(qū)方法得到的結(jié)果；圖(f)是使用本文方法合并并直角化后得到的結(jié)果。通過(guò)對(duì)比可以看出，圖(d)、(e)雖然能正確識(shí)別出建筑物的鄰近關(guān)系并進(jìn)行合并，但是并不能保持建筑物的直角化特征。

另外，本文還對(duì)實(shí)現(xiàn)方法的效率進(jìn)行了測(cè)試分析，如表1所示。試驗(yàn)1—4統(tǒng)計(jì)的是自動(dòng)化合并所需要的時(shí)間。試驗(yàn)5—6由于數(shù)據(jù)保密性等原因，統(tǒng)計(jì)的是建筑物綜合處理(合并、選取、化簡(jiǎn))的時(shí)間。從圖中可以看出：建筑物自動(dòng)化合并的時(shí)間遠(yuǎn)遠(yuǎn)短于人工處理的時(shí)間，能夠滿足實(shí)際生產(chǎn)的需要；同時(shí)也發(fā)現(xiàn)，試驗(yàn)1—2使用的是形狀規(guī)則、分布整齊是城區(qū)。試驗(yàn)3—4是形狀破碎的農(nóng)村數(shù)據(jù)，因此。試驗(yàn)3—4消耗的時(shí)間是不與其數(shù)據(jù)范圍成比例的。即自動(dòng)合并的時(shí)間和數(shù)據(jù)范圍、數(shù)據(jù)的具體情況、比例尺等都有密切關(guān)系。

圖7　合并效果對(duì)比圖Fig.7　Comparison chart

試驗(yàn)序號(hào)數(shù)據(jù)范圍/km2原始比例尺目標(biāo)比例尺運(yùn)行時(shí)間備注161∶5001∶500015.37s自動(dòng)合并261∶5001∶1000020.08s自動(dòng)合并3361∶5001∶5000200.27s自動(dòng)合并4361∶5001∶10000241.22s自動(dòng)合并56511∶20001∶50004.5h自動(dòng)綜合66511∶20001∶100007.5h自動(dòng)綜合

4　結(jié)　論

建筑物的合并綜合本質(zhì)包含兩個(gè)子過(guò)程：一是鄰近關(guān)系識(shí)別，確定哪些建筑物應(yīng)該合并在一起；二是對(duì)確定了鄰近關(guān)系的建筑物實(shí)施合并操作。三角網(wǎng)結(jié)構(gòu)在表達(dá)空間對(duì)象鄰近關(guān)系時(shí)具有定性、定量的優(yōu)勢(shì)：既可以確定建筑物是否相鄰，又可以通過(guò)對(duì)網(wǎng)中三角形的分析、量測(cè)和計(jì)算確定相鄰的具體情況。通過(guò)對(duì)多樣性真實(shí)數(shù)據(jù)的試驗(yàn)和分析，證明合并結(jié)果合理，效率能夠滿足生產(chǎn)實(shí)踐的要求。該方法已應(yīng)用于多個(gè)城市的數(shù)據(jù)縮編項(xiàng)目中，并取得了良好的效果。

基于三角網(wǎng)分類的建筑物合并操作是針對(duì)不同建筑物之間縫隙的填充，下一步的研究將是通過(guò)觀察建筑物外部自身凹陷部分三角形的特點(diǎn)，來(lái)建立一定的過(guò)濾規(guī)則，完成這一部分空隙的填充，實(shí)現(xiàn)建筑物合并和化簡(jiǎn)的一體化實(shí)現(xiàn)。

[1]王光霞, 楊培. 數(shù)學(xué)形態(tài)學(xué)在居民地街區(qū)合并中的應(yīng)用[J]. 測(cè)繪學(xué)院學(xué)報(bào), 2000, 17(3): 201-206.

WANGGuangxia,YANGPei.ApplicationofMathematicMorphologyinUnitingBlocksofResidentialArea[J].JournalofInstituteofSurveyingandMapping, 2000, 17(3): 201-206.

[2]王輝連, 武芳, 張琳琳, 等. 數(shù)學(xué)形態(tài)學(xué)和模式識(shí)別在建筑物多邊形化簡(jiǎn)中的應(yīng)用[J]. 測(cè)繪學(xué)報(bào), 2005, 34(3): 269-276.

WANGHuilian,WUFang,ZHANGLinlin,etal.TheApplicationofMathematicalMorphologyandPatternRecognitiontoBuildingPolygonSimplification[J].ActaGeodaeticaetCartographicaSinica, 2005, 34(3): 269-276.

[3]郭仁忠, 艾廷華. 制圖綜合中建筑物多邊形的合并與化簡(jiǎn)[J]. 武漢測(cè)繪科技大學(xué)學(xué)報(bào), 2000, 25(1): 25-30.

GUORenzhong,AITinghua.SimplificationandAggregationofBuildingPolygoninAutomaticMapGeneralization[J].JournalofWuhanTechnicalUniversityofSurveyingandMapping, 2000, 25(1): 25-30.

[4]郭建忠, 謝明霞, 李柱林. 基于線緩沖區(qū)分析的街區(qū)合并方法[J]. 地理與地理信息科學(xué), 2011, 27(6): 111-112.

GUOJianzhong,XIEMingxia,LIZhulin.BlockAggregationBasedonLineBufferAnalysis[J].GeographyandGeo-InformationScience, 2011, 27(6): 111-112.

[5]何宇兵. 地學(xué)制圖綜合中多邊形對(duì)象的合并算法研究與應(yīng)用[D]. 杭州: 浙江大學(xué), 2007.HEYubing.StudyandApplicationofAlgorithmforPolygonAggregationinGeo-CartographicGeneralization[D].Hangzhou:ZhejiangUniversity, 2007.

[6]齊琳.D-TIN并行構(gòu)建方法及其在地圖綜合中的應(yīng)用研究[D]. 南京: 南京師范大學(xué), 2011.

QILin.DelaunayTriangulationParallelConstructionMethodandItsApplicationinMapGeneralization[D].Nanjing:NanjingNormalUniversity, 2011.

[7]張巧鳳. 應(yīng)用Delaunay三角網(wǎng)進(jìn)行城市居民地和路網(wǎng)自動(dòng)綜合理論和方法研究[D]. 太原: 太原理工大學(xué), 2005.

ZHANGQiaofeng.TheMethodandTheoryResearchonAutomatedMapGeneralizationofCitySettlementandRoadNetworkApplyingDelaunayTriangulationNetwork[D].Taiyuan:TaiyuanUniversityofTechnology, 2005.

[8]REGNAULDN.SpatialStructurestoSupportAutomaticGeneralisation[C]∥Proceedingsofthe22ndInternationalCartographicConference.ACorua: [s.n.], 2005.

[9]艾廷華.Delaunay三角網(wǎng)支持下的空間場(chǎng)表達(dá)[J]. 測(cè)繪學(xué)報(bào), 2006, 35(1): 71-76

AITinghua.ASpatialFieldRepresentationModelBasedonDelaunayTriangulation[J].ActaGeodaeticaetCartographicaSinica, 2006, 35(1): 71-76, 82.

[10]艾廷華, 郭仁忠. 支持地圖綜合的面狀目標(biāo)約束Delaunay三角網(wǎng)剖分[J]. 武漢測(cè)繪科技大學(xué)學(xué)報(bào), 2000, 25(1): 35-41.

AITinghua,GUORenzhong.AConstrainedDelaunayPartitioningofArealObjectstoSupportMapGeneralization[J].JournalofWuhanTechnicalUniversityofSurveyingandMapping, 2000, 25(1): 35-41.

[11]艾廷華, 郭仁忠, 陳曉東.Delaunay三角網(wǎng)支持下的多邊形化簡(jiǎn)與合并[J]. 中國(guó)圖象圖形學(xué)報(bào), 2001, 6(7): 703-709.

AITinghua,GUORenzhong,CHENXiaodong.SimplificationandAggregationofPolygonObjectSupportedbyDelaunayTriangulationStructure[J].JournalofImageandGraphics, 2001, 6(7): 703-709.

[12]JONESCB,WAREJM.ProximitySearchwithaTriangulatedSpatialModel[J].TheComputerJournal, 1998, 41(2): 71-83.

[13]JONESCB,WAREJM,EYNONCD.TriangulatedSpatialModelsandNeighbourhoodSearch:AnExperimentalComparisonwithQuadtrees[J].TheVisualComputer, 1999, 15(5): 235-248.

[14]童小華, 熊國(guó)鋒. 建筑物多邊形的多尺度合并化簡(jiǎn)與平差處理[J]. 同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2007, 35(6): 824-829.

TONGXiaohua,XIONGGuofeng.Aggregation,SimplificationandAdjustmentofBuildingPolygonObjectsinMulti-scaleMapGeneralization[J].JournalofTongjiUniversity(NaturalScience), 2007, 35(6): 824-829.

[15]黃繼風(fēng). 基于Delaunay三角網(wǎng)的城市多邊形合并算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2004, 25(7): 1220-1222.

HUANGJifeng.UrbanPolygonAggregationAlgorithmsBasedonDelaunayTrigonometryNetwork[J].ComputerEngineeringandDesign, 2004, 25(7): 1220-1222.

[16]LIZ,YANH,AIT,etal.AutomatedBuildingGeneralizationBasedonUrbanMorphologyandGestaltTheory[J].InternationalJournalofGeographicalInformationScience, 2004, 18(5): 513-534.

[17]YANHaowen,WEIBELR,YANGBisheng.AMulti-parameterApproachtoAutomatedBuildingGroupingandGeneralization[J].Geoinformatica, 2008, 12(1): 73-89.

[18]錢海忠, 武芳, 譚笑, 等. 基于ABTM的城市建筑物合并算法[J]. 中國(guó)圖象圖形學(xué)報(bào), 2005, 10(10): 1224-1233.

QIANHaizhong,WUFang,TANXiao,etal.TheAlgorithmforMergingCityBuildingsBasedonABTM[J].JournalofImageandGraphics, 2005, 10(10): 1224-1233.

[19]邵春麗, 胡鵬, 黃承義, 等.DELAUNAY三角網(wǎng)的算法詳述及其應(yīng)用發(fā)展前景[J]. 測(cè)繪科學(xué), 2004, 29(6): 68-71.

SHAOChunli,HUPeng,HUANGChengyi.TheExpatiationofDelaunayAlgorithmsandaPromisingDirectioninApplication[J].ScienceofSurveyingandMapping, 2004, 29(6): 68-71.

[20]劉鵬程, 艾廷華, 鄧吉芳. 基于最小二乘的建筑物多邊形的化簡(jiǎn)與直角化[J]. 中國(guó)礦業(yè)大學(xué)學(xué)報(bào), 2008, 37(5): 699-704.LIUPengcheng,AITinghua,DENGJifang.SimplificationandRectangularityofBuilding-polygonBasedonLeastSquaresAdjustment[J].JournalofChinaUniversityofMining&Technology, 2008, 37(5): 699-704.

[21]劉鵬程, 艾廷華, 胡晉山. 一種基于條件極值的建筑多邊形直角化的方法[J]. 測(cè)繪與空間地理信息, 2008, 31(5): 12-14, 18.LIUPengcheng,AITinghua,HUJinshan.RectangularityofBuildingPolygonBasedonCondition-Extremum[J].Geomatics&SpatialInformationTechnology, 2008, 31(5): 12-14, 18.

[22]BADERM,WEIBELR.DetectingandResolvingSizeandProximityConflictsintheGeneralizationofPolygonalMaps[C]∥Proceedingsofthe18thInternationalCartographicConference.Stockholm: [s.n.], 1997.

(責(zé)任編輯：宋啟凡)

修回日期： 2016-05-23

E-mail：guopeipei925@163.com

ClassificationandFilteringofConstrainedDelaunayTriangulationforAutomatedBuildingAggregation

GUOPeipei1,2,LIChengming2,YINYong2

1.CollegeofGeomatics,ShandongUniversityofScienceandTechnology,Qingdao266590,China; 2.InstituteofGIS,ChineseAcademyofSurveyingandMapping,Beijing100830,China

Buildingaggregationisanimportantpartofresearchonlargescalemapgeneralization.Atriangulationbasedapproachisproposedfromtheperspectiveofshapefeatures,sixmeasureparametersoftrianglesinaconstrainedDelaunaytriangulationareproposed.Firstofall,usethesixmeasureparameterstodeterminewhichtrianglesareretainedandwhichareerased.Then,thecontoursofretainedtriangles,asbridgeareasbetweenbuildings,areautomaticallyidentifiedandrightangleprocessed.Andthen,thebuildingsareaggregatedwithrightanglefeatureretainedbymergingthebridgeareaswithconnectingbuildings.Finally,theapproachisverifiedbybeingcarriedoutonactualdata.Experimentalresultshowsthatitisefficientandpractical.

mapgeneralization;buildingaggregation;constrainedDelaunaytriangulation;rectangularity

GUOPeipei(1986—),female,PhDcandidate，majorsinautomatedmapgeneralizationanddatamining.

P208

A

1001-1595(2016)08-1001-07

國(guó)家科技支撐計(jì)劃(2015BAJ06B01)；測(cè)繪地理信息公益性行業(yè)科研專項(xiàng)(201412003)；中國(guó)測(cè)繪科學(xué)研究院基本科研業(yè)務(wù)費(fèi)(7771530)

2015-11-20

郭沛沛(1986—)，女，博士生，研究方向?yàn)樽詣?dòng)化制圖綜合和空間數(shù)據(jù)處理與挖掘。

引文格式：郭沛沛，李成名，殷勇.建筑物合并的Delaunay三角網(wǎng)分類過(guò)濾法[J].測(cè)繪學(xué)報(bào)，2016,45(8)：1001-1007.DOI:10.11947/j.AGCS.2016.20150587.

GUOPeipei,LIChengming,YINYong.ClassificationandFilteringofConstrainedDelaunayTriangulationforAutomatedBuildingAggregation[J].ActaGeodaeticaetCartographicaSinica,2016,45(8):1001-1007.DOI:10.11947/j.AGCS.2016.20150587.