地圖矢量數據拓撲關系生成算法

徐 立，孫 群，楊 帥，徐 振

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

地圖矢量數據拓撲關系生成算法

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

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

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

拓撲元素；拓撲關系；線要素互相交斷鏈；結點匹配；多邊形追蹤

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

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

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

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

（2）弧段。兩結點間的有向線段稱為弧段［3］。弧段一般都具有實際意義，如道路、管線和面狀河流湖泊的邊線等；但在某些特殊情況下也可能沒有實際意義，如面狀要素的強制閉合線。在弧段的定義中，弧段是帶有方向性的，但其對應的空間要素可能并沒有方向性，如一般的公路（單車道公路除外）沒有方向性。方向對于用來構建面域的弧段是有作用的，圖1中湖泊a的邊線是順時針方向，島嶼b的邊線是逆時針方向，在計算湖泊面積時，島嶼b的面積會出現負值。

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

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

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

2 算法的主要步驟

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

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

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

2.1 線要素互相交斷鏈

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

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

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

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

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

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

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

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

2.2 結點與弧段間關系的建立

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

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

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

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

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

2.3 弧段與多邊形間關系的建立

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

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

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

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

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

3 實驗分析

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

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

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

表1中，交通層數據主要用來生成道路拓撲網，算法的耗時與參加拓撲的弧段總數呈正相關，因此實驗主要對比兩種算法建立結點與弧段間關系的效率。可以看出，當弧段總數較小時，兩種算法的時間相差不大；但隨著弧段總數的增加，兩種算法的時間差越來越大，說明在大數據量情況下，本文算法能夠明顯減少拓撲關系生成的時間。

表2中，由于不需要對居民地數據進行線要素互相交斷鏈處理，算法的耗時與參加拓撲的面域總數呈正相關，因此實驗主要對比兩種算法追蹤多邊形的效率。可以看出，隨著面域總數的增加，兩種算法的時間差不斷增大；但當面域總數增至一定數量時，兩者的時間差比較穩定，但本文算法的效率一直優于傳統算法。

4 結論

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

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

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

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

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

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

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

［7］ 李麗麗.基于拓撲關系的導航電子地圖增量更新關鍵技術研究［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－），男，博士研究生，主要研究領域是空間數據模型和數字制圖技術。E－mail：xuli＿1985＠yeah.net