基于CDT骨架線的地圖目標(biāo)鄰近沖突識(shí)別

劉遠(yuǎn)剛，郭慶勝，蔡永香，柯西林 ，龍穎波，李紳弘

(1. 長(zhǎng)江大學(xué) 地球科學(xué)學(xué)院，湖北 武漢 430100；2. 武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079；3. 地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710054)

基于CDT骨架線的地圖目標(biāo)鄰近沖突識(shí)別

劉遠(yuǎn)剛1，郭慶勝2，蔡永香1，柯西林3，龍穎波1，李紳弘1

(1. 長(zhǎng)江大學(xué) 地球科學(xué)學(xué)院，湖北 武漢 430100；2. 武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079；3. 地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710054)

制圖綜合過(guò)程中隨著比例尺的縮小，不可避免地產(chǎn)生鄰近沖突。為了在數(shù)字環(huán)境下自動(dòng)地解決這類沖突，首先需要實(shí)現(xiàn)這些沖突的自動(dòng)識(shí)別。文中提出一種基于CDT骨架線的地圖目標(biāo)鄰近沖突識(shí)別方法。該方法首先基于CDT提取地圖目標(biāo)之間空白區(qū)域的骨架線；然后沿著每一條骨架線弧段所穿過(guò)的三角形路徑搜索相鄰地圖目標(biāo)之間的沖突區(qū)域(寬度小于閾值的三角形集合)；最后，從沖突涉及的地圖目標(biāo)、發(fā)生沖突的空間位置以及沖突嚴(yán)重程度3個(gè)方面給出所識(shí)別沖突的定量化描述，從而為鄰近沖突的解決提供依據(jù)。

制圖綜合；鄰近沖突；沖突識(shí)別；CDT骨架線

制圖綜合過(guò)程中隨著比例尺的縮小，地圖上的空白區(qū)域越來(lái)越小，同時(shí)為了表達(dá)的清晰性，部分地圖目標(biāo)不得不采用夸大的地圖符號(hào)表示，導(dǎo)致地圖上鄰近目標(biāo)之間的占位競(jìng)爭(zhēng)越來(lái)越激烈，最終不可避免地產(chǎn)生鄰近沖突。此時(shí)，一般采用移位操作對(duì)這些沖突加以處理。為了實(shí)現(xiàn)數(shù)字地圖中移位操作的自動(dòng)化，首先得實(shí)現(xiàn)這種鄰近沖突的自動(dòng)識(shí)別，首先需要知道：誰(shuí)和誰(shuí)沖突；沖突在什么位置發(fā)生；沖突的嚴(yán)重程度如何。目前，針對(duì)移位問(wèn)題提出了不少鄰近沖突識(shí)別的方法，主要有基于緩沖區(qū)的方法[1-4]、基于聚類分析的方法[5-6]、基于柵格數(shù)據(jù)結(jié)構(gòu)的方法[7-8]和基于CDT(constrained Delaunay triangulation)或Voronoi圖的方法[9-10]等。借助CDT在空間鄰近表達(dá)上的優(yōu)勢(shì)，能夠方便地在矢量地圖模型下描述目標(biāo)間的鄰近關(guān)系,從而快速地探測(cè)地圖上的鄰近沖突[11]。因此，本文專注于基于CDT骨架線的地圖目標(biāo)鄰近沖突識(shí)別方法研究，給出定量化的沖突識(shí)別和描述手段，試圖為數(shù)字環(huán)境下地圖目標(biāo)移位操作的自動(dòng)化提供支撐。

1 地圖目標(biāo)的Voronoi圖和CDT骨架線

鄰近沖突是相鄰目標(biāo)的鄰近關(guān)系遭到破壞的結(jié)果，因此首先需要刻畫出地圖目標(biāo)的鄰近關(guān)系。一般的地圖或GIS數(shù)據(jù)模型中，這種空間關(guān)系信息是無(wú)法直接得到的，需要通過(guò)專門的空間關(guān)系計(jì)算模型才能得出[12]。在計(jì)算幾何領(lǐng)域，Voronoi圖一直是用于描述和分析空間平面點(diǎn)集鄰近關(guān)系最為有效的幾何結(jié)構(gòu)之一。而在地圖中，空間目標(biāo)按照幾何圖形特征可分為點(diǎn)、線、面3種，經(jīng)典的Voronoi圖不足以描述地圖平面上空間目標(biāo)之間的鄰近關(guān)系。于是需要構(gòu)造地圖平面中針對(duì)點(diǎn)、線、面目標(biāo)的Voronoi圖來(lái)描述地圖空間目標(biāo)(群)的鄰近關(guān)系。目前，對(duì)于地圖目標(biāo)群的Voronoi圖的構(gòu)造一般采用基于柵格的算法[13-15]，雖然這些算法的結(jié)果能夠較準(zhǔn)確地獲取地圖目標(biāo)之間的中軸，避免產(chǎn)生過(guò)多“毛刺”，但需要事先對(duì)圖形數(shù)據(jù)進(jìn)行繁瑣的矢柵轉(zhuǎn)換和二值化等處理，增加了計(jì)算量[12,16]。而基于矢量的方法對(duì)點(diǎn)狀目標(biāo)具有較好的適用性，對(duì)于包含面狀和線狀等復(fù)雜幾何對(duì)象的Voronoi圖較難實(shí)現(xiàn)[17]。本文的目的是通過(guò)Voronoi圖空間等距離剖分的特性表達(dá)地圖目標(biāo)之間的鄰近關(guān)系，對(duì)生成Voronoi圖的精度并無(wú)很高的要求，因此將采用基于CDT的算法構(gòu)造一種矢量數(shù)據(jù)的近似Voronoi圖，該結(jié)構(gòu)中的每一條邊是從CDT中提取出的一種相鄰地圖目標(biāo)之間空白區(qū)域的中軸線，一般稱為CDT骨架線[10,18-19]。采用文獻(xiàn)[19]中實(shí)現(xiàn)的算法，提取地圖目標(biāo)群間的骨架線，用于本文的鄰近沖突識(shí)別。如圖1所示，是對(duì)百度地圖上部分街區(qū)數(shù)字化后得到的實(shí)驗(yàn)數(shù)據(jù)，圖中描述了所提取的地圖上的獨(dú)立地物點(diǎn)、建筑物和街道三類不同要素的地圖目標(biāo)之間的骨架線，并構(gòu)建了這些地圖目標(biāo)之間的鄰近圖。每個(gè)地圖目標(biāo)周圍由數(shù)條骨架線弧段環(huán)繞，構(gòu)成一個(gè)閉合區(qū)域，該區(qū)域表達(dá)了對(duì)應(yīng)目標(biāo)的空間勢(shì)力范圍，總體上形成一種類似Voronoi圖的剖分結(jié)構(gòu)。圖中每條弧段對(duì)應(yīng)相鄰兩個(gè)目標(biāo)之間的1階鄰近關(guān)系[20]?；谶@種骨架線結(jié)構(gòu)可以很容易地計(jì)算出1階鄰近目標(biāo)之間的最小距離，從而為目標(biāo)間沖突的探測(cè)提供定量化指標(biāo)。

2 基于骨架線的鄰近沖突識(shí)別與描述

借助CDT骨架線提供的鄰近關(guān)系信息可以快速地識(shí)別地圖中相鄰兩目標(biāo)之間的沖突，并對(duì)沖突進(jìn)行描述。具體地，可以解答以下三個(gè)問(wèn)題：誰(shuí)和誰(shuí)沖突？沖突在什么位置發(fā)生？沖突的嚴(yán)重程度如何？

在CDT中，地圖上相鄰地圖目標(biāo)的空白區(qū)域被劃分為多個(gè)不規(guī)則的三角形單元，所提取的骨架線結(jié)構(gòu)將這些三角形串聯(lián)為連通的三角形路徑。沿著一條給定的骨架線弧段，依次計(jì)算其所穿過(guò)的每一個(gè)三角形在鄰近地圖目標(biāo)之間跨過(guò)的局部最小距離，將其中小于距離閾值dmin的三角形標(biāo)記出來(lái)。如果兩相鄰地圖目標(biāo)之間存在這種三角形，即說(shuō)明兩者存在鄰近沖突；同時(shí)，這些成串標(biāo)記的三角形就描繪了這兩個(gè)地圖目標(biāo)之間的沖突區(qū)域，即確定了沖突發(fā)生的具體位置；在此基礎(chǔ)上，進(jìn)一步找出其中距離最小的三角形，從而確定兩目標(biāo)之間的最小距離D。該最小距離可用于說(shuō)明鄰近沖突的程度，即當(dāng)兩目標(biāo)之間存在鄰近沖突時(shí)，它們離得越近，說(shuō)明沖突就越嚴(yán)重，需要移位的距離也就越大。所以本文將沖突嚴(yán)重程度用式(1)來(lái)定義。

sl=max[0,(dmin-D)].

(1)

式中：dmin為最小距離閾值；D為兩相鄰目標(biāo)之間的最小距離；sl表示該沖突的嚴(yán)重程度。將地圖符號(hào)的尺寸考慮在內(nèi)，兩相鄰地圖目標(biāo)之間的最小距離閾值可以由式(2)得到。

(2)

式中：dc是地圖上圖形之間可以辨識(shí)的最小距離閾值(一般設(shè)為0.2 mm)；r1和r2分別是兩個(gè)相鄰地

圖目標(biāo)的符號(hào)尺寸；dmin為兩地圖目標(biāo)之間的最小距離閾值。按式(1)、式(2)計(jì)算的沖突嚴(yán)重程度，實(shí)際上是解決沖突時(shí)，地圖目標(biāo)需要移位的距離，這為進(jìn)一步的解決沖突問(wèn)題提供了必要信息，增強(qiáng)了該方法的可用性。為了統(tǒng)一量綱，這里用地圖上通常采用的距離單位mm來(lái)度量沖突的嚴(yán)重程度。

以上是識(shí)別地圖上不同目標(biāo)之間沖突的主要思路，對(duì)于相同目標(biāo)內(nèi)部不同部分之間沖突的識(shí)別，思路類似，只不過(guò)所處理的骨架線弧段左右兩邊的地圖目標(biāo)是同一目標(biāo)的不同部分(例如，一個(gè)彎曲的兩個(gè)分支)。

為了描述和存儲(chǔ)所識(shí)別出的沖突目標(biāo)之間的沖突區(qū)域信息，定義了沖突區(qū)域?qū)ο髷?shù)據(jù)結(jié)構(gòu)如下(CJHJ語(yǔ)言描述)：

class Conflict_ Area

{

List TList;

Skeleton_ Arc ArcRef;

float Degree;

… …

}

其中TList表示該沖突區(qū)域所包含的一段連續(xù)三角形的序列，ArcRef表示該沖突區(qū)域所在的骨架線弧段的引用, Degree表示沖突的大小。每一個(gè)沖突區(qū)域?qū)ο笏娜切涡蛄兄兄辽俅嬖谝粋€(gè)三角形，且它們是相互連通的。也就是說(shuō)，如果一條骨架線上存在多段分開(kāi)的沖突三角形序列，則被分別表示為不同的沖突區(qū)域?qū)ο蟆＿@樣做可以將目標(biāo)之間或目標(biāo)內(nèi)部那些具有比較復(fù)雜的空間上下文的沖突進(jìn)行分解，有助于更好地指導(dǎo)后續(xù)的移位操作。

如圖2所示，是對(duì)與圖1中相同的實(shí)驗(yàn)數(shù)據(jù)采用本方法進(jìn)行沖突識(shí)別的結(jié)果，受篇幅所限，僅對(duì)圖中的局部范圍放大顯示。圖上三類地圖要素在1∶10 000比例尺下符號(hào)化之后產(chǎn)生多處符號(hào)重疊和鄰近沖突(符號(hào)間距不足0.2 mm)。圖中各類要素對(duì)應(yīng)符號(hào)尺寸分別為：獨(dú)立地物點(diǎn)(直徑3.5 mm)、建筑物面(邊線寬0.35 mm)和街道線(線寬2.2 mm)。圖2(b)描述了采用本文提出的沖突識(shí)別方法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理得到的結(jié)果，其中所識(shí)別出的沖突區(qū)域用紅色三角形表示。通過(guò)對(duì)比，可見(jiàn)圖2(a)中所表現(xiàn)出的沖突及其范圍和算法識(shí)別的沖突區(qū)域(圖2(b))是一致的。

圖2 基于CDT骨架線的沖突識(shí)別結(jié)果

表1中列出了圖中識(shí)別出的21個(gè)沖突的詳細(xì)信息，包括發(fā)生沖突的地圖目標(biāo)和計(jì)算出的沖突嚴(yán)重程度值。經(jīng)對(duì)比分析可知符合圖中反映的實(shí)際情況，說(shuō)明本文的方法是有效的，并且該方法已經(jīng)在筆者相關(guān)的移位算法研究中加以應(yīng)用，這些應(yīng)用也表明該方法可以成功地用于點(diǎn)、線、面狀地圖目標(biāo)間的鄰近沖突識(shí)別，并為移位初始向量的計(jì)算提供依據(jù)[21-23]。

需要說(shuō)明的是，當(dāng)兩條線狀目標(biāo)相交時(shí)，它們之間的最小距離恒為0。采用以上方法識(shí)別出的沖突區(qū)域會(huì)包含關(guān)聯(lián)線交點(diǎn)附近的三角形。而從視覺(jué)認(rèn)知的角度看，這些區(qū)域并不屬于沖突，需要排除。如圖3(a)所示，可以以交點(diǎn)為圓心作緩沖區(qū)，與之相交的區(qū)域內(nèi)，所有三角形均不作為沖突區(qū)域。其中，緩沖區(qū)的半徑至少為最小距離閾值dmin，本文實(shí)驗(yàn)中設(shè)置為2*dmin。同理，在識(shí)別線目標(biāo)內(nèi)部沖突時(shí)，線目標(biāo)上彎曲頂點(diǎn)附近三角形內(nèi)部距離較小，導(dǎo)致彎曲左右分支之間的最小距離也小于閾值，因而被誤判為線內(nèi)部的沖突。為了排除這種“假?zèng)_突”情況，也需采用類似方式，此時(shí)將彎曲的頂點(diǎn)作為排除區(qū)域的圓心繪制緩沖區(qū)(見(jiàn)圖3(b))。

表1 沖突信息表 mm

圖3 排除線狀目標(biāo)的交點(diǎn)和彎曲頂點(diǎn)附近的“假?zèng)_突”

3 結(jié)束語(yǔ)

本文針對(duì)制圖綜合中移位操作的需要，提出了一種基于CDT骨架線的地圖目標(biāo)鄰近沖突識(shí)別方法。該方法利用CDT骨架線所蘊(yùn)含的空間鄰近關(guān)系，識(shí)別相鄰地圖目標(biāo)之間的鄰近沖突，并給出鄰近沖突的發(fā)生位置和嚴(yán)重程度的定量化描述。對(duì)實(shí)驗(yàn)數(shù)據(jù)的測(cè)試結(jié)果以及筆者之前有關(guān)移位算法研究中的應(yīng)用情況，均表明該方法是有效的。下一步將結(jié)合制圖知識(shí)和規(guī)則進(jìn)一步研究所識(shí)別鄰近沖突的特征和類型，為設(shè)計(jì)更合理的自動(dòng)化移位操作方法提供支持。

[1] NICKERSON B G. Automated cartographic generalization for linear features [J]. Cartographica: the International Journal for Geographic information and Geovisualization, 1988, 25(3): 15-66.

[2] LONERGAN M, JONES C B. An iterative displacement method for conflict resolution in map generalization [J]. Algorithmica, 2001, 30(2): 287-301.

[3] BADER M. Energy minimization methods for feature displacement in map generalization [D]: [Ph.D.]. Switzerland: Doctorate thesis, Geographic Information System Division, Department of Geography, University of Zurich, 2001.

[4] 郭慶勝，王琳，孫雅庚，等.線圖形簡(jiǎn)化與移位算子的協(xié)同方法[J].測(cè)繪學(xué)報(bào)，2016,45(7)：850-857.

[5] MACKANESS W A. An algorithm for conflict identication and feature displacement in automated map generalization[J]. Cartography and Geographic Information Systems, 1994, 21(4) :219-232.

[6] 劉晴，郭慶勝，龍毅. 比例射線移位算法的改進(jìn)及其應(yīng)用[J]. 測(cè)繪工程，2015，25(12)：68-71.

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

[9] THOM S. Automatic resolution of road network conflicts using displacement algorithms orchestrated by geographical agents [A]. In: 10th ICA Workshop on Generalisation and Multiple Representation[C]. Moscow, 2007.

[10] AI T H, ZHANG X, ZHOU Q, et al. A vector field model to handle the displacement of multiple conflicts in building generalization [J]. International Journal of Geographical Information Science, 2015, 29(8), 1310-1331.

[11] 艾廷華. Delaunay三角網(wǎng)支持下的空間場(chǎng)表達(dá)[J]. 測(cè)繪學(xué)報(bào), 2006, 35(1): 71-76.

[12] 趙仁亮.基于Voronoi圖的GIS空間關(guān)系計(jì)算[M].北京：測(cè)繪科學(xué)出版社, 2006.

[13] 劉小鳳，吳艷蘭，胡海. 面狀要素的多層次骨架線提取[J]. 測(cè)繪學(xué)報(bào)，2003，42(4): 588-594.

[14] 胡鵬，王海軍，邵春麗，等. 論多邊形中軸問(wèn)題和算法[J]．武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2005，30(10): 853-857.

[15] 郭邦梅，王濤，趙榮，等. 面狀要素骨架線提取算法的研究[J]. 測(cè)繪通報(bào)，2013(4): 17-19.

[16] 陳軍，趙仁亮. GIS空間關(guān)系的基本問(wèn)題與研究進(jìn)展[J].測(cè)繪學(xué)報(bào),1999,28(2):95-102.

[17] 喬慶華. 計(jì)算幾何基礎(chǔ)庫(kù)的建立及其在地圖自動(dòng)綜合中的若干應(yīng)用[D]. 武漢：武漢大學(xué), 2004.

[18] AI Tinghua, ZHANG Xiang. The aggregation of urban building clusters based on the skeleton partitioning of gap space [A]. The European Information Society, Lecture Notes in Geoinformation and Cartography [C]. Berlin : Springer-Verlag, 2007, 153-157.

[19] 劉遠(yuǎn)剛，郭慶勝，孫雅庚，等. 地圖目標(biāo)群間骨架線提取的算法研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版) ,2015,40(2):264-268.

[20] 杜曉初，郭慶勝.基于Delaunay 三角網(wǎng)的空間鄰近關(guān)系推理[J].測(cè)繪科學(xué)，2004，29 (6):65-67.

[21] LIU Y G, GUO Q S, SUN Y G. A complete solution of cartographic displacement based on elastic beams model and Delaunay triangulation[A]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2014, XL-4: 163-168.

[22] LIU Y G, GUO Q S, SUN Y G,et al. A combined approach to cartographic displacement for buildings based on skeleton and improved elastic beam algorithm[A]. PLoS ONE, 2014, 9(12): e113953.

[23] 劉遠(yuǎn)剛，郭慶勝， 孫雅庚，等. 地圖自動(dòng)綜合中Beams移位算法的實(shí)現(xiàn)與改進(jìn)[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2016, 41(4): 450-454.

[責(zé)任編輯：張德福]

Identifying proximity conflicts of map objects based on CDT skeleton

LIU Yuangang1, GUO Qingsheng2, CAI Yongxiang1, KE Xilin3, LONG Yingbo1, LI Shenhong1

(1. School of Geoscience, Yangtze University, Wuhan 430100, China; 2. School of Resource and Environment Science, Wuhan University, Wuhan 430079, China; 3. State Key Laboratory of Geo-information Engineering, Xi’an 710054, China)

In the process of cartographic generalization, duo to the reduction of scales, it is inevitable to encounter proximity conflicts. In order to solve these conflicts automatically in the digital environment, it needs to realize the automatic identification of the conflicts at first. This paper proposeds a method to identify the conflicts on the basis of constrained Delaunay triangulation skeleton. Firstly, the skeleton of white space between neighboring map objects are extracted. Then, the conflict regions between neighboring map objects are identified by using triangular path along each skeleton arc. It is represented by triangular sets with a width less than a threshold. Finally, the quantitative description of the identified conflicts from three aspects is given, including the conflicting map objects, the spatial location of conflict and the degree of conflict, which can provide the basis for the solution of proximity conflicts.

cartographic generalization; proximity conflicts; identification of the conflicts; CDT skeleton

2016-01-19；

2017-3-4

國(guó)家自然科學(xué)基金面上項(xiàng)目(41471384)；湖北省教育廳科學(xué)研究計(jì)劃指導(dǎo)性項(xiàng)目(B2015448)；地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金課題資助(SKLGIE2016-Z-4-1)；長(zhǎng)江大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(2016010)

劉遠(yuǎn)剛(1982-)，男，講師，博士.

郭慶勝(1965-)，男，教授，博士生導(dǎo)師.

著錄：劉遠(yuǎn)剛，郭慶勝，蔡永香，等.基于CDT骨架線的地圖目標(biāo)鄰近沖突識(shí)別[J].測(cè)繪工程，2017，26(8)：10-13，19.

10.19349/j.cnki.issn1006-7949.2017.08.003

P208

A

1006-7949(2017)08-0010-04