李 國 輝，龍 毅*，許 文 帥，周 侗，高 朝

(1.南京師范大學地理科學學院，江蘇 南京 210023；2.常州市基礎地理勘測中心，江蘇 常州 213003；3.南通大學地理科學學院，江蘇 南通 226007)

?

目標移位安全區(qū)約束的道路D-P化簡優(yōu)化方法

李 國 輝1，龍 毅1*，許 文 帥2，周 侗3，高 朝1

(1.南京師范大學地理科學學院，江蘇 南京 210023；2.常州市基礎地理勘測中心，江蘇 常州 213003；3.南通大學地理科學學院，江蘇 南通 226007)

針對道路化簡產生的與建筑物空間關系不一致問題，以道路與建筑物要素的關聯(lián)關系為出發(fā)點，構建道路的目標移位安全區(qū)，在此基礎上對D-P化簡算法進行改善，提出一種以道路目標移位安全區(qū)為約束的D-P化簡優(yōu)化算法，在化簡道路曲線的同時保證化簡后道路曲線不與鄰近建筑物產生空間沖突。選取1:10 000的建筑物與道路數據對多種目標比例尺的化簡操作進行實驗，結果表明該方法可有效保持道路與建筑物間的空間關系。

目標移位安全區(qū)；道路；建筑物；D-P化簡；優(yōu)化方法

0 引言

地圖制圖綜合中，常需對道路數據進行化簡[1]。早期針對曲線化簡算法的研究取得了豐富的成果，方法也比較成熟，典型的有Douglas-Peucker法(D-P法)、Lang法、Li-Openshaw法、垂距法、光柵法等[2-4]，其中D-P法是一種從全局出發(fā)的經典化簡算法，通過遞歸逐步舍棄次要點以達到化簡目的[5]，在道路數據的化簡中應用廣泛[1]。建筑物與道路之間有著顯著的空間依賴性和語義依存性，建筑物多沿道路兩側布局，兩要素貼合緊密[6]，因此道路的化簡操作需要協(xié)同考慮建筑物的空間布局。傳統(tǒng)的基于道路單要素化簡可能導致道路與建筑物的空間沖突，比如道路與建筑物幾何上相互壓蓋，嚴重情況下建筑物可能因為道路彎曲段的化簡而從道路的一側越到另一側，產生方位沖突。

道路與建筑物沖突處理主要有移位道路與移位建筑物兩種方式，其選擇取決于數據的定位精度和具體的應用背景。已有的沖突處理方式主要針對地圖比例尺縮小道路變寬或者道路符號化后產生的拓撲關系沖突或視覺鄰近沖突情況[7-12]，此時根據要素的優(yōu)先級和精度大小，多采用移位建筑物的方式以保證具有較高優(yōu)先級的道路精度。而對于諸如風景名勝區(qū)、動植物園或建筑物專題圖等建筑物重要性高于道路的情況，綜合過程中建筑物優(yōu)先級往往高于道路[13]，此時宜保證建筑物不動而調整道路；且在數據來源、比例尺相同原始數據精度相似的情況下，化簡后的道路準確性和精度要低于建筑物[13]，移位建筑物的方式容易導致幾何精度進一步降低。

道路圖形的協(xié)同化簡既是對自身幾何信息細節(jié)的約簡，又是對兩要素空間、結構關系等進行保持和維護的過程，考慮到道路與建筑物之間具有天然的地理關聯(lián)性，僅通過道路單要素的化簡無法保證化簡后的道路與建筑物達到一致化的效果。本文根據道路與建筑物的聯(lián)合CD-TIN探測雙要素之間空間鄰近關系，在此基礎上構建道路的目標移位安全區(qū)(Security Area of Object Displacement,SAOD)，以目標移位安全區(qū)約束道路曲線的化簡，有效避免了雙要素之間因為道路化簡而產生的空間沖突。

1 問題描述

1.1 相關概念

(1)路段。路段是路網中被道路交叉點分隔而成的道路曲線段，是一條完整道路的一部分。在化簡過程中，由于道路交叉點有著特殊的地理指示作用，精度要求高，因此以路段作為構建目標移位安全區(qū)進行協(xié)同約束化簡的基本單位，可以利用D-P化簡保留首末點的特性強行保留道路交叉點。

(2)雙要素。要素是從幾何和語義角度劃分的一類地理目標的集合，如道路目標的集合即為道路要素。由于本文主要研究道路與建筑物間的空間關系及其協(xié)同操作，因此下文提及的雙要素特指道路與建筑物兩個要素。

1.2 基本思路

地圖上建筑物應位于道路兩側，道路化簡產生的雙要素沖突往往是與鄰近的建筑物相交或越過鄰近建筑物而導致的空間沖突。解決此沖突直接而有效的方式就是避免空間沖突的產生，即改變道路化簡方法，將道路的化簡結果控制在鄰近建筑物所約束的空間范圍內，該空間范圍即目標移位安全區(qū)。由于建筑物成組分布且形態(tài)變化較大，與道路之間的鄰近程度也不同，無法通過緩沖區(qū)等方法獲得定寬的目標移位安全區(qū)，而CD-TIN是一種從全局角度構建的空間結構，通過三角形邊的連接關系探測道路與建筑物目標間的鄰近關系，方便構建道路的目標移位安全區(qū)。D-P算法作為曲線化簡的經典算法，在道路的化簡過程中應用廣泛，且由于該算法是一種以逐步遞歸由粗到精的方式尋找曲線的特征點，因此可以借鑒該特點，對導致空間沖突的局部線段通過增加遞歸程度逐步消除沖突。

2 雙要素協(xié)同的SAOD提取

2.1 CD-TIN特征三角形分類

由于Delaunay三角網結構具有很好的空間關系表達能力，通過構建雙要素聯(lián)合CD-TIN可以有效探測要素之間的鄰近關系。三角形類型特征是判斷成組三角形組合模式的基礎，也是進行SAOD提取的必要條件。根據三角形頂點所在的目標類型及頂點之間鄰接關系的不同，將CD-TIN三角形分為不同的類型，表1為與道路移位安全區(qū)提取相關的三角形分類及其形式化描述。需要指出的是，同一個三角形在不同路段中類型可能不同，因此三角形類別必須針對特定的路段。

表1 三角形分類及其詳細說明

Table 1 Classification and description of triangles

三角形類型形式化描述圖形路端三角形(P0∈Δt∧P1∈Δt)∨(PN-2∈Δt∧PN-1∈Δt)圖1△A1/△A2橋接三角形DRL+DSL=2∨(DRL=2∧DSL=1)圖1△B1/△B2/△B3/△B4路內三角形DRL=1∧DSL=0圖1△C分叉三角形DRL=3∧DSL=0圖1△D

定義當前路段從起點到終點編號P0、P1、P2、…、PN-1共N個點，對于三角網中任意給定的三角形t(v1,v2,v3)(簡稱為△t，其中v1、v2、v3為3個頂點)，Pk∈Δt表示路段的第k個點是△t中的一個頂點，DRL表示△t的3個頂點所在不同路段的個數，DSL表示△t的3個頂點中在建筑物上的個數。圖1中的粗實線為當前路段，三角形針對該路段進行類型判別。

圖1 CD-TIN三角形分類示意

Fig.1 Classification of CD-TIN triangles

2.2 SAOD提取

SAOD構建過程中，首先提取與當前路段直接相連的所有三角形并存于集合T，其次根據T中三角形的不同類型采用如下規(guī)則提取新的多邊形以構建SAOD。新建集合S用于存放處理后的三角形或四邊形，具體構建規(guī)則如下(定義center(v1,v2)表示v1和v2點的中點，center(t)表示△t的中點)。

規(guī)則1：對于路端三角形t(v1,v2,v3)，設v1和v2位于當前路段的起始點上；若v3位于建筑物上，如圖2a中三角形t1，則將△t存入S中；若v3在另外一條路段上，如圖2a中三角形t2，則重新構建三角形t(v1,v2,center(v2,v3))存入S；特殊情況下，若v3位于當前路段上，則按照路內三角形的處理規(guī)則對△t進行處理。

規(guī)則2：對于接橋三角形t(v1,v2,v3)，設v1點位于當前路段上；若v1位于路段的起點或終點，且v2和v3都不在當前路段上，則該三角形不參與構建SAOD，直接刪除；若只有一個點位于其他路段上(設該點為v3)，另外一點位于建筑物或當前路段上，如圖2b中三角形t1，則構建三角形t(v1,v2,center(v1,v3))存入S；若v2和v3兩點位于除當前路段外的同一路段上，如圖2b中三角形t2，則構建三角形t(v1,center(v1,v2),center(v1,v3))存入S；若△t中所有點位于建筑物和當前路段上，如圖2b中三角形t3，則直接將△t存入S中即可。

規(guī)則3：路內三角形t(v1,v2,v3)與其他任何目標無聯(lián)系，如圖2c中三角形t1，整個三角形都屬于路段的SAOD，只需要將△t完整存入S即可。

規(guī)則4：分叉三角形t(v1,v2,v3)被3條不同路段共用，如圖2d中三角形t1，設v1點位于當前路段上，v2、v3分別位于另兩條路段上，則構建多邊形t(v1,center(v1,v2),center(t),center(v1,v3))存入S。

對集合T中的所有三角形按照上述規(guī)則處理后，集合S就存放了組成當前路段的SAOD所需的幾何體，只需要將S中的幾何體依次合并成一個統(tǒng)一的多邊形，如圖3所示，粗實線表示當前路段，虛線包圍的陰影區(qū)域即為該路段的SAOD。

圖2 不同條件下SAOD提取過程示意

Fig.2 Diagram of SAOD extraction process under various conditions

圖3 一條路段的SAOD

Fig.3 The SAOD of one road fragment

3 D-P化簡優(yōu)化方法

圖4 D-P優(yōu)化算法示意

Fig.4 Diagram of optimized D-P simplification

4 實驗與分析

在Eclipse 3.7環(huán)境下利用Java語言對提出的方案進行實驗和分析。數據選取1∶10 000廬山地區(qū)部分道路與建筑物數據，如圖5a所示，其中建筑物335個，路段67個，道路總點數為913個，構建的SAOD如圖5b所示。以1∶25 000作為化簡的目標比例尺，圖上距離3 mm作為最小可視范圍，可得D-P化簡閾值為7.5 m。圖6顯示了傳統(tǒng)D-P化簡結果和以SAOD為約束的D-P化簡結果的疊加圖，可以看出，傳統(tǒng)的化簡方法導致道路與建筑物相交的情況較多，而以SAOD為約束化簡方法有效避免了雙要素之間的空間沖突，保持了雙要素間的空間關系一致性，化簡結果較好。

圖5 雙要素原始數據及其SAOD 圖6 兩種化簡方式的疊加示意(1∶25 000)

Fig.5 Original data of two feature and their SAOD Fig.6 Diagram of two simplification methods

為進一步檢驗方法在跨越多比例尺下的可行性，對經典D-P化簡(簡稱“方法1”)和SAOD約束化簡(簡稱“方法2”)兩種方式4種目標比例尺下的多組化簡結果進行統(tǒng)計(表2)。定義化簡率為道路化簡后被刪除的總點數與化簡前的總點數的百分比，可見化簡率是評價化簡程度的重要標準。圖7是兩種方法在不同比例尺下的化簡率。

表2 道路化簡數據統(tǒng)計

Table 2 Statistical data of road simplification

根據表2和圖7可得如下結論：1)隨著比例尺跨度逐漸變大，利用方法1對道路單要素進行化簡出現的兩要素間空間沖突數量逐漸增多；方法2由于將曲線嚴格控制在安全范圍內，因而有效避免了空間沖突的產生。2)從化簡程度的角度看，本文提出的方法在比例尺跨度較小情況下的化簡效果較好，當比例尺跨度逐漸變大時，方法2的化簡率提升幅度逐漸減小，與方法1的化簡率差值逐漸變大?？尚械慕鉀Q辦法是化簡道路之前先選取道路與建筑物,將次要道路和建筑物刪除。此外，單要素化簡時個別目標之間出現相交的情況(如圖8a以道路與島嶼要素為例)，在利用目標移位安全區(qū)進行約束化簡時也可以解決(如圖8b)。由此可見，本文提出的方法在處理要素內部的空間沖突時也具有一定的可行性。

圖7 化簡率走勢

Fig.7 Trend of simplification rate

圖8 D-P優(yōu)化化簡方法在單要素內部沖突處理的作用

Fig.8 Role of this method in handing feature internal conflict

5 結論

在經典的D-P化簡算法的基礎之上，通過構建道路與建筑物雙要素的CD-TIN提取道路的目標移位安全區(qū)，設計出D-P化簡的優(yōu)化方法，在有效化簡道路曲線的同時避免了道路與建筑物之間可能的空間沖突，同時該方法在處理要素內部的空間沖突時也有一定的可行性。需要說明的是,以SAOD為約束的D-P優(yōu)化化簡算法在比例尺跨度過大時會導致化簡率提升幅度逐漸放緩，且地圖比例尺縮小后，符號化后的道路寬度也隨之增大，可能出現原始道路與建筑物之間產生空間沖突需要移位建筑物的情況，因此對于比例尺跨度較大且化簡率要求高的操作的適用性較低。在今后研究中將進一步探討如何在保證道路與建筑物空間關系一致性的同時不損耗道路的化簡率。

[1] 李少梅,安曉亞,孫群,等.道路數據綜合的融合算法研究[J].測繪科學,2009(5):11-13.

[2] 張傳明,潘懋,吳煥萍,等.保持拓撲一致性的等高線化簡算法研究[J].北京大學學報(自然科學版),2007,43(2):216-222.

[3] 陳軼,彭認燦,鄭義東,等.基于 Douglas 雙側多叉樹的曲線綜合算法研究[J].測繪學報,2010,39(3):310-315.

[4] OPHEIM H.Fast data reduction of a digitized curve[J].Geo-processing,1982,2:33-40.

[5] DOUGLAS D H,PEUCKER T K.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].Cartographica:The International Journal for Geographic Information and Geo-visualization,1973,10(2):112-122.

[6] 陳文瀚.地圖道路與居民地協(xié)同綜合方法研究[D].南京:南京師范大學,2011.

[7] 吳小芳,杜清運,徐智勇.多層次移位原則的道路與建筑物空間沖突處理[J].測繪學報,2010,39(6):649-654.

[8] 艾廷華.基于場論分析的建筑物群的移位[J].測繪學報,2004,33(1):89-94.

[9] 周啟,艾廷華,張翔.面向多重空間沖突解決的移位場模型[J].測繪學報,2013,42(4):615-620.

[10] 侯璇,武芳,劉芳,等.基于彈性力學思想的居民地點群目標位移模型[J].測繪科學,2005,30(2):44-47.

[11] 何津,費立凡.解決圖形沖突的受限變形所涉及的數學原則:以道路與建筑物的關系為例[J].武漢大學學報(信息科學版),2007,32(4):326-330.

[12] 費立凡,何津.解決街道與建筑物圖形沖突的移位模型研究[J].武漢大學學報(信息科學版),2007,32(6):540-543.

[13] 王家耀.地圖學原理與方法[M].北京:科學出版社,2006.

An Optimized Douglas-Peucker Method of Road Simplification Based on SAOD Constraints

LI Guo-hui1,LONG Yi1,XU Wen-shuai2,ZHOU Tong3,GAO Zhao1

(1.CollegeofGeographicScience,NanjingNormalUniversity,Nanjing210023;2.BasicGeographicSurveyingCenterofChangzhou,Changzhou213003;3.SchoolofGeographicScience,NantongUniversity,Nantong226007,China)

This paper presents an optimized Douglas-Peucker(D-P)algorithm to simplify roads curve which is focus on the inconsistency between simplified roads and buildings.In order to make sure the simplified roads do not cross the nearby buildings,this paper puts forward a concept named Security Area of Object Displacement(SAOD)which is extracted by Delaunay Triangulation(DT)of two features.The SAOD of a road is decided by the nearby buildings.The simplification ensure simplified road in a certain range by changing the recursion condition of the D-P algorithm.That is to say,the method not only can simplify the curve,but also can maintain consistency of spatial relations.Several experiments were taken to test this method.The results showed that the method can effectively avoid the conflicts between simplified roads and buildings.

SAOD;road;buildings;D-P simplification;optimized method

2014-11-26；

2015-01-28

國家自然科學基金項目(41171350、41271449、41301514)；江蘇省高校自然科學研究項目(13KJB170020)

李國輝(1989-)，男，碩士研究生，主要研究方向為地圖自動綜合。 *通訊作者E-mail：longyi@njnu.edu.cn

10.3969/j.issn.1672-0504.2015.03.004

P208

A

1672-0504(2015)03-0017-05