徐 立，孫 群，楊 帥，徐 振

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

地圖矢量數(shù)據(jù)拓撲關(guān)系生成算法

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

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

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

拓撲元素；拓撲關(guān)系；線要素互相交斷鏈；結(jié)點匹配；多邊形追蹤

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

1 拓撲元素的分類及地理意義

拓撲元素與空間要素并不是一一對應的關(guān)系。按照拓撲學原理，地圖要素中的拓撲元素主要有3種基本類型：結(jié)點、弧段和面域［2］。

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

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

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

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

依據(jù)以上不同拓撲元素的地理意義，可以在拓撲數(shù)據(jù)預處理時自動篩選需要參加拓撲的元素。

2 算法的主要步驟

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

在地圖矢量數(shù)據(jù)中，只是部分要素層的部分要素需要參加拓撲，以1∶25萬地形圖的居民地層為例，只有由面屬性決定的邊線、圖邊強制閉合線、圖幅內(nèi)強制閉合線和街區(qū)邊線需要參加拓撲［5］。因此在拓撲關(guān)系構(gòu)建前，需要建立一個拓撲控制表，依據(jù)該表對初始數(shù)據(jù)進行篩選，以確定需要參加拓撲的要素。每個參加拓撲的要素層必須包含相應的拓撲控制表，每個參加拓撲的要素必須包含編碼信息和精度等級信息。每種要素（以編碼區(qū)分）都有一個精度等級，如省道比一般的縣道等級高，在進行結(jié)點匹配時，若省道相關(guān)的結(jié)點與附近縣道相關(guān)的結(jié)點在空間位置上發(fā)生沖突，則以省道相關(guān)的結(jié)點坐標為準。

圖2 拓撲算法處理流程Fig.2 The process of the topological algorithm

2.1 線要素互相交斷鏈

在采集地圖數(shù)據(jù)時，為節(jié)省時間，可能將幾條相連的弧段作為一條線要素輸入，這樣可能導致弧段之間相交。這種情況是不允許的，因為在弧段的定義中規(guī)定：弧段之間除了結(jié)點外不能有其它的公共點［6］。因此，需要對參加拓撲的線要素進行互相交斷鏈處理。

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

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

2.1.2 線要素間的互相交斷鏈 線要素格網(wǎng)索引建立完畢后，針對每個格網(wǎng)中的線要素進行互相交斷鏈處理，算法如下：設網(wǎng)格線要素鏈表為Link，任意線要素為Li，n為Link包含的線要素個數(shù)，從鏈表Link中取出第一個線要素，并設置為當前要素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標記為已求交，并依次取出Li中包含的線段，求出它們與L的交點。若其中一條線段Li與L產(chǎn)生交點，將Li標記為已求交，如圖3所示：L與Li中的線段AB相交，產(chǎn)生交點P1、P2、P3。對于其它特殊情況還需另行處理：如圖4中交點P1剛好與折線L的端點重合，此時生成3個線要素；根據(jù)交點對應于Li中的線段號，將交點重新排序為：P1、P2、P3。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

本文以1∶25萬濟寧市地形圖的交通層和居民地層為實驗數(shù)據(jù)，采用逐步增加拓撲要素的方法比較了傳統(tǒng)拓撲關(guān)系生成算法和本文拓撲關(guān)系生成算法在執(zhí)行效率上的差異，結(jié)果如表1、表2所示。

表1 交通層拓撲生成實驗Table 1 Topological data generation for traffic layer

表2 居民地層拓撲生成實驗Table 2 Topological data generation for habitation layer

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

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

4 結(jié)論

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

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

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

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

［4］ 陳春，張樹文，徐佳芬.GIS中多邊形圖拓撲信息生成的數(shù)學基礎(chǔ)［J］.測繪學報，1996，3（4）：266－271.

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

［6］ 程雙偉.GIS中拓撲關(guān)系的建立與更新［D］.信息工程大學，2002.16.

［7］ 李麗麗.基于拓撲關(guān)系的導航電子地圖增量更新關(guān)鍵技術(shù)研究［D］.吉林大學，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

國家自然科學基金項目（41071297）

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