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

李 國(guó) 輝，龍 毅*，許 文 帥，周 侗，高 朝

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

?

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

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

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

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

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

0 引言

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

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

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

1 問(wèn)題描述

1.1 相關(guān)概念

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

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

1.2 基本思路

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

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

2.1 CD-TIN特征三角形分類

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

表1 三角形分類及其詳細(xì)說(shuō)明

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路內(nèi)三角形DRL=1∧DSL=0圖1△C分叉三角形DRL=3∧DSL=0圖1△D

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

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

Fig.1 Classification of CD-TIN triangles

2.2 SAOD提取

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

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

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

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

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

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

圖2 不同條件下SAOD提取過(guò)程示意

Fig.2 Diagram of SAOD extraction process under various conditions

圖3 一條路段的SAOD

Fig.3 The SAOD of one road fragment

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

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

Fig.4 Diagram of optimized D-P simplification

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

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

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

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

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

表2 道路化簡(jiǎn)數(shù)據(jù)統(tǒng)計(jì)

Table 2 Statistical data of road simplification

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

圖7 化簡(jiǎn)率走勢(shì)

Fig.7 Trend of simplification rate

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

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

5 結(jié)論

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

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

[2] 張傳明,潘懋,吳煥萍,等.保持拓?fù)湟恢滦缘牡雀呔€化簡(jiǎn)算法研究[J].北京大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,43(2):216-222.

[3] 陳軼,彭認(rèn)燦,鄭義東,等.基于 Douglas 雙側(cè)多叉樹(shù)的曲線綜合算法研究[J].測(cè)繪學(xué)報(bào),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].南京:南京師范大學(xué),2011.

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

[8] 艾廷華.基于場(chǎng)論分析的建筑物群的移位[J].測(cè)繪學(xué)報(bào),2004,33(1):89-94.

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

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

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

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

[13] 王家耀.地圖學(xué)原理與方法[M].北京:科學(xué)出版社,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

國(guó)家自然科學(xué)基金項(xiàng)目(41171350、41271449、41301514)；江蘇省高校自然科學(xué)研究項(xiàng)目(13KJB170020)

李國(guó)輝(1989-)，男，碩士研究生，主要研究方向?yàn)榈貓D自動(dòng)綜合。 *通訊作者E-mail：longyi@njnu.edu.cn

10.3969/j.issn.1672-0504.2015.03.004

P208

A

1672-0504(2015)03-0017-05