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

劉　洋，蘭澤英，張　榮

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

Research on Algorithm of Building Group and Aggregation Considering

Residential Distribution Features

LIU Yang, LAN Zeying, ZHANG Rong

?

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

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

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

Research on Algorithm of Building Group and Aggregation Considering

Residential Distribution Features

LIU Yang, LAN Zeying, ZHANG Rong

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

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

一、引言

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

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

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

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

文獻[3]提出一種綜合考慮距離、方向、大小等因素的“視覺距離”來衡量建筑物多邊形間的鄰近關系。其中，距離為建筑物多邊形間的平均距離，是描述目標關系疏密的主導因素，方向差異和大小差異作為權值加載到平均距離上，從而綜合衡量目標間的鄰近關系。基于此思想，并考慮工程化應用的便利，本文提出綜合采用建筑物多邊形間鄰接相關邊長度和平均距離來衡量其視覺鄰近關系。

1. 建筑物多邊形間的鄰接相關邊長度計算

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

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

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

3) 計算多邊形間的鄰接相關邊長度。多邊形間所有鄰接跨立三角形底邊的集合即為多邊形間的鄰接相關邊，其長度采用加權方式計算。設三角形的底邊長度為l，底邊中點到頂點距離為d，通過d與閾值D比值的加權取得有效相關邊長度，計算公式為

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

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

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

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

3. 建筑物分組合并

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

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

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

3) 返回步驟1)。

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

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

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

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

1) “背景”區(qū)域提取：首先基于約束Delaunay三角網(wǎng)建立城中村建筑物群的空間剖分模型，構建建筑物群的凸殼，用凸殼與建筑物區(qū)域作差運算來提取背景區(qū)域；

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

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

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

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

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

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

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

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

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

五、試驗結果

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

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

表1　參數(shù)值

六、結束語

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

參考文獻：

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

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

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

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

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

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

作者簡介：劉洋(1981—)，男，博士，高級工程師，研究方向為地理信息系統(tǒng)、3S集成技術。E-mail：liuyang_052@163.com

基金項目：國家自然科學基金青年科學基金(41301377)

收稿日期：2015-01-03

中圖分類號：P208

文獻標識碼：B

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

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