基于Delaunay三角網(wǎng)的跨比例尺點要素綜合算法

柳華橋，舒賓，周義軍

(天津市測繪院，天津 300381)

基于Delaunay三角網(wǎng)的跨比例尺點要素綜合算法

柳華橋?，舒賓，周義軍

(天津市測繪院，天津 300381)

隨著網(wǎng)絡地圖的興起以及地理信息在各行業(yè)中的應用，興趣點已經(jīng)成為地理信息應用中不可或缺的一類要素，在地理信息應用中起到越來越重要的作用。但隨之而來的，跨比例尺間的興趣點取舍問題卻成為地理信息應用中的一個難點。提出一種基于Delaunay三角網(wǎng)的跨比例尺點要素綜合算法，結(jié)合空間和屬性特征解決了跨比例尺興趣點的取舍問題。

地圖綜合；Delaunay三角網(wǎng)；結(jié)點領域；空間聚類；生命周期

1 引 言

隨著網(wǎng)絡地圖的廣泛應用，興趣點在地理信息應用中起到越來越重要的作用，而興趣點的綜合也成為地理信息應用中的一個難點。在跨比例尺時，考慮到點重要性程度的情況，興趣點的取舍更加復雜?，F(xiàn)有的點要素綜合算法有基于遺傳算法的點群目標選取模型，基于Voronoi圖的點群目標普適綜合算法等?；谶z傳算法的點綜合算法是先自適應分類，在每個子點群中利用凸殼化簡方法進行選取[2]，此種算法具有分治的思想，有自適應能力，但算法中沒有考慮到屬性加權(quán)的情況；基于Voronoi圖的點綜合算法考慮拓撲信息，相應的改進算法也考慮了點重要性程度[3]，但此算法選取標準一成不變，對子點群不能區(qū)別對待，缺少自適應性，改進的算法中反復構(gòu)造Voronoi圖效率較低。本文在原有算法的基礎上，提出一種基于Delaunay三角網(wǎng)的跨比例尺點要素綜合算法，兼容已有算法的優(yōu)點，摒棄已有算法的缺點。

2 相關概念

2.1 Delaunay三角網(wǎng)

1908年，俄國數(shù)學家M.G.Voronoi首先在數(shù)學上限定了每個離散點數(shù)據(jù)的有效作用范圍，并定義了二維平面上的Voronoi圖。1934年，俄國數(shù)學家B.Delaunay由Voronoi圖演化出了更易于分析應用的Delaunay三角網(wǎng)[6]。

Delaunay三角網(wǎng)具有最大最小角特性和空外接圓特性，即任意三角形的外接圓不包含其他結(jié)點，這使它最大限度地避免了尖銳內(nèi)角的出現(xiàn)。在地圖綜合種可利用該模型進行目標間鄰近關系的搜索和沖突探測[1]，另外，Delaunay三角網(wǎng)外圍邊界構(gòu)建的是一個凸殼，且三角網(wǎng)的對偶圖形為Voronoi圖，這兩個性質(zhì)也可在地圖綜合算法設計中進行利用，如圖1所示。

圖1 Delaunay三角網(wǎng)、Voronoi圖

2.2 結(jié)點領域

Delaunay三角網(wǎng)的對偶圖為Voronoi圖，也即Voronoi圖中的每個單元內(nèi)有且只包含一個結(jié)點，那么，我們定義此單元為包含結(jié)點的領域，用單元的面積度量結(jié)點領域的大小，面積越大，結(jié)點領域越大。

如果結(jié)點在點集的凸殼邊線上，那么，取凸殼和Voronoi圖的相交部分的面積作為結(jié)點的領域，因為只考慮結(jié)點占據(jù)點集內(nèi)部空間的面積，而不涉及點集的外部空間。

在空間中，結(jié)點領域越大，那么，結(jié)點的空間重要性就越大。

2.3 生命周期

在地圖表達空間中，每一個空間實體存在的尺度范圍都是有限的[4]，以獨立地物中的報刊亭為例，在大比例尺如1∶500地形圖中，以點的形式表達，在小比例尺如1∶25萬地形圖中則不表達。空間數(shù)據(jù)在尺度上的展示，猶如自然生命一樣，有出生也有死亡，也即擁有生命周期。

我們借用自然生命的生命周期的概念，定義空間數(shù)據(jù)的生命周期L為:

其中S0為起始比例尺，Sn為終止比例尺。

那么，興趣點在生命周期內(nèi)作為選取目標考慮，在生命周期外則不予考慮。

2.4 空間聚類

空間聚類是將空間對象幾何劃分為由相似對象組成的多個簇的過程。同簇內(nèi)的對象之間具有盡可能大的相似性，而不同簇的對象之間則具有較大的差異性，從而有助于人們認識現(xiàn)象的整體分布模式。在GIS研究中，學者們將計算幾何、圖論方法與傳統(tǒng)的聚類分析方法結(jié)合衍生出了面向空間目標的空間聚類方法。本文將利用Delaunay三角網(wǎng)的特性進行空間聚類。

3 本算法的實現(xiàn)步驟

地理要素的制圖綜合涉及兩方面的內(nèi)容，一是空間位置的綜合，實際表現(xiàn)為圖形上的縮減；二是屬性方面的綜合，實際表現(xiàn)在語義方面的縮減，在地理信息數(shù)據(jù)模型中，屬性以屬性項的方式輔助圖形上的縮減。本算法綜合考慮這兩方面的內(nèi)容，基于Delaunay三角網(wǎng)的特性設計出能夠應用于跨比例尺的點要素綜合的算法，算法步驟如下。

3.1 設定興趣點的生命周期，確定綜合所需點集

確定綜合目標點集是綜合算法的第一步，本文先從屬性方面入手，通過設定點的生命周期，從語義上剔除不需進行圖形縮減的興趣點。

首先，根據(jù)地物的重要性和項目的具體需求，設置興趣點的生命周期，例如，獨立地物點中，報刊亭的生命周期L1=[1/100，1/1萬]，即報刊亭的存在于1∶100比例尺到1∶1萬比例尺之間；三甲醫(yī)院的生命周期L2=[1/100，1/25萬]。

其次，根據(jù)綜合前后的比例尺，對照各類興趣點的生命周期，選取需要綜合的興趣點集。

3.2 建立Delaunay三角網(wǎng)

如圖2所示，對3.1所得的興趣點集，建立Delaunay三角網(wǎng)，本文采用了掃描線算法[7]生成Delaunay三角網(wǎng)。

圖2 Delaunay三角網(wǎng)

3.3 求得興趣點的領域

根據(jù)結(jié)點領域的定義，通過Delaunay三角網(wǎng)求得對偶圖形Voronoi圖，得到Voronoi圖的每個單元的面積，并將面積付給單元內(nèi)的結(jié)點。

3.4 空間聚類

根據(jù)國家相關標準和綜合項目要求，確定兩興趣點間的最短距離為minD，依據(jù)Delaunay的特性，先將三角形進行聚類后，再通過三角形的聚類子集求得興趣點子集。

輸入:三角形集D。

輸出:興趣點集P1，P2，P3，……，Pn

步1:取三角形集D中的一個三角形，此三角形三邊長度都小于等于min D或只有一邊長度大于min D，以此三角形作為三角形子集D1。

步2:取三角形集D中剩余的任意一個三角形X，X∈D。如圖3所示，三角形X的三個頂點為A，B，C。計算三角形X的三邊長度S1，S2，S3。

步3:循環(huán)所有三角形子集{D1，…，Dn}，針對每個三角形子集Dm，m∈{1，...，n}，判斷Dm中是否存在三角形X的相接三角形。如果存在，轉(zhuǎn)到步4。如果所有三角形子集中都不存在三角形X的相接三角形。那么，新增三角形子集Dn+1={X}。

步4:三角形子集Dm中存在三角形X的相接三角形。如圖3所示，如果三角形X的三邊長度都小于等于min D或只有一邊長度大于min D，那么，將三角形X加入到三角形子集Dm中，否則，新增三角形子集Dn+1={X}。

圖3 三角形X

步5:轉(zhuǎn)到步2，直到三角形集D中所有符合條件的三角形都被取過為止。

步6:得到三角形子集D1，D2，…，Dn。如圖4所示的畫紅杠的三角形被刪除后，得到三個三角形子集。

圖4 三角網(wǎng)聚類

步7:針對每個三角形子集，去掉重復的三角形頂點，得到興趣點子集P1，P2，P3，…，Pn。

3.5 處理各個興趣點子集

取興趣點子集PX，X∈{1，...，n}，則綜合的結(jié)果應為子集PX的一個子集Pend，并且Pend中任意兩點之間的距離都大于min D。步驟如下:

輸入:興趣點集P1，P2，P3，…，Pn。

輸出:綜合結(jié)果興趣點集P。

步1:取興趣點子集PX，X∈{1，...，n}。

步2:取Px中的一點S，點S的領域在子集Px中的最大。以點S初始化Pend={S}。

步3:取Px的任意一點M，M∈Px且M∈Pend。如果點M到Pend中的任意一點的距離都大于min D，那么，將點S加入到Pend中。否則進行下一步。

步4:轉(zhuǎn)到步3，直到PX中所有符合條件的點都被取到。

步5:得到子集Px的一個子集Pend，將Pend中的點加入到綜合結(jié)果興趣點集P中。

步6:轉(zhuǎn)到步1，直到所有的興趣點集都被取到。步7:得到綜合結(jié)果興趣點集P，如圖5所示。

圖5 綜合結(jié)果

在步3中，計算M到Pend中的任意一點的距離，可以通過屬性對距離進行加權(quán)。例如，醫(yī)院和學校之間D，在加權(quán)后為1.2?D再與min D進行比較，這樣既考慮了空間方面的制約，又考慮了屬性方面的影響，在此子集范圍內(nèi)能夠做到一定程度的自適應。

4 結(jié) 論

本文根據(jù)興趣點要素的特點，先從屬性入手，應用生命周期概念，對興趣點進行初步篩選，然后，通過建立Delaunay三角網(wǎng)，得到結(jié)點領域，進行空間聚類，將興趣點按照空間鄰近性分類一個個點集，之后，針對各個點集，以其中結(jié)點領域最大的點為起點，集合空間位置和屬性兩方面的信息，處理各個點集，得到最終結(jié)果。本文所提的算法，既考慮了興趣點的全局分部特征，又針對局部進行區(qū)別對待；既考慮了點的空間位置的重要性，又考慮了屬性信息的影響，并且，本算法中的步驟大部分都是應用Delaunay三角網(wǎng)的特性，相對反復構(gòu)造Voronoi圖來說，效率有所提高。

[1] 艾廷華，郭仁忠，陳曉東.Delaunay三角網(wǎng)支持下的多邊形化簡與合并[J].中國圖象圖形學報，2001，6(7):707～709.

[2] 鄧紅艷，武芳，錢海忠等.基于遺傳算法的點群目標選取模型[J].中國圖象圖形學報，2003(8):133～135.

[3] 閆浩文，王家耀.基于Voronoi圖的點群目標普適綜合算法[J].中國圖象圖形學報，2005(5):665～668.

[4] Cecconi A.Integration of Cartographic Generalization and Multi-Scale Databases for Enhanced Web Mapping[D]. Zurich:University of Zurich，2003.

[5] 艾廷華，李靜忠.尺度空間中GIS數(shù)據(jù)表達的生命期模型[J].武漢大學學報·信息科學版，2010 35(7):756～762.

[6] 普雷帕拉塔FP，沙莫斯MI.計算幾何[M].北京:北京科學出版社，1992.

[7] V.Domiter，B.Zalik.Sweep-line algorithm for constrained Delaunay triangulation[J].International Journal of Geographical Information Science，2008，22(4):449～462.

[8] 孫家廣，楊長貴.計算機圖形學[M].北京:清華大學出版社，2000.

M ulti-scale M ap Generalization Algorithm of Point Feature Based on Delaunay Triangulation

Liu Huaqiao，Shu Bin，Zhou Yijun
(Tianjin Institute of Surveying and Mapping，Tianjin 300381，China)

With the rise of the network map，and geographic information applications in various industries，interest points has become an integral part of the geographic information features and play an increasingly important role in the geographic information application.But the ensuing cross-scale interest point trade-off has become a difficult geographic information applications.This paper presents a delaunay triangulation-based cross-scale point feature algorithm combining spatial and attribute characteristics to solve the problem of cross-scale interest point of the trade-offs.

map generalization；delaunay triangular；node domain；spatial clustering；life period

1672-8262(2013)04-42-03

P208.1，P209

B

2012—11—22

柳華橋(1980—)，男，工程師，注冊測繪師，主要從事工程測量、地理信息系統(tǒng)等方面的工作。