地圖矢量數(shù)據(jù)拓?fù)潢P(guān)系生成算法

徐 立，孫 群，楊 帥，徐 振

（1.信息工程大學(xué)測繪學(xué)院，河南鄭州450052；2.北京大學(xué)地球與空間科學(xué)學(xué)院，北京100871；3.66240部隊，北京100042）

地圖矢量數(shù)據(jù)拓?fù)潢P(guān)系生成算法

徐 立1，孫 群1，楊 帥2，徐 振3

（1.信息工程大學(xué)測繪學(xué)院，河南鄭州450052；2.北京大學(xué)地球與空間科學(xué)學(xué)院，北京100871；3.66240部隊，北京100042）

拓?fù)潢P(guān)系的建立是地圖矢量數(shù)據(jù)管理和更新的重要內(nèi)容。在綜合多種典型拓?fù)渌惴▋?yōu)點(diǎn)的基礎(chǔ)上，詳細(xì)描述了拓?fù)潢P(guān)系生成算法的主要過程，并在線要素互相交斷鏈、結(jié)點(diǎn)匹配和特殊情況處理等方面對算法進(jìn)行了改進(jìn)。最后以1∶25萬濟(jì)寧市地形圖數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)，結(jié)果表明該算法在效率方面優(yōu)于傳統(tǒng)算法。

拓?fù)湓兀煌負(fù)潢P(guān)系；線要素互相交斷鏈；結(jié)點(diǎn)匹配；多邊形追蹤

地圖圖形數(shù)據(jù)的拓?fù)潢P(guān)系是對地圖矢量數(shù)據(jù)進(jìn)行空間查詢、分析和質(zhì)量檢查等操作的基礎(chǔ)［1］。拓?fù)潢P(guān)系生成算法主要包括3方面的內(nèi)容：線要素互相交斷鏈、結(jié)點(diǎn)與弧段間關(guān)系的建立、弧段與多邊形間關(guān)系的建立。在處理大量數(shù)據(jù)的情況下，傳統(tǒng)算法在線要素互相交斷鏈過程中效率會明顯降低；在建立結(jié)點(diǎn)與弧段間關(guān)系的過程中，傳統(tǒng)算法往往無法科學(xué)地匹配不同精度的結(jié)點(diǎn)；另外，由于地圖矢量數(shù)據(jù)較復(fù)雜，在建立弧段與多邊形間關(guān)系的過程中有時會出現(xiàn)一些特殊情況，傳統(tǒng)算法并沒有合理地處理這些特殊情況。針對以上不足，結(jié)合現(xiàn)有地圖矢量數(shù)據(jù)的特點(diǎn)，本文對傳統(tǒng)的地圖矢量關(guān)系生成算法做出了相應(yīng)的改進(jìn)。

1 拓?fù)湓氐姆诸惣暗乩硪饬x

拓?fù)湓嘏c空間要素并不是一一對應(yīng)的關(guān)系。按照拓?fù)鋵W(xué)原理，地圖要素中的拓?fù)湓刂饕?種基本類型：結(jié)點(diǎn)、弧段和面域［2］。

（1）結(jié)點(diǎn)。兩條或兩條以上弧段的連接點(diǎn)稱為結(jié)點(diǎn)，一條閉合弧段的首尾接點(diǎn)或一條懸掛鏈的端點(diǎn)也可稱為結(jié)點(diǎn)［3］。結(jié)點(diǎn)可以有實(shí)際地理意義，如道路中的交叉口、橋梁和界碑等；也可以無實(shí)際地理意義，如湖泊邊線上的結(jié)點(diǎn)。

（2）弧段。兩結(jié)點(diǎn)間的有向線段稱為弧段［3］?；《我话愣季哂袑?shí)際意義，如道路、管線和面狀河流湖泊的邊線等；但在某些特殊情況下也可能沒有實(shí)際意義，如面狀要素的強(qiáng)制閉合線。在弧段的定義中，弧段是帶有方向性的，但其對應(yīng)的空間要素可能并沒有方向性，如一般的公路（單車道公路除外）沒有方向性。方向?qū)τ谟脕順?gòu)建面域的弧段是有作用的，圖1中湖泊a的邊線是順時針方向，島嶼b的邊線是逆時針方向，在計算湖泊面積時，島嶼b的面積會出現(xiàn)負(fù)值。

圖1 弧段的方向性Fig.1 Directions of the arcs

（3）面域。面域是指由一條或若干條弧段構(gòu)成的閉合多邊形［3］，每個面域都有一個內(nèi)點(diǎn)（面域內(nèi)的任意一點(diǎn)，承載面域的屬性信息）與之相對應(yīng)。絕大多數(shù)面域具有實(shí)際意義，如面狀河流與湖泊、行政區(qū)和面狀居民地等。

依據(jù)以上不同拓?fù)湓氐牡乩硪饬x，可以在拓?fù)鋽?shù)據(jù)預(yù)處理時自動篩選需要參加拓?fù)涞脑亍?/p>

2 算法的主要步驟

目前一般采用自動方式生成地圖數(shù)據(jù)拓?fù)潢P(guān)系，首先對需要參加拓?fù)涞臄?shù)據(jù)進(jìn)行預(yù)處理，再根據(jù)左轉(zhuǎn)算法（通過判斷鄰接弧間的內(nèi)角）和基于圖的理論確定拓?fù)潢P(guān)系［4］。拓?fù)潢P(guān)系處理流程如圖2所示。

在地圖矢量數(shù)據(jù)中，只是部分要素層的部分要素需要參加拓?fù)?，?∶25萬地形圖的居民地層為例，只有由面屬性決定的邊線、圖邊強(qiáng)制閉合線、圖幅內(nèi)強(qiáng)制閉合線和街區(qū)邊線需要參加拓?fù)洌?］。因此在拓?fù)潢P(guān)系構(gòu)建前，需要建立一個拓?fù)淇刂票?，依?jù)該表對初始數(shù)據(jù)進(jìn)行篩選，以確定需要參加拓?fù)涞囊?。每個參加拓?fù)涞囊貙颖仨毎鄳?yīng)的拓?fù)淇刂票?，每個參加拓?fù)涞囊乇仨毎幋a信息和精度等級信息。每種要素（以編碼區(qū)分）都有一個精度等級，如省道比一般的縣道等級高，在進(jìn)行結(jié)點(diǎn)匹配時，若省道相關(guān)的結(jié)點(diǎn)與附近縣道相關(guān)的結(jié)點(diǎn)在空間位置上發(fā)生沖突，則以省道相關(guān)的結(jié)點(diǎn)坐標(biāo)為準(zhǔn)。

圖2 拓?fù)渌惴ㄌ幚砹鞒蘁ig.2 The process of the topological algorithm

2.1 線要素互相交斷鏈

在采集地圖數(shù)據(jù)時，為節(jié)省時間，可能將幾條相連的弧段作為一條線要素輸入，這樣可能導(dǎo)致弧段之間相交。這種情況是不允許的，因?yàn)樵诨《蔚亩x中規(guī)定：弧段之間除了結(jié)點(diǎn)外不能有其它的公共點(diǎn)［6］。因此，需要對參加拓?fù)涞木€要素進(jìn)行互相交斷鏈處理。

2.1.1 線要素格網(wǎng)索引的建立 一幅地圖矢量數(shù)據(jù)中，線要素數(shù)量最多，若對所有參加拓?fù)涞木€要素兩兩求交，勢必降低算法效率。從全局角度考慮，大部分情況下線要素并不相交，這時可以將地圖區(qū)域分為M×N個矩形子區(qū)域。由于有可能出現(xiàn)相交點(diǎn)落在線段延長線上且交點(diǎn)在線段某端點(diǎn)附近的特殊情況，這時兩條線段實(shí)際上可能相交，但兩條線段卻又處于相鄰的兩個網(wǎng)格區(qū)域，則無法對兩條線段進(jìn)行相交處理，所以必須對網(wǎng)格進(jìn)行適當(dāng)?shù)耐鈹U(kuò)處理，所生成的網(wǎng)格寬度w和高度h公式如下：

其中：Xmax、Xmin、Ymax、Ymin為圖幅的外接范圍，D為結(jié)點(diǎn)匹配誤差，2D為網(wǎng)格擴(kuò)充的長度。

2.1.2 線要素間的互相交斷鏈 線要素格網(wǎng)索引建立完畢后，針對每個格網(wǎng)中的線要素進(jìn)行互相交斷鏈處理，算法如下：設(shè)網(wǎng)格線要素鏈表為Link，任意線要素為Li，n為Link包含的線要素個數(shù)，從鏈表Link中取出第一個線要素，并設(shè)置為當(dāng)前要素L；將線要素L依次與后面的線要素Li（1＜i≤n，i為整數(shù)）求交。

（1）判斷L是否已求交或是否有效，若已求交或無效，則轉(zhuǎn)入步驟3；判斷L的ID是否與Li的ID相同，若相同，則轉(zhuǎn)入步驟3；判斷L和Li的外接矩形是否相交，若不相交，則轉(zhuǎn)入步驟3。

（2）將L標(biāo)記為已求交，并依次取出Li中包含的線段，求出它們與L的交點(diǎn)。若其中一條線段Li與L產(chǎn)生交點(diǎn)，將Li標(biāo)記為已求交，如圖3所示：L與Li中的線段AB相交，產(chǎn)生交點(diǎn)P1、P2、P3。對于其它特殊情況還需另行處理：如圖4中交點(diǎn)P1剛好與折線L的端點(diǎn)重合，此時生成3個線要素；根據(jù)交點(diǎn)對應(yīng)于Li中的線段號，將交點(diǎn)重新排序?yàn)椋篜1、P2、P3。

（3）在Link中，取出當(dāng)前線要素的后一個線要素，若不為空，將該要素設(shè)為當(dāng)前要素L，轉(zhuǎn)入步驟2，反之轉(zhuǎn)入步驟4。

（4）建立新鏈表Link2，重新遍歷鏈表Link，若線要素有效，則將要素加入鏈表Link2，據(jù)此生成的新鏈表Link2即為線要素互相交斷鏈結(jié)果。

2.2 結(jié)點(diǎn)與弧段間關(guān)系的建立

線要素進(jìn)行互相交斷鏈處理生成的數(shù)據(jù)是孤立的弧段和結(jié)點(diǎn)，必須進(jìn)一步通過結(jié)點(diǎn)匹配的方法建立結(jié)點(diǎn)與弧段之間的關(guān)聯(lián)關(guān)系，同時也為弧段與多邊形間關(guān)系的建立奠定了數(shù)據(jù)基礎(chǔ)。

2.2.1 點(diǎn)要素格網(wǎng)索引的建立 建立結(jié)點(diǎn)與弧段間關(guān)系之前，除了要讀入?yún)⒓油負(fù)涞慕Y(jié)點(diǎn)要素（有實(shí)際意義的點(diǎn)狀要素），還需加入弧段的首、末結(jié)點(diǎn)［7］。這里將結(jié)點(diǎn)分為兩種類型：有實(shí)際地理意義的結(jié)點(diǎn)要素；沒有實(shí)際地理意義且屬于某一弧段的結(jié)點(diǎn)。類似于線要素的自相交斷鏈算法，為了提高算法效率，必須對結(jié)點(diǎn)要素建立網(wǎng)格索引，此過程中只需判斷結(jié)點(diǎn)是否落入特定的網(wǎng)格即可。另外，每個網(wǎng)格區(qū)域必須往外擴(kuò)張2D（D為結(jié)點(diǎn)匹配容差）大小的范圍，以防止相鄰網(wǎng)格間出現(xiàn)結(jié)點(diǎn)漏匹配的情況。

2.2.2 結(jié)點(diǎn)匹配 結(jié)點(diǎn)匹配主要有兩個作用：一是將距離在閾值D范圍內(nèi)的結(jié)點(diǎn)合并為一個點(diǎn)，當(dāng)所有結(jié)點(diǎn)的精度等級相同時，可將其平均位置設(shè)為新結(jié)點(diǎn)的位置，否則，將等級最高的結(jié)點(diǎn)的位置設(shè)為平均位置；二是生成弧段與結(jié)點(diǎn)之間的拓?fù)潢P(guān)系。由于每個索引網(wǎng)格采用的算法都一樣，所以下述結(jié)點(diǎn)匹配算法主要是針對單個索引網(wǎng)格，主要步驟如下：

（1）對網(wǎng)格內(nèi)所有的結(jié)點(diǎn)排序。首先在x方向上對結(jié)點(diǎn)排序，然后在y方向上對結(jié)點(diǎn)排序，則點(diǎn)位相近的結(jié)點(diǎn)排至一起，這時只需對排序后的結(jié)點(diǎn)進(jìn)行一次循環(huán)操作，便可找出位置相同或相近的結(jié)點(diǎn)，從而減少了比較次數(shù)。另外，對x和y兩個方向的結(jié)點(diǎn)進(jìn)行排序，可以避免結(jié)點(diǎn)間僅在某一方向距離很小而帶來的干擾。

（2）排序后結(jié)點(diǎn)的處理。1）從排序后的鏈表中取出第一個結(jié)點(diǎn)，并設(shè)為當(dāng)前結(jié)點(diǎn)。2）依次取出后面的結(jié)點(diǎn)，與當(dāng)前結(jié)點(diǎn)進(jìn)行比較，若后面結(jié)點(diǎn)不為空且兩點(diǎn)間的距離小于等于匹配限差D，則將兩結(jié)點(diǎn)作為一組；若兩點(diǎn)間的距離大于匹配限差D，則計算點(diǎn)組中的結(jié)點(diǎn)數(shù)，結(jié)點(diǎn)數(shù)大于1則轉(zhuǎn)入步驟3，反之轉(zhuǎn)入步驟5。3）找出點(diǎn)組中所有結(jié)點(diǎn)的關(guān)聯(lián)弧段，將其中的關(guān)聯(lián)結(jié)點(diǎn)（首結(jié)點(diǎn)或末結(jié)點(diǎn)）設(shè)為新結(jié)點(diǎn)P（X，Y），并將這些弧段設(shè)為新結(jié)點(diǎn)的關(guān)聯(lián)弧段。4）將點(diǎn)組中具有實(shí)際意義的結(jié)點(diǎn)坐標(biāo)設(shè)為（X，Y），刪除點(diǎn)組中沒有實(shí)際意義的結(jié)點(diǎn)。5）取出下一個未比較的結(jié)點(diǎn)，若該結(jié)點(diǎn)不為空，則將該結(jié)點(diǎn)設(shè)為當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)入步驟2；否則，結(jié)點(diǎn)與弧段的拓?fù)潢P(guān)系初步建立完畢，轉(zhuǎn)入步驟6。6）依次遍歷每個結(jié)點(diǎn)，將偽結(jié)點(diǎn)刪除。在地圖矢量數(shù)據(jù)中，若1個二鏈結(jié)點(diǎn)所關(guān)聯(lián)的兩條弧段屬性完全相同，那該結(jié)點(diǎn)為偽結(jié)點(diǎn)，即所關(guān)聯(lián)的兩條弧段可以合并成一條弧段；若1個二鏈結(jié)點(diǎn)所關(guān)聯(lián)的兩條弧段屬性部分相同，則該結(jié)點(diǎn)不是偽結(jié)點(diǎn)。例如，有一個結(jié)點(diǎn)A，在A處只連接瀝青路L1和水泥路L2，因L1和L2道路性質(zhì)不同，不能合并成一條道路，結(jié)點(diǎn)A則不是偽結(jié)點(diǎn)。偽結(jié)點(diǎn)的處理主要分為3步：將兩條關(guān)聯(lián)弧段合并為一條弧段；若結(jié)點(diǎn)有實(shí)際地理意義，則將結(jié)點(diǎn)修改為一般地理點(diǎn)要素，否則刪除該結(jié)點(diǎn)；刪除原來的弧段。

2.3 弧段與多邊形間關(guān)系的建立

弧段與多邊形關(guān)系的建立也稱為面域構(gòu)建，該過程是拓?fù)潢P(guān)系生成算法的最后階段，其主要作用是根據(jù)結(jié)點(diǎn)與弧段的關(guān)聯(lián)關(guān)系、多邊形與面域點(diǎn)的包含關(guān)系和多邊形之間的包含關(guān)系，生成簡單多邊形實(shí)體和復(fù)合多邊形實(shí)體（如含有多個島嶼的湖泊）。算法主要分為多邊形追蹤和面域點(diǎn)與多邊形關(guān)系的確定兩個過程，前者是根據(jù)結(jié)點(diǎn)與弧段間的關(guān)聯(lián)關(guān)系構(gòu)建多邊形，后者是在前者的基礎(chǔ)上確定面域點(diǎn)與多邊形的對應(yīng)關(guān)系。

2.3.1 多邊形追蹤 多邊形追蹤算法的基本思路是：首先以數(shù)據(jù)中任意一條弧段為初始弧段，以初始弧段的首結(jié)點(diǎn)或末結(jié)點(diǎn)為初始結(jié)點(diǎn)，找出初始結(jié)點(diǎn)的所有關(guān)聯(lián)弧段；然后以關(guān)聯(lián)弧段中方向角最小的弧段為后續(xù)弧段，并將后續(xù)弧段的另一端點(diǎn)作為后續(xù)結(jié)點(diǎn)，再以上述方法進(jìn)行循環(huán)追蹤，直至滿足追蹤條件，則停止本次追蹤。

對于大多數(shù)圖形而言，每個多邊形都可根據(jù)上述思想構(gòu)建，但必須考慮以下兩種特殊情況（圖5）：若以圖5a所示方向進(jìn)行多邊形｀追蹤，在結(jié)點(diǎn)A處可能存在一條閉合弧段b（單獨(dú)構(gòu)成一個多邊形），本次追蹤可能在A點(diǎn)提前結(jié)束；此時需要重新回到A點(diǎn)，刪除弧段b，以弧段c為后續(xù)弧段，繼續(xù)向下追蹤。以圖5b所示方向進(jìn)行多邊形追蹤，在結(jié)點(diǎn)A處下一個弧段是c，但是c以后的弧段都不能構(gòu)成多邊形，如果繼續(xù)向下追蹤，則會提前結(jié)束追蹤。此時追蹤的順序?yàn)椋合茸粉櫟交《蝑，發(fā)現(xiàn)沒有后續(xù)弧段，則退回至結(jié)點(diǎn)B；追蹤到弧段e，再次退回至結(jié)點(diǎn)B；然后繼續(xù)退回至結(jié)點(diǎn)A，直至構(gòu)成一個多邊形。

圖5 多邊形追蹤特殊情況Fig.5 The exceptive instances of polygon tracking

2.3.2 面域點(diǎn)與多邊形對應(yīng)關(guān)系的確定 面域點(diǎn)與多邊形之間可能存在多對多的關(guān)系，即一個面域點(diǎn)可能落入多個多邊形內(nèi)，一個多邊形可能包含多個面域點(diǎn)，所以必須確定面域點(diǎn)實(shí)際與哪個多邊形對應(yīng)，以保證面域點(diǎn)與多邊形之間的一對一關(guān)系，具體過程不再贅述。

3 實(shí)驗(yàn)分析

本文以1∶25萬濟(jì)寧市地形圖的交通層和居民地層為實(shí)驗(yàn)數(shù)據(jù)，采用逐步增加拓?fù)湟氐姆椒ū容^了傳統(tǒng)拓?fù)潢P(guān)系生成算法和本文拓?fù)潢P(guān)系生成算法在執(zhí)行效率上的差異，結(jié)果如表1、表2所示。

表1 交通層拓?fù)渖蓪?shí)驗(yàn)Table 1 Topological data generation for traffic layer

表2 居民地層拓?fù)渖蓪?shí)驗(yàn)Table 2 Topological data generation for habitation layer

表1中，交通層數(shù)據(jù)主要用來生成道路拓?fù)渚W(wǎng)，算法的耗時與參加拓?fù)涞幕《慰倲?shù)呈正相關(guān)，因此實(shí)驗(yàn)主要對比兩種算法建立結(jié)點(diǎn)與弧段間關(guān)系的效率?？梢钥闯觯?dāng)弧段總數(shù)較小時，兩種算法的時間相差不大；但隨著弧段總數(shù)的增加，兩種算法的時間差越來越大，說明在大數(shù)據(jù)量情況下，本文算法能夠明顯減少拓?fù)潢P(guān)系生成的時間。

表2中，由于不需要對居民地數(shù)據(jù)進(jìn)行線要素互相交斷鏈處理，算法的耗時與參加拓?fù)涞拿嬗蚩倲?shù)呈正相關(guān)，因此實(shí)驗(yàn)主要對比兩種算法追蹤多邊形的效率。可以看出，隨著面域總數(shù)的增加，兩種算法的時間差不斷增大；但當(dāng)面域總數(shù)增至一定數(shù)量時，兩者的時間差比較穩(wěn)定，但本文算法的效率一直優(yōu)于傳統(tǒng)算法。

4 結(jié)論

拓?fù)潢P(guān)系生成算法主要包括線要素互相交斷鏈、結(jié)點(diǎn)匹配和多邊形追蹤等子算法。本文對以下方面進(jìn)行了改進(jìn)：1）利用要素編碼控制表的形式篩選參加拓?fù)涞囊?，并對每類要素設(shè)置精度等級，使結(jié)點(diǎn)匹配時的點(diǎn)坐標(biāo)擬合更科學(xué)；2）根據(jù)屬性信息對偽結(jié)點(diǎn)進(jìn)行自動處理，對結(jié)點(diǎn)和弧段建立網(wǎng)格索引，提高了算法的運(yùn)行效率；3）對算法中出現(xiàn)的多種特殊情況進(jìn)行了處理，提高了算法的穩(wěn)定性。

［1］ 華一新，吳升，趙軍喜.地理信息系統(tǒng)原理與技術(shù)［M］.北京：解放軍出版社，2001.30.

［2］ 謝露蓉.地圖圖形數(shù)據(jù)拓?fù)潢P(guān)系的建立［J］.測繪科學(xué)，1999，3（2）：36－41.

［3］ 趙國成.基于Microstation的掃描矢量化軟件的研制［D］.信息工程大學(xué)，2004.53－54.

［4］ 陳春，張樹文，徐佳芬.GIS中多邊形圖拓?fù)湫畔⑸傻臄?shù)學(xué)基礎(chǔ)［J］.測繪學(xué)報，1996，3（4）：266－271.

［5］ 劉海硯.數(shù)字地圖制圖原理與技術(shù)［M］.北京：解放軍出版社，2006.62.

［6］ 程雙偉.GIS中拓?fù)潢P(guān)系的建立與更新［D］.信息工程大學(xué)，2002.16.

［7］ 李麗麗.基于拓?fù)潢P(guān)系的導(dǎo)航電子地圖增量更新關(guān)鍵技術(shù)研究［D］.吉林大學(xué)，2009.30－31.

Abstract：The establishment of topological relationship is essential to map vector data management and updating.Based on the advantages of multiple topological algorithm being integrated，the main process of topological was introduced detailedly.The topological algorithm was modified at the aspects of line feature intersecting，node matching and area building.Finally，an experiment was tried on the 1∶250 000 scale topographical map data for Jining.It indicated that the efficiency of topological algorithm could be improved compared to the traditional algorithm.

Key words：topological element；topological relationship；line feature intersecting；node matching；polygon tracking

Topological Algorithm for Map Vector Data

XU Li1，SUN Qun1，YANG Shuai2，XU Zhen3
（1.Institute of Surveying and Mapping，Information Engineering University，Zhengzhou 450052；2.School of Earth and Space Sciences，Peking University，Beijing 100871；3.66240 Troops，Beijing 100042，China）

P283

A

1672－0504（2012）04－0018－04

2012－01－07；

2012－03－12

國家自然科學(xué)基金項目（41071297）

徐立（1985－），男，博士研究生，主要研究領(lǐng)域是空間數(shù)據(jù)模型和數(shù)字制圖技術(shù)。E－mail：xuli＿1985＠yeah.net