劉　洋，蘭澤英，張　榮

(1. 廣州市城市規(guī)劃勘測(cè)設(shè)計(jì)研究院，廣東 廣州 510060； 2. 廣東工業(yè)大學(xué)管理學(xué)院，廣東 廣州 510060)

Research on Algorithm of Building Group and Aggregation Considering

Residential Distribution Features

LIU Yang, LAN Zeying, ZHANG Rong

?

顧及居民地分布特征的建筑物分組合并算法研究

劉洋1，蘭澤英2，張榮1

(1. 廣州市城市規(guī)劃勘測(cè)設(shè)計(jì)研究院，廣東 廣州 510060； 2. 廣東工業(yè)大學(xué)管理學(xué)院，廣東 廣州 510060)

Research on Algorithm of Building Group and Aggregation Considering

Residential Distribution Features

LIU Yang, LAN Zeying, ZHANG Rong

摘要：建筑物多邊形分組合并是城市大比例尺地圖綜合中的重要問題。本文在建筑物群的約束Delaunay三角網(wǎng)空間剖分模型及目標(biāo)間“視覺距離”計(jì)算模型研究基礎(chǔ)上，以廣州地區(qū)3種具有典型分布特征的建筑物群分組合并操作為研究對(duì)象，并基于“分而治之”的思想，分別提出不同處理方法。設(shè)計(jì)的算子兼顧了適用性和效率，在廣州地區(qū)序列比例尺空間數(shù)據(jù)庫(kù)快速構(gòu)建中得到了成功應(yīng)用。

關(guān)鍵詞：建筑物多邊形分組合并；視覺距離；建筑物多邊形鄰近關(guān)系

一、引言

建筑物多邊形綜合是大中比例尺地圖縮編的重要內(nèi)容。與一般的水系、植被等自然地物不同，建筑物作為人造地物具有其特殊性[1-2]，如房屋多邊形角為直角、分布在道路兩側(cè)的房屋呈陣列化對(duì)齊等，這對(duì)建筑物綜合算子的適用性和效率提出了較高要求。

大比例尺地圖綜合中，建筑物多邊形分組合并是一個(gè)重要問題[1]，取得了較多的研究成果。郭仁忠[1]認(rèn)為鄰近關(guān)系是建筑物多邊形合并過程的重要依據(jù)，并針對(duì)拓?fù)溧徑c視覺鄰近兩種空間關(guān)系，分別提出基于矢量拓?fù)浣Y(jié)構(gòu)的“剪枝擴(kuò)展”算法和基于柵格結(jié)構(gòu)的兩垂直方向掃描填充算法。艾廷華[3]提出綜合考慮目標(biāo)間距離、方向和大小差異的“視覺距離”計(jì)算模型。錢海忠等[4]提出了把Agent技術(shù)與TIN技術(shù)、聚類技術(shù)相結(jié)合的算法(ABTM)。孟妮娜等[5]建立基于相同特征量的鄰近關(guān)系相似性模型和基于等距離關(guān)系曲線的鄰近關(guān)系相似性模型，對(duì)建筑物鄰近關(guān)系相似性作定量化計(jì)算和判斷。許文帥等[6]提出一種基于視覺鄰近探測(cè)的縫合算法。以上研究成果在理論層面為建筑物多邊形間的鄰近關(guān)系判定和分組合并方法提供了有益借鑒，但對(duì)于大規(guī)模工程化應(yīng)用中，設(shè)計(jì)顧及不同地域特征的建筑物分組合并算子無法面面俱到，而且此類應(yīng)用中對(duì)算子的適用性和效率提出了更高要求。

為此，在借鑒已有的研究成果的基礎(chǔ)上，本文以廣州地區(qū)3種具有典型分布特征的建筑物群分組合并操作為研究對(duì)象，3種樣本分別是城區(qū)規(guī)則排列建筑物群、城中村不規(guī)則排列建筑物群及郊區(qū)散列式建筑物群。本文基于“分而治之”的思想，分別提出不同的處理方法(具體算法見下文),本文設(shè)計(jì)的算子兼顧了適用性和效率，在廣州地區(qū)序列比例尺空間數(shù)據(jù)庫(kù)快速構(gòu)建中得到了成功應(yīng)用。

二、城區(qū)規(guī)則排列建筑物分組合并

文獻(xiàn)[3]提出一種綜合考慮距離、方向、大小等因素的“視覺距離”來衡量建筑物多邊形間的鄰近關(guān)系。其中，距離為建筑物多邊形間的平均距離，是描述目標(biāo)關(guān)系疏密的主導(dǎo)因素，方向差異和大小差異作為權(quán)值加載到平均距離上，從而綜合衡量目標(biāo)間的鄰近關(guān)系?；诖怂枷?，并考慮工程化應(yīng)用的便利，本文提出綜合采用建筑物多邊形間鄰接相關(guān)邊長(zhǎng)度和平均距離來衡量其視覺鄰近關(guān)系。

1. 建筑物多邊形間的鄰接相關(guān)邊長(zhǎng)度計(jì)算

鄰接相關(guān)邊是基于建筑物群的約束Delaunay三角網(wǎng)空間剖分模型及鄰接跨立三角形判定為基礎(chǔ)來定義的[3]，它構(gòu)成了建筑物目標(biāo)間的“鄰近通廊”，具體如下：

1) 采用Delaunay三角網(wǎng)建立建筑物群的空間剖分模型。為避免建筑物邊界與三角形相交及三角形穿越道路，本文采用約束Delaunay三角網(wǎng)，參加三角網(wǎng)構(gòu)建的點(diǎn)為建筑物邊界及道路中心線上的端點(diǎn)和內(nèi)插點(diǎn)，內(nèi)插步長(zhǎng)為相鄰建筑物間的最小距離閾值。

2) 確定多邊形間的鄰接跨立三角形。剔除位于多邊形內(nèi)部或其凹部區(qū)域的三角形，僅保留跨立三角形(即兩個(gè)節(jié)點(diǎn)在同一個(gè)要素上，另外一個(gè)節(jié)點(diǎn)在另一個(gè)要素上的三角形)。設(shè)跨立三角形位于同一要素上的邊為底邊，其他兩邊為腰，排除掉任意一條腰長(zhǎng)度超過距離閾值的三角形，排除掉腰與底邊形成的夾角中任意角度超過閾值θ(經(jīng)驗(yàn)取值)的三角形，剩下的即為多邊形間的鄰接跨立三角形。

3) 計(jì)算多邊形間的鄰接相關(guān)邊長(zhǎng)度。多邊形間所有鄰接跨立三角形底邊的集合即為多邊形間的鄰接相關(guān)邊，其長(zhǎng)度采用加權(quán)方式計(jì)算。設(shè)三角形的底邊長(zhǎng)度為l，底邊中點(diǎn)到頂點(diǎn)距離為d，通過d與閾值D比值的加權(quán)取得有效相關(guān)邊長(zhǎng)度，計(jì)算公式為

f(l,d)=l(1-wd/D)

式中，w為權(quán)，取值范圍為(0，1)，根據(jù)試驗(yàn)數(shù)據(jù)經(jīng)驗(yàn)取值。累加兩個(gè)多邊形之間所有跨立三角形的有效邊長(zhǎng)度，得到兩個(gè)多邊形的鄰近邊長(zhǎng)度。

2. 建筑物多邊形間的平均距離計(jì)算

鄰接跨立三角形集構(gòu)成了多邊形間的“鄰近通廊”，基于經(jīng)典算法[3]提取“鄰近通廊”的骨架線，獲取骨架線總長(zhǎng)度L、鄰接跨立三角形數(shù)量n、每個(gè)鄰接跨立三角形的高h(yuǎn)i及骨架線落在每個(gè)鄰接跨立三角形的長(zhǎng)度si，然后基于微積分思想加權(quán)累積得到兩多邊形間的平均距離

3. 建筑物分組合并

建筑物分組合并時(shí)，采用建筑多邊形間平均距離、建筑多邊形間鄰接相關(guān)邊長(zhǎng)度及建筑分組面積3個(gè)指標(biāo)作為控制指標(biāo)。其中，距離控制建筑物分組資格，只有建筑物距離小于閾值時(shí)才能分為一組；鄰接相關(guān)邊長(zhǎng)度控制分組決策過程，優(yōu)先合并鄰接相關(guān)邊長(zhǎng)度最長(zhǎng)的兩個(gè)建筑多邊形；建筑分組面積控制分組停止條件，即綜合的粒度，當(dāng)分為一組的多邊形總面積超過閾值(縮編后最小上圖面積)時(shí)，此組多邊形將喪失“活性”，不再參與合并。建筑物分組的具體過程如下：

1) 計(jì)算每個(gè)建筑物多邊形的面積并排序，面積大于縮編后最小上圖面積的多邊形將喪失“活性”，不再參與分組操作，取面積最小的“活躍”多邊形A作為當(dāng)前目標(biāo)。

2) 在Delaunay三角網(wǎng)建立的建筑物群的空間剖分模型中考察與A有鄰接跨立三角形聯(lián)系的建筑物多邊形集U，獲取與A平均距離在閾值以內(nèi)的建筑物多邊形集U′，取U′中與A鄰接相關(guān)邊長(zhǎng)度最長(zhǎng)的建筑物多邊形B與之優(yōu)先分為一組(當(dāng)鄰接相關(guān)邊長(zhǎng)度相同時(shí)，考慮平均距離較小的多邊形)；分組后的多邊形集將作為一個(gè)完整的大多邊形參與面積計(jì)算、排序和分組操作。

3) 返回步驟1)。

4) 直至所有多邊形均喪失“活性”，分組操作停止。

具體系統(tǒng)開發(fā)時(shí)，還應(yīng)提供高效的人機(jī)交互工具，方便作業(yè)員對(duì)不合理的分組進(jìn)行調(diào)整。調(diào)整完成后在保持建筑物直角化特征的情況下進(jìn)行建筑物合并操作，最后刪除面積小于上圖面積的建筑物。

三、城中村不規(guī)則排列建筑物分組合并

廣州市城中村建筑物群具有其獨(dú)特的分布特征：建筑物分布雜亂，無統(tǒng)一的朝向及明顯的分布模式，呈片團(tuán)不規(guī)則聚集；存在大量“握手樓”，建筑物間距狹小，街道蜿蜒、寬度不一、存在較多斷頭路現(xiàn)象。若直接采用上節(jié)的算法，效果并不理想。在傳統(tǒng)人工綜合縮編時(shí)，對(duì)此類建筑物處理采用如下思路：根據(jù)城中村街道及建筑群分布間隙，生成較完整的區(qū)域路網(wǎng)，首先依據(jù)綜合尺度對(duì)路網(wǎng)進(jìn)行抽稀，保持區(qū)域的骨架結(jié)構(gòu)，然后以道路為硬約束條件對(duì)建筑群進(jìn)行分割，并設(shè)置較小的距離閾值對(duì)建筑物進(jìn)行分組合并?；诖恕跋嚷肪W(wǎng)生成處理，后建筑物分組合并”的迂回策略，本文提出“四步走”的處理方法：

1) “背景”區(qū)域提?。菏紫然诩s束Delaunay三角網(wǎng)建立城中村建筑物群的空間剖分模型，構(gòu)建建筑物群的凸殼，用凸殼與建筑物區(qū)域作差運(yùn)算來提取背景區(qū)域；

2) 構(gòu)建道路網(wǎng)stroke模型[7]：包括生成道路中心線弧段、道路中心線弧段stroke連接及stroke分級(jí)3個(gè)部分。所謂stroke是指具有連通延展性的弧段分組。

a. 生成道路中心線弧段：采用“骨架線”提取算法生成背景區(qū)域的骨架線網(wǎng)絡(luò)，對(duì)骨架線進(jìn)行平滑、化簡(jiǎn)和數(shù)據(jù)預(yù)處理(斷線連接，刪除偽結(jié)點(diǎn)、懸掛線、短線等)，生成道路中心線弧段網(wǎng)絡(luò)，借鑒建筑物平均距離的計(jì)算方法獲取每個(gè)弧段的平均寬度，并計(jì)算其長(zhǎng)度。

b. 道路中心線弧段stroke連接：即判斷拓?fù)潢P(guān)聯(lián)的弧段是否屬于同一stroke的過程，一般綜合考慮弧段間的方向一致性和語義一致性進(jìn)行判斷，本文采用的連接策略是以方向一致性判斷為主，輔以街道名稱來判斷(若為無名路則不考慮語義一致性)。設(shè)道路中心線弧段ei和ej，它們可劃分為同一stroke進(jìn)行連接的條件是：ei和ej具有公共結(jié)點(diǎn)p，且ei和ej的方向夾角θij(取銳角)小于閾值δ(一般根據(jù)試驗(yàn)結(jié)果確定)。θij越小，ei和ej的連通延展性越好，θij=0時(shí)，兩者方向完全一致。然后計(jì)算同一組弧段的平均寬度和總長(zhǎng)度作為stroke的寬度和長(zhǎng)度。

c. 道路中心線弧段stroke分級(jí)：為了簡(jiǎn)便，本文主要綜合考慮stroke的寬度和長(zhǎng)度對(duì)其進(jìn)行分級(jí)，判定標(biāo)準(zhǔn)如下：若stroke寬度和長(zhǎng)度均滿足當(dāng)前等級(jí)I閾值要求時(shí)，直接設(shè)定其等級(jí)為I；若寬度達(dá)不到閾值要求，則直接與下一等級(jí)比較；若寬度滿足要求，長(zhǎng)度不夠時(shí)，則直接設(shè)定其等級(jí)為I-2。計(jì)算機(jī)自動(dòng)分級(jí)后局部不合理之處需人工調(diào)整。

3) 顧及道路目標(biāo)stroke特征保持的路網(wǎng)自動(dòng)綜合：本文采用文獻(xiàn)[7]提出的綜合算法，首先依據(jù)方根模型確定道路的選取比例，采用約束Delaunay三角網(wǎng)構(gòu)建道路中心線弧段的鄰近關(guān)系模型，然后按如下算法對(duì)路網(wǎng)進(jìn)行迭代抽?。孩冁i定高等級(jí)道路；②刪除最短沒有被鎖定且刪除后不影響連通性的道路R；③鎖定R周圍的道路；④如果達(dá)到選取比例則終止，否則到⑤；⑤如果所有道路都被鎖定則解鎖所有低等級(jí)道路，并跳至②。本算法不僅可兼顧個(gè)體目標(biāo)重要性和保持路網(wǎng)密度分布特征，而且可以動(dòng)態(tài)維護(hù)路網(wǎng)的連通性。

4) 建筑物分組合并：以綜合的道路為硬約束條件，設(shè)置比城區(qū)其他區(qū)域較小的距離閾值，按第2節(jié)視覺鄰近關(guān)系計(jì)算方法和分組策略對(duì)建筑群進(jìn)行處理。

四、郊區(qū)散列式居民地分組合并

廣州市郊區(qū)的散列式居民地主要有兩種分布類型，一般位于花都、從化及增城等山區(qū)。一是沿道路、河流分布的散列式居民地，此類居民地合并與城區(qū)不同，合并多邊形邊界除了應(yīng)盡量滿足垂直相交、邊界平直之外，還需要顧及與周圍河流、道路的延展方向，并保持整體范圍性的部分居民地。二是隨機(jī)分布的散列式居民地，此類居民地綜合大多采用基于群點(diǎn)重采樣算法進(jìn)行化簡(jiǎn)和選取。本文主要對(duì)第一種具有方向延展性分布特征的居民地分組合并操作進(jìn)行研究。

首先采用經(jīng)典的道格拉斯算法對(duì)道路河流中心線進(jìn)行化簡(jiǎn)，并獲取其擬合直線，該直線表示居民地分布的延展方向。在此基礎(chǔ)上，居民地合并時(shí)除考慮目標(biāo)間的距離、鄰接相關(guān)邊長(zhǎng)度外，還應(yīng)考慮目標(biāo)間的方向。文獻(xiàn)[3]采用方向差異權(quán)值Cd對(duì)目標(biāo)間的鄰接相關(guān)邊長(zhǎng)度進(jìn)行修正。獲取相鄰多邊形重心連線與道路或河流擬合直線間的夾角?，?的取值范圍為[0,90°]，Cd取值范圍為[1,2]，角度越大，Cd越大，即方向的不一致將導(dǎo)致目標(biāo)間的疏遠(yuǎn)，分組合并算法的總體框架與第2節(jié)一致。

五、試驗(yàn)結(jié)果

本文在3個(gè)典型樣本區(qū)域抽取了大量數(shù)據(jù)對(duì)以上設(shè)計(jì)的算子進(jìn)行了應(yīng)用試驗(yàn)，并不斷調(diào)整確定各種關(guān)鍵參數(shù)。其中最小距離閾值和最小上圖面積閾值根據(jù)相應(yīng)尺度綜合的制圖規(guī)范確定，可根據(jù)廣州市的特殊情況作適當(dāng)調(diào)整。而建筑物鄰接相關(guān)邊長(zhǎng)度計(jì)算及道路中心線弧段stroke連接中的關(guān)鍵參數(shù)確定見表1。試驗(yàn)后，本文設(shè)計(jì)的算子在廣州地區(qū)序列比例尺空間數(shù)據(jù)庫(kù)快速構(gòu)建中得到了大規(guī)模工程化應(yīng)用，在適用性和計(jì)算效率方面均取得較好效果。

效率方面，本文中建筑物分組時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(n)；城中村道路中心線弧段stroke分級(jí)算法時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)；城中村道路綜合算法時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(n)。通過工日對(duì)比測(cè)算，本文采用的建筑物分組合并算法在效率上約為人工的6倍以上。適用性方面，從試驗(yàn)結(jié)果來看，本文設(shè)計(jì)的算法很好地顧及了目標(biāo)重要性、目標(biāo)間視覺鄰近關(guān)系及保持目標(biāo)群整體分布特征等多方面的要求。

表1　參數(shù)值

六、結(jié)束語

建筑物多邊形分組合并是城市大比例尺地圖綜合中的重要問題。本文在建筑物群的約束Delaunay三角網(wǎng)空間剖分模型及目標(biāo)間“視覺距離”計(jì)算模型研究基礎(chǔ)上，以廣州地區(qū)3種典型分布特征的建筑物群分組合并操作為研究對(duì)象，基于“分而治之”的思想，分別提出不同處理方法：對(duì)于城區(qū)規(guī)則排列建筑物群，考慮工程化應(yīng)用的便利，提出綜合采用建筑物多邊形間鄰接相關(guān)邊長(zhǎng)度和平均距離來衡量建筑物多邊形間的視覺鄰近關(guān)系，并設(shè)計(jì)分組算法采用平均距離、鄰接相關(guān)邊長(zhǎng)度及建筑分組面積3個(gè)控制指標(biāo)來決策建筑物分組的“活性”、優(yōu)先級(jí)和綜合粒度；對(duì)于城中村不規(guī)則排列建筑物群，采用“先路網(wǎng)生成處理，后建筑分組合并”的迂回策略，提出背景區(qū)域提取、構(gòu)建路網(wǎng)stroke模型、顧及道路目標(biāo)stroke特征保持的路網(wǎng)自動(dòng)綜合、建筑物分組合并的“四步走”處理方法；對(duì)于郊區(qū)具有方向延展性的建筑物群，提出采用方向差異權(quán)值對(duì)目標(biāo)間鄰接相關(guān)邊長(zhǎng)度進(jìn)行修正的做法，將方向因子納入視覺鄰近關(guān)系計(jì)算中。本文設(shè)計(jì)的算子在適用性和計(jì)算效率方面均取得了較好效果。

參考文獻(xiàn)：

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

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

[3]艾廷華, 郭仁忠.基于格式塔識(shí)別原則挖掘空間分布模式[J].測(cè)繪學(xué)報(bào)，2007，36(3)：302-308.

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

[5]孟妮娜，艾廷華，周校東.建筑群鄰近關(guān)系相似性計(jì)算[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2012，37(7):775-778.

[6]許文帥，龍毅，周侗，等.面向復(fù)雜多邊形合并的視覺鄰近探測(cè)與縫合算法[J].地理與地理信息科學(xué),2014,30(1):125-126.

作者簡(jiǎn)介：劉洋(1981—)，男，博士，高級(jí)工程師，研究方向?yàn)榈乩硇畔⑾到y(tǒng)、3S集成技術(shù)。E-mail：liuyang_052@163.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金青年科學(xué)基金(41301377)

收稿日期：2015-01-03

中圖分類號(hào)：P208

文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：0494-0911(2015)12-0050-04

引文格式： 劉洋，蘭澤英，張榮. 顧及居民地分布特征的建筑物分組合并算法研究[J].測(cè)繪通報(bào)，2015(12)：50-53.DOI:10.13474/j.cnki.11-2246.2015.376