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

柳華橋，舒賓，周義軍

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

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

柳華橋?，舒賓，周義軍

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

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

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

1 引 言

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

2 相關(guān)概念

2.1 Delaunay三角網(wǎng)

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

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

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

2.2 結(jié)點(diǎn)領(lǐng)域

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

如果結(jié)點(diǎn)在點(diǎn)集的凸殼邊線上，那么，取凸殼和Voronoi圖的相交部分的面積作為結(jié)點(diǎn)的領(lǐng)域，因?yàn)橹豢紤]結(jié)點(diǎn)占據(jù)點(diǎn)集內(nèi)部空間的面積，而不涉及點(diǎn)集的外部空間。

在空間中，結(jié)點(diǎn)領(lǐng)域越大，那么，結(jié)點(diǎn)的空間重要性就越大。

2.3 生命周期

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

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

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

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

2.4 空間聚類

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

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

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

3.1 設(shè)定興趣點(diǎn)的生命周期，確定綜合所需點(diǎn)集

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

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

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

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

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

圖2 Delaunay三角網(wǎng)

3.3 求得興趣點(diǎn)的領(lǐng)域

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

3.4 空間聚類

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

輸入:三角形集D。

輸出:興趣點(diǎn)集P1，P2，P3，……，Pn

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

步2:取三角形集D中剩余的任意一個(gè)三角形X，X∈D。如圖3所示，三角形X的三個(gè)頂點(diǎn)為A，B，C。計(jì)算三角形X的三邊長(zhǎng)度S1，S2，S3。

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

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

圖3 三角形X

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

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

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

步7:針對(duì)每個(gè)三角形子集，去掉重復(fù)的三角形頂點(diǎn)，得到興趣點(diǎn)子集P1，P2，P3，…，Pn。

3.5 處理各個(gè)興趣點(diǎn)子集

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

輸入:興趣點(diǎn)集P1，P2，P3，…，Pn。

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

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

步2:取Px中的一點(diǎn)S，點(diǎn)S的領(lǐng)域在子集Px中的最大。以點(diǎn)S初始化Pend={S}。

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

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

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

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

圖5 綜合結(jié)果

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

4 結(jié) 論

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

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

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

[3] 閆浩文，王家耀.基于Voronoi圖的點(diǎn)群目標(biāo)普適綜合算法[J].中國圖象圖形學(xué)報(bào)，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ù)表達(dá)的生命期模型[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2010 35(7):756～762.

[6] 普雷帕拉塔FP，沙莫斯MI.計(jì)算幾何[M].北京:北京科學(xué)出版社，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] 孫家廣，楊長(zhǎng)貴.計(jì)算機(jī)圖形學(xué)[M].北京:清華大學(xué)出版社，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—)，男，工程師，注冊(cè)測(cè)繪師，主要從事工程測(cè)量、地理信息系統(tǒng)等方面的工作。