基于頂點(diǎn)線性插值的建筑物群聚合的簡(jiǎn)易方法

黃玉蘭，郭慶勝＊,王慧慧,王 勇

（1.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079 2.中國(guó)測(cè)繪科學(xué)研究院，北京 100830）

建筑物群作為城市地圖中的核心要素，對(duì)地圖表達(dá)的效果具有重要影響[1]。建筑物群的自動(dòng)聚合是制圖綜合的難點(diǎn)之一，國(guó)內(nèi)外諸多學(xué)者對(duì)建筑物群聚合方法進(jìn)行了大量研究[2-26]?；谙嚓P(guān)研究，本文提出了基于頂點(diǎn)線性插值的建筑物群聚合的簡(jiǎn)易方法：首先利用最短鄰近連線獲取建筑群鄰近關(guān)系，然后通過(guò)對(duì)這些連線的分析、量測(cè)和計(jì)算準(zhǔn)確獲取相鄰建筑物的聚合部分，最后采用漸進(jìn)式方法實(shí)現(xiàn)建筑物群聚合。該方法還能處理建筑物群的多邊形存在相交和重疊空間拓?fù)潢P(guān)系的聚合問(wèn)題。此外，本文利用道路網(wǎng)將建筑物群劃分到不同區(qū)域后進(jìn)行聚合，既維持了建筑物的空間分布特征，又能提高算法效率。

1 建筑物群的空間鄰近關(guān)系

空間鄰近關(guān)系是尋找鄰近建筑物進(jìn)行聚合的重要依據(jù)，獲取的鄰近關(guān)系不同，則對(duì)應(yīng)的聚合結(jié)果也會(huì)有所不同。根據(jù)建筑物輪廓線可以構(gòu)建約束性Delaunay三角網(wǎng)（contrained delaunay triangulation,CDT），然后獲取建筑物群的空間鄰近關(guān)系，但該方法會(huì)疏漏一些建筑物之間的空間鄰近關(guān)系。例如，針對(duì)圖1a中的建筑物群建立CDT并得到相應(yīng)的空間鄰近圖，如圖1b所示，此時(shí)未探測(cè)到建筑物B1與B2及B1與B3之間的空間鄰近關(guān)系。對(duì)此已有學(xué)者進(jìn)行了研究，如文獻(xiàn)[23]綜合考慮多個(gè)影響建筑物群聚的因子，可獲取B1與B2及B1與B3之間的空間鄰近關(guān)系，但未討論如何量測(cè)和計(jì)算B1與B2及B1與B3之間的具體相鄰情況。

加密插值建筑物輪廓線上的頂點(diǎn)后，構(gòu)建的建筑物間的CDT和建筑物群的空間鄰近圖分別如圖2a和圖2b所示。對(duì)比圖1和圖2可知，等間距加密建筑物輪廓線頂點(diǎn)后，能更準(zhǔn)確地探測(cè)到建筑物B1與B2及B1與B3之間的空間鄰近關(guān)系，且相鄰建筑物間的空間可由三角形填充。

圖1 基于CDT的空間鄰近關(guān)系

圖2 加密頂點(diǎn)后的空間鄰近關(guān)系

2 搜尋最短鄰近連線

建筑物輪廓線頂點(diǎn)加密后，相鄰2個(gè)建筑物的聚合就有一個(gè)直觀的理解：相鄰建筑物的聚合部分就應(yīng)該是長(zhǎng)度小于閾值的最短距離頂點(diǎn)連線的組合。因此，從一個(gè)建筑物輪廓線上的一個(gè)頂點(diǎn)到相鄰的另一個(gè)建筑物輪廓線上最鄰近的點(diǎn)之間的連線就非常重要，這里稱(chēng)之為“最短鄰近連線”。設(shè)a是建筑物A的一個(gè)頂點(diǎn)，b是建筑物B的一個(gè)頂點(diǎn)，A與B之間是鄰近關(guān)系，若從a到建筑物B的某個(gè)頂點(diǎn)之間距離最小時(shí)，建筑物B的這個(gè)頂點(diǎn)是b，那么從a到b的連線就是“建筑物A的頂點(diǎn)a到建筑物B的最短鄰近連線”。最短鄰近連線具有以下特性：

1）dist(a,b)＜dist(a,c),a∈A,b∈B,c∈B,b≠c

2）line(a,b)∩A=?

3）line(a,b)∩B=?

式中，c表示建筑物B上除b之外的任意頂點(diǎn)；dist表示2個(gè)頂點(diǎn)之間的距離；line表示2個(gè)頂點(diǎn)之間的連線（不包括a和b）。

基于最短鄰近連線的特性就可以構(gòu)建最短鄰近連線網(wǎng)，利用長(zhǎng)度小于閾值的最短鄰近連線的組合就能確定相鄰建筑物的聚合部分。

2.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理包括插入交點(diǎn)和通過(guò)插值加密建筑物輪廓線頂點(diǎn)2部分。由于數(shù)據(jù)誤差，建筑物之間有可能相交，在這些交點(diǎn)處存在長(zhǎng)度為零的特殊最短鄰近連線，所以構(gòu)建最短鄰近連線前需插入交點(diǎn)。在建筑物群聚合時(shí)，長(zhǎng)度小于閾值的最短鄰近連線就表示了建筑物群的聚合之處。因此，為了提高建筑物群聚合效果，必須對(duì)建筑物輪廓線的頂點(diǎn)加密。處理后的建筑物輪廓點(diǎn)序號(hào)在外環(huán)中按順時(shí)針?lè)较蚪M織，內(nèi)環(huán)中按逆時(shí)針?lè)较蚪M織。

2.2 過(guò)濾條件

最短鄰近連線網(wǎng)可以準(zhǔn)確描述建筑物群的鄰近關(guān)系，且容易進(jìn)行長(zhǎng)度、角度等幾何計(jì)算。本文在建立建筑物的一個(gè)輪廓點(diǎn)與其所有鄰近點(diǎn)之間的鄰近連線后，使用位置、屬性、長(zhǎng)度和角度4個(gè)特征度量進(jìn)行條件過(guò)濾，排除不滿足聚合要求的連線。具體判斷條件如下：

1）屬性的過(guò)濾條件。鄰近連線的端點(diǎn)至少關(guān)聯(lián)一個(gè)建筑物。依據(jù)端點(diǎn)關(guān)聯(lián)的建筑物ID，可以獲取連接相鄰的2個(gè)建筑物的連線。

2）位置的過(guò)濾條件。相離建筑物間的鄰近連線不應(yīng)穿過(guò)任何建筑物，而相交建筑物重疊區(qū)域的鄰近連線應(yīng)在2個(gè)建筑物內(nèi)部。利用鄰近連線的中點(diǎn)M，就可以判斷鄰近連線的位置。設(shè)S1和S2分別為2個(gè)建筑物的內(nèi)部區(qū)域，鄰近連線能保留下來(lái)的條件為：

3）角度的過(guò)濾條件。2個(gè)視覺(jué)鄰近的建筑物的待聚合輪廓線應(yīng)盡量平行，要求最短鄰近連線關(guān)聯(lián)的2條輪廓線的方位差小于設(shè)定的閾值（設(shè)為α）；聚合后的建筑物多邊形不應(yīng)該出現(xiàn)“尖銳角現(xiàn)象”，要求最短鄰近連線與關(guān)聯(lián)的每條輪廓邊之間的夾角大于設(shè)定的閾值（設(shè)為δ）。設(shè)line(Qi,Pj)為鄰近連線，Qi與Pj為輪廓線上點(diǎn)，如圖3所示，line(Qi,Pj)連接的待聚合邊為e1與e2，則鄰近連線能保留下來(lái)的條件為：

圖3 最短鄰近連線

4）長(zhǎng)度的過(guò)濾條件。經(jīng)上述過(guò)濾后保留的鄰近連線中長(zhǎng)度最短的即可作為當(dāng)前建筑物輪廓點(diǎn)的最短鄰近連線，長(zhǎng)度小于聚合距離閾值的最短鄰近連線即可用于后續(xù)建筑物群的聚合。此外，為了處理建筑物之間相交情況，本文定義建筑物相交區(qū)域內(nèi)部的最短鄰近連線的“長(zhǎng)度為負(fù)值”。

3 構(gòu)建聚合通道

相鄰的2個(gè)建筑物聚合時(shí)可能會(huì)出現(xiàn)在建筑物不同部位進(jìn)行聚合的情況，這些部位本文稱(chēng)之為“聚合通道”，每個(gè)“聚合通道”由一組最短鄰近連線組成，“聚合通道”的構(gòu)建就是搜尋到獨(dú)立成組的最短鄰近連線集合。

設(shè)2個(gè)鄰近建筑物（B1和B2）之間的最短鄰近連線集合已經(jīng)找到，若多條最短鄰近連線關(guān)聯(lián)的建筑物輪廓線頂點(diǎn)序號(hào)是連續(xù)且有序的，那么這個(gè)由多條最短鄰近連線就組成了一個(gè)“聚合通道”；否則，需分2種情況處理：

1）如圖4所示，建筑物B1上點(diǎn)Qx與Qk之間所有最短鄰近連線已經(jīng)被剔除，但點(diǎn)Qx與Qk之間這部分還是需要聚合，雖然點(diǎn)Qx與Qk的序號(hào)不連續(xù)，但是可直接組成一個(gè)“聚合通道”。

圖4 一個(gè)聚合通道

2）如圖5所示，建筑物B1上點(diǎn)Qx與Qk之間線段的長(zhǎng)度大于設(shè)定的閾值，并且與B2上對(duì)應(yīng)的輪廓線部分和關(guān)聯(lián)的兩條最短鄰近連線所圍成的區(qū)域比較大，其面積大于設(shè)定的閾值。此時(shí)，Qx與Qk之間需要分解，兩端單獨(dú)構(gòu)建“聚合通道”。

圖5 多個(gè)聚合通道

4 建筑物群的漸進(jìn)式聚合

4.1 漸進(jìn)式聚合原理

建筑物群漸進(jìn)式聚合的基本原理是基于最短鄰近連線獲取建筑群鄰近關(guān)系后，從2個(gè)鄰近建筑物的聚合開(kāi)始，在新的聚合建筑物生成后，刪除原來(lái)被聚合的2個(gè)建筑物；針對(duì)新建筑物和鄰近建筑物重新構(gòu)建最短鄰近連線，獲取“聚合通道”，隨后漸進(jìn)式地把新建筑物與鄰近建筑物聚合，直至該建筑物群全部聚合完成。

4.2 詳細(xì)算法

基于2個(gè)建筑物之間的“聚合通道”，就可以提取聚合后的新建筑物輪廓線。新建筑物輪廓線提取過(guò)程為：

1）如圖6所示，按照建筑物輪廓點(diǎn)序號(hào)升序獲取當(dāng)前點(diǎn)，若當(dāng)前頂點(diǎn)為“不可聚合的頂點(diǎn)”，則記錄當(dāng)前點(diǎn)并跟蹤下一點(diǎn)。

2）若為“可聚合的頂點(diǎn)Pk”（如圖6所示），需獲取點(diǎn)Pk對(duì)應(yīng)的最短鄰近連線，然后按照順時(shí)針?lè)较蜻x擇與線段PkPk-1的夾角最小的邊PkQj，并對(duì)點(diǎn)Qj所在建筑物的輪廓線頂點(diǎn)集合按照同樣的方法跟蹤，直至當(dāng)前點(diǎn)為最左邊點(diǎn)Si就可構(gòu)成封閉環(huán)，最后將所有構(gòu)成環(huán)的點(diǎn)移出集合R。

3）若2個(gè)建筑物之間只有一個(gè)“聚合通道”（圖6），至此即完成新建筑物輪廓線提取；若如圖6b所示，2個(gè)建筑物之間有多個(gè)“聚合通道”，則新建筑物存在內(nèi)環(huán)，需按照上述提取環(huán)方法繼續(xù)提取建筑物內(nèi)環(huán)，直至R集合中的點(diǎn)無(wú)法構(gòu)成環(huán)。

圖6 提取內(nèi)/外環(huán)

實(shí)現(xiàn)2個(gè)鄰近建筑物聚合后，就可以對(duì)一個(gè)建筑物群進(jìn)行聚合?；谧疃锑徑B線對(duì)建筑物群進(jìn)行漸進(jìn)式聚合具體步驟如下：

1）依據(jù)聚合距離閾值搜尋到一個(gè)建筑物子群。

2）判斷建筑物之間的相交情況，插入交點(diǎn)；根據(jù)設(shè)定的插值點(diǎn)距離閾值加密建筑物輪廓線的頂點(diǎn)。

3）獲取當(dāng)前需要聚合的2個(gè)鄰近建筑物，聚合后得到一個(gè)新建筑物B'。

4）更新建筑物群的空間鄰近關(guān)系圖，獲取新建筑物B'的一個(gè)鄰近建筑物，聚合得到新建筑物B''。漸進(jìn)式地把新建筑物與其鄰近建筑物聚合，直至當(dāng)前建筑物子群聚合完成。

5）搜尋下一個(gè)建筑物子群，回到步驟2）。若所有建筑物子群處理完時(shí)，該過(guò)程結(jié)束。

5 實(shí)驗(yàn)與分析

5.1 實(shí) 驗(yàn)1

實(shí)驗(yàn)1選取了湖北省武漢市部分區(qū)域的數(shù)據(jù)作為實(shí)驗(yàn)?zāi)繕?biāo)，其地圖比例尺為1:10 000。本文用Dot-Spatial+Visual Studio軟件，實(shí)現(xiàn)并驗(yàn)證算法。圖7 a是聚合前的原始建筑物數(shù)據(jù)。在本實(shí)驗(yàn)中，設(shè)插點(diǎn)間隔閾值變量為InterD，聚合距離閾值變量為d，刪除內(nèi)環(huán)面積閾值變量為Area，2個(gè)建筑物邊線的方位差閾值變量為α，去除建筑物尖角的角度閾值變量為δ，構(gòu)建聚合通道所設(shè)直線長(zhǎng)度、折線長(zhǎng)度和面積的閾值變量分別為L(zhǎng)1、L2、DelArea。長(zhǎng)度閾值的單位均為m，面積閾值的單位為m2。實(shí)驗(yàn)?zāi)繕?biāo)比例尺為1:100 000，根據(jù)國(guó)家地形圖標(biāo)準(zhǔn)，此時(shí)建筑物長(zhǎng)、寬和面積的最小尺寸分別為0.7 mm、0.5 mm、0.35 mm[27]，通過(guò)實(shí)驗(yàn)對(duì)比，將閾值設(shè)定為：α=30°，δ=5°，d=20，InterD=5，L1=60，L2=20，DelArea=400，Area=400。聚合結(jié)果如圖7b所示，均為合理。

圖7 建筑物群聚合前后對(duì)比圖

為了對(duì)比聚合效果，使用同樣的實(shí)驗(yàn)數(shù)據(jù)和參數(shù)設(shè)置，分別采用文獻(xiàn)[28]提出的CDT方法、ArcGIS（10.2）軟件中地圖綜合工具箱的多邊形綜合工具以及本文提出的方法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理。其中使用Arc-GIS的多邊形綜合方法時(shí)，勾選了保留直角化特征選項(xiàng)。選取了實(shí)驗(yàn)結(jié)果的局部區(qū)域進(jìn)行分析，圖8a為原始建筑物數(shù)據(jù)，圖8b、圖8c及圖8d的聚合距離閾值d均為2；圖8e、圖8f及圖8g的聚合距離閾值d均為20，其中橢圓框區(qū)域?yàn)橹攸c(diǎn)對(duì)比部分。對(duì)比實(shí)驗(yàn)的結(jié)果表明：

1)CDT方法用于小跨度的建筑物聚合時(shí)，可兼顧特征保持和避免鄰近探測(cè)疏漏；反之則易出現(xiàn)鄰近探測(cè)疏漏，產(chǎn)生圖8e所示不合理凹部。

2)ArcGIS聚合方法在聚合方向差異較大的建筑物時(shí)，“夸大”了局部區(qū)域，如圖8c所示。但是ArcGIS聚合方法用于大跨度的建筑物群聚合時(shí)，聚合結(jié)果相對(duì)合理，如圖8f所示。

3)基于最短鄰近連線的建筑物群漸進(jìn)式聚合方法受聚合跨度影響最小，聚合結(jié)果較為合理，具體如圖8d與圖8g所示。

圖8 不同聚合方法的實(shí)驗(yàn)效果對(duì)比

為了進(jìn)一步說(shuō)明本文所提方法的有效性，本文使用同樣的實(shí)驗(yàn)數(shù)據(jù)和參數(shù)設(shè)置，將3種方法對(duì)圖9a所示的原始建筑物群進(jìn)行聚合，其中使用ArcGIS的多邊形綜合方法時(shí)，勾選了保留直角化特征選項(xiàng)。圖9b為基于頂點(diǎn)線性插值的建筑物群漸進(jìn)式聚合結(jié)果。若使用CDT法進(jìn)行建筑物群聚合，如圖9c所示無(wú)法同時(shí)構(gòu)建B1與B4、B2與B3之間的連接三角形，導(dǎo)致B1與B4間無(wú)法基于連接三角形獲取聚合通道進(jìn)行聚合，聚合結(jié)果見(jiàn)圖9d；使用ArcGIS（10.2）軟件的聚合工具所得的結(jié)果見(jiàn)圖9e。從實(shí)驗(yàn)結(jié)果的比較可以看出，使用本文所提方法可以得到更理想的結(jié)果。

圖9 建筑物群聚合結(jié)果對(duì)比

5.2 實(shí) 驗(yàn)2

實(shí)驗(yàn)2選取了廣州市局部地區(qū)的建筑物數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，原始地圖比例尺為1:1 000，綜合后地圖比例尺為1:2 000。由于數(shù)據(jù)采集誤差，該區(qū)域原始數(shù)據(jù)中存在較多建筑物群相交的情況。圖10a為原始建筑物群，圖10b為使用本文所提方法聚合后的建筑物群。由圖10可知，本文提出的方法可以處理建筑物多邊形之間存在相交和重疊空間拓?fù)潢P(guān)系的建筑物群聚合問(wèn)題。

圖10 實(shí)驗(yàn)結(jié)果（局部）

使用同樣的參數(shù)，采用ArcGIS（10.2）軟件中地圖綜合工具箱的多邊形綜合（aggregate polygon）工具和文獻(xiàn)[28]提出的CDT方法對(duì)該實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理，勾選了保留直角化特征選項(xiàng)。使用ArcGIS（10.2）軟件的聚合工具所得的結(jié)果如圖10c所示，從結(jié)果可以看出ArcGIS（10.2）軟件的聚合工具雖然可以處理建筑物之間相交和重疊空間拓?fù)潢P(guān)系問(wèn)題，但是有些聚合后建筑物整體輪廓的直角特征不明顯；使用CDT法處理所得結(jié)果如圖10d所示。從實(shí)驗(yàn)結(jié)果的比較可以看出，使用本文所提方法和CDT法在處理建筑物群的多邊形數(shù)據(jù)里存在相交和重疊空間拓?fù)潢P(guān)系的聚合問(wèn)題時(shí)，能夠更好地保留建筑物整體輪廓的直角化特征。

6 結(jié)語(yǔ)

本文提出了基于頂點(diǎn)線性插值的建筑物群聚合的簡(jiǎn)易方法，在插值加密建筑物輪廓線頂點(diǎn)后，直接構(gòu)建相鄰建筑物頂點(diǎn)之間最短鄰近連線用于分析、量測(cè)和計(jì)算建筑物群的鄰近關(guān)系實(shí)現(xiàn)聚合；與基于CDT的建筑物聚合方法相比，該方法簡(jiǎn)化了計(jì)算過(guò)程，融合了三角網(wǎng)法[14-16]和緩沖區(qū)法[12-13]的特點(diǎn)。實(shí)驗(yàn)結(jié)果表明該方法實(shí)現(xiàn)了定性、定量獲取建筑物群鄰近關(guān)系進(jìn)行聚合；處理了建筑物群的多邊形數(shù)據(jù)里存在相交和重疊空間拓?fù)潢P(guān)系的聚合問(wèn)題；能滿足較大跨度的建筑物聚合，聚合建筑物群的結(jié)果合理且美觀。目前，基于頂點(diǎn)線性插值的建筑物群聚合的簡(jiǎn)易方法通過(guò)探測(cè)相鄰建筑物間的空隙完成建筑物群的聚合，僅能完成建筑物內(nèi)部小島嶼的填充化簡(jiǎn)，后續(xù)將研究建筑物自身凹部細(xì)節(jié)的化簡(jiǎn)方法，實(shí)現(xiàn)建筑物群聚合和化簡(jiǎn)的一體化。