劉遠剛，郭慶勝，蔡永香，柯西林 ，龍穎波，李紳弘

(1. 長江大學 地球科學學院，湖北 武漢 430100；2. 武漢大學 資源與環(huán)境科學學院，湖北 武漢 430079；3. 地理信息工程國家重點實驗室，陜西 西安 710054)

基于CDT骨架線的地圖目標鄰近沖突識別

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

(1. 長江大學 地球科學學院，湖北 武漢 430100；2. 武漢大學 資源與環(huán)境科學學院，湖北 武漢 430079；3. 地理信息工程國家重點實驗室，陜西 西安 710054)

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

制圖綜合；鄰近沖突；沖突識別；CDT骨架線

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

1 地圖目標的Voronoi圖和CDT骨架線

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

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

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

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

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

(1)

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

(2)

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

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

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

為了描述和存儲所識別出的沖突目標之間的沖突區(qū)域信息，定義了沖突區(qū)域對象數(shù)據(jù)結構如下(CJHJ語言描述)：

class Conflict_ Area

{

List TList;

Skeleton_ Arc ArcRef;

float Degree;

… …

}

其中TList表示該沖突區(qū)域所包含的一段連續(xù)三角形的序列，ArcRef表示該沖突區(qū)域所在的骨架線弧段的引用, Degree表示沖突的大小。每一個沖突區(qū)域對象所包含的三角形序列中至少存在一個三角形，且它們是相互連通的。也就是說，如果一條骨架線上存在多段分開的沖突三角形序列，則被分別表示為不同的沖突區(qū)域對象。這樣做可以將目標之間或目標內部那些具有比較復雜的空間上下文的沖突進行分解，有助于更好地指導后續(xù)的移位操作。

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

圖2 基于CDT骨架線的沖突識別結果

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

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

表1 沖突信息表 mm

圖3 排除線狀目標的交點和彎曲頂點附近的“假沖突”

3 結束語

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

[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] 郭慶勝，王琳，孫雅庚，等.線圖形簡化與移位算子的協(xié)同方法[J].測繪學報，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]. 測繪工程，2015，25(12)：68-71.

[8] 費立凡，何津． 解決街道與建筑物圖形沖突的移位模型研究[J]. 武漢大學學報(信息科學版)，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三角網支持下的空間場表達[J]. 測繪學報, 2006, 35(1): 71-76.

[12] 趙仁亮.基于Voronoi圖的GIS空間關系計算[M].北京：測繪科學出版社, 2006.

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

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

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

[16] 陳軍，趙仁亮. GIS空間關系的基本問題與研究進展[J].測繪學報,1999,28(2):95-102.

[17] 喬慶華. 計算幾何基礎庫的建立及其在地圖自動綜合中的若干應用[D]. 武漢：武漢大學, 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] 劉遠剛，郭慶勝，孫雅庚，等. 地圖目標群間骨架線提取的算法研究[J]. 武漢大學學報(信息科學版) ,2015,40(2):264-268.

[20] 杜曉初，郭慶勝.基于Delaunay 三角網的空間鄰近關系推理[J].測繪科學，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] 劉遠剛，郭慶勝， 孫雅庚，等. 地圖自動綜合中Beams移位算法的實現(xiàn)與改進[J]. 武漢大學學報(信息科學版)，2016, 41(4): 450-454.

[責任編輯：張德福]

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

國家自然科學基金面上項目(41471384)；湖北省教育廳科學研究計劃指導性項目(B2015448)；地理信息工程國家重點實驗室開放基金課題資助(SKLGIE2016-Z-4-1)；長江大學大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(2016010)

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

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

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

10.19349/j.cnki.issn1006-7949.2017.08.003

P208

A

1006-7949(2017)08-0010-04