面向矢量數據疊加分析的拓撲一致性處理研究

王 少 華,鐘 耳 順,李 紹 俊,3,盧 浩

(1.中國科學院地理科學與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國科學院大學，北京 100039)

?

面向矢量數據疊加分析的拓撲一致性處理研究

王 少 華1,2,鐘 耳 順1,李 紹 俊1,2,3,盧 浩2*

(1.中國科學院地理科學與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國科學院大學，北京 100039)

在疊加分析、緩沖區分析、拓撲分析等各種矢量數據分析過程中，首要面對的便是矢量數據拓撲一致性問題。拓撲一致性處理是對GIS矢量數據中由于采集、存儲、壓縮、轉換導致的空間拓撲關系不一致問題進行的拓撲處理,其使得待處理數據在容限范圍內具有拓撲一致性，從而便于后續相關分析功能的進行。該文在分析和總結已有拓撲一致性處理算法的基礎上，提出了一種更為高效的拓撲一致性處理改進算法，包括弧段間拓撲處理、節點與弧段間拓撲處理、節點間鄰近搜索等核心過程。對比實驗表明，該算法在保證拓撲一致性處理效果的基礎上具有較高的處理性能，是一種實用性較強的拓撲一致性處理算法。

矢量數據；疊加分析；均勻格網索引；拓撲一致性

0 引言

GIS中的疊加分析實質是地理信息圖層間的空間關系運算。由于受到數據精度的限制，在地理信息圖層疊加分析過程中，不同圖層間對象可能出現邊界線段不一致問題，極易造成疊加結果產生不符合規范的細碎多邊形,如不對其進行有效處理，將引起后續分析計算的異常[1]。因此在進行疊加分析計算時引入了容限概念，從而在矢量數據幾何計算中修正與維護數據的拓撲一致性。但單純通過高精度節點捕捉低精度節點的處理方式很難從根本上避免和消除所有的拓撲不一致情況，因此一種較為系統的解決方案就顯得尤為重要。

在拓撲一致性處理和疊加分析過程中存在著大量的計算幾何運算，而基于計算幾何的算法實現過程主要面臨兩個挑戰：一是計算機在進行數值計算時不可避免的數值精度誤差[2]。例如計算幾何中經常需要判斷點和線段的空間位置關系，在通過求算線段方程判斷時，對方程結果是否為零的判斷極易出現求算結果略大或略小于零的情況，導致判斷失效。程序計算時的精度損失引起的誤差一般通過兩種方法解決，第一種方法是在中間計算過程中提高表達精度，進行盡可能的“精確”計算[3]，第二種方法是設定對象間的“容限”使得計算結果都在容限范圍內[2]。另一種挑戰稱之為表達誤差，由于矢量數據的本質是真實地物對象的映射和模擬，因此在生產矢量數據的過程中不可避免地會引入表達誤差，即矢量數據和真實情況的偏移，或稱之為矢量數據的不確定性，這種誤差同樣會導致疊加計算過程出現細碎多邊形等異常情況。現有算法中主要通過一種稱為“epsilon geometry/tolerance”[4,5]的方法來處理表達誤差，即主要通過對待處理數據的規范化來避免誤差，且通過“epsilon geometry/tolerance”這一框架，可同時處理數值精度誤差和表達誤差問題[6,7]。

Milenkovic針對以上問題提出了數據規范化(data normalization)[8]，其解決思路是在計算分析之前對數據進行預處理，用以糾正所存在的拓撲不一致問題。Pullar提出了一種效果較好的解決方案[9]，稱之為地圖調整(map accommodation)過程,該方法基于Milenkovic算法的思路進行數據調整，但為了避免Milenkovic算法存在的問題，在節點捕捉過程中引入聚類分析的概念。通過對待捕捉的節點進行整體的聚類分析達到改進拓撲一致性捕捉效果的目的，同時也可以通過在聚類分析中增加限制條件，解決多次移動導致的節點偏移過大問題。Harvey等提出了一種控制更加嚴格的以節點移動為主要方法的拓撲一致性處理算法[10]，該算法主要基于聚類分析實現，通過近似的啟發式算法選擇節點，要求用戶先選擇一個數據集中的節點，而后自動調整另一個數據集中的節點與之匹配。ArcGIS的處理模式[11]整體上和Pullar算法接近，且Pullar算法中提及的需要迭代多次操作的情況在ArcGIS中也有體現。

1 拓撲一致性處理改進算法

針對已有的拓撲一致性處理算法存在的不足，本文提出一種性能較優的拓撲一致性處理改進算法，并對算法核心數據結構以及弧段間拓撲處理、節點與弧段間拓撲處理、節點間鄰近搜索3個核心處理過程進行詳細闡述。

1.1 核心數據結構

(1)均勻格網索引信息結構。在對待處理數據中需進行拓撲一致性處理的各種情況進行搜索查詢時，由于均勻格網索引結構實現簡單且能有效提升查詢性能[12]，因此，本文使用均勻格網索引結構建立空間數據索引，其核心數據結構主要包括以下3個組成部分：

structTopoGridInfo

{

IntnSegmentCount;

TSegmentInfo*pSegmentUnit;

};

structTSegmentInfo

{

IntnDTIndex;

IntnObjIndex;

IntnPntIndex;

IntnPntPos;

};

ArrayPnts

其中：TopoGridInfo為基礎的均勻網格索引結構單元結構體，整數類型nSegmentCount記錄此網格索引單元中索引的節點(或弧段)數目；TSegmentInfo為基本索引信息結構，其由4個Int型整數構成，其中nDTIndex記錄圖層索引值，nObjIndex記錄該圖層中的對象索引值，nPntIndex記錄該對象中的節點索引值(當針對弧段建立索引時，即記錄弧段的起始節點索引值)，nPntPos記錄該節點的索引節點數組Pnts中的位置，數組長度為nPntCount；pSegmentUnit是一個TSegmentInfo類型的指針數組，該指針指向網格索引單元中具體索引的空間數據信息。經過均勻格網索引建立過程后，空間數據中的節點都存儲在索引節點數組Pnts中，同時被均勻格網索引單元結構TopoGridInfo管理；而整體的索引結構為單元結構的數組，數組數目即格網索引行數和列數的乘積：

TopoGridInfo*pTopoGridInfo=

newTopoGridInfo[nGridRows*nGridCols]

其中:nGridRows為格網索引行數目，nGridCols為格網索引列數目，行列數目根據待處理數據規模確定。整體索引結構如圖1所示。

圖1 索引核心結構示意

Fig.1Indexcorestructurediagram

(2)數據調整信息數據結構。為支持多圖層間的拓撲一致性處理，本文設計了一種較為簡潔統一的數據結構來存儲各圖層中數據對象需要進行調整的信息，核心數據結構為一個結構體和節點數組：

struct TopoUnitNodeInfo

{

Array nIntersetPntIndex;

Array nIntersetPntPos;

};

ArrayIntersetPnts

每個結構體TopoUnitNodeInfo對應一個待調整的空間對象，nIntersetPntIndex記錄該對象需要調整的節點索引(或需要進行節點插入的弧段起始節點索引)，nIntersetPntIndex記錄該節點所需調整的坐標在節點數組中的位置，即IntersetPnts中記錄的調整結果節點數組的索引。由于拓撲一致性處理方法需支持多圖層多對象的處理，因此算法中使用的結構為：

VectorparrTopoUnitNodes

parrTopoUnitNodes長度為所需處理的圖層數目，每個圖層需要根據其對象數目nObjCount申請所需的內存。

TopoUnitNodeInfo*pTopoUnitNodeInfo=new TopoUnitNodeInfo[nObjCount]

1.2 弧段間拓撲處理

弧段間拓撲處理過程主要是進行弧段與弧段拓撲關系的判別，以及對不滿足弧段與弧段間拓撲關系的數據進行修正和維護。當兩弧段位置關系出現類似“十字”形的相交情況時，需在兩弧段的相交處各插入一個節點，即弧段間的相交情況只允許出現在弧段的起始或終止端點處。此過程基本對應于Pullar算法中的弧段相交情況，但由于Pullar算法中弧段相交過程新增的節點有可能存在和其它弧段造成的二次修正情況，因此把該過程放在第一個流程進行處理，使得新增節點可能導致的和其它弧段或者節點距離小于容限的情況在后續過程中依次進行修正，避免了多次迭代修正的問題。

整體處理過程可以劃分為檢測和修復兩大過程，在檢測過程中則對拓撲處理的各圖層數據進行遍歷查詢。通過建立均勻格網索引結構提升弧段間關系判定效率，在建立索引后，依次遍歷所有格網索引結構，在一個或周邊多個格網范圍內進行弧段間相交情況的判定。應注意：當出現兩弧段交點距某一弧段起始或終止節點距離在容限范圍內的情況時，則此節點不需要插入到兩弧段中，而是在后續的節點與弧段拓撲處理過程中進行處理。

如圖2所示，弧段L1L2和L3L4相交于點P，但由于點P距離節點L3小于節點容限，因此此時點P不被插入到弧段L1L2和L3L4當中，而將此情況在后面的節點與弧段間拓撲處理過程進行處理。整體處理流程如下：1) 依次遍歷矢量數據圖層，取出每個對象，根據對象每條弧段位置建立網格索引，索引中記錄弧段所屬的數據集ID、對象ID、節點索引值等信息，并將所有弧段中節點統一存儲到一個節點數組中(相鄰兩弧段共用的起始終止節點只需存儲一次)。2) 索引建立后，遍歷所有索引格網，依次取出每個單元格內的弧段，并將此弧段和格網內其它弧段進行相交計算。需注意：如果兩弧段交點不在此網格內，則不記錄，將此情況交由交點所在網格處理，防止重復記錄插入交點。3) 相交計算結束后，按照相交計算記錄的交點信息，進行交點插入處理。需注意：當對象某一弧段需添加多個節點時，對新添加的節點排序，根據排序后的順序添加交點。

圖2 弧段間拓撲處理特殊情況

Fig.2Specialcasesofarcstopologyconsistencyprocess

1.3 節點與弧段間拓撲處理

在節點與弧段間拓撲處理過程中主要是判別節點與弧段的拓撲關系，以及對于不滿足節點與弧段拓撲關系的數據進行修正和維護，即當節點距某弧段距離小于容限時，需在弧段上添加此節點的垂足。此過程基本對應于Pullar算法中的弧段插點過程，但由于Pullar算法流程中弧段插點過程理論上存在和其它弧段造成的二次修正情況，因此把該過程放在第二流程進行處理，修正過程由第三過程完成。

整體處理過程同樣可以劃分為檢測和修復兩大過程，在檢測過程中遍歷數據，通過建立均勻格網索引結構提升后續判定速度，在索引建立后，則依次遍歷所有格網，在一個或周邊多個格網范圍內判定節點和鄰近弧段的距離。需注意：當出現節點到弧段端點距離小于容限情況時，則無論節點與弧段的距離為多少都不進行插入，而當出現節點到弧段端點距離大于容限，但節點的垂足到弧段端點距離小于容限的情況時，則此垂足點也需插入到弧段中，此情況會在后續的節點間鄰近搜索過程中進行處理。

如圖3所示，以弧段v1v2為例進行節點與弧段拓撲處理的說明，當節點v距弧段左右兩端點v1或v2的距離小于容限，即位于圖3中左右端A區域時，無需進行處理，此情況會在后續的節點間鄰近搜索中處理。當節點v距弧段端點距離大于容限，但距弧段距離小于容限，即位于圖3中C區域時，需要計算節點v到弧段的垂足點，并將此垂足點插入弧段中。有一種特殊情況需要注意：當節點v距弧段端點距離大于容限，但垂足點到弧段端點距離小于容限時，即圖3中4個B區域，此時仍需將垂足點插入到弧段中，且后續節點間鄰近搜索會處理此特殊情況。整體處理流程如下：1) 依次遍歷矢量數據集圖層，取出每個對象，將其節點和線段建立網格索引，并將所有節點存儲到一個節點數組中。使用兩個網格索引結構分別存儲所有的節點信息和所有的弧段信息。需注意：節點索引中只需記錄節點的坐標信息，無需記錄其所屬的數據圖層、對象、點串索引等信息。弧段存入弧段網格索引結構中，索引結構中需要同步記錄該弧段所屬的數據圖層、對象、點串索引等信息。2) 遍歷所有索引網格，依次取出每個索引網格內的節點v，以v為中心點，擴散一個容限的距離，查詢是否符合節點插入條件。需注意：如果計算出的垂足點不在當前處理網格內，則不記錄，將此情況交由垂足點所在網格處理，防止重復記錄所需的插入節點。3) 節點與弧段位置計算結束后，按照記錄的節點插入信息，進行數據調整。

圖3 節點與弧段間拓撲處理特殊情況

Fig.3Specialcasesofvertexandarctopologyconsistencyprocess

1.4 節點間鄰近搜索

在經過弧段間拓撲處理和節點與弧段間拓撲處理兩個過程后，已對數據中的弧段相交情況進行了節點插入，并將數據中存在的節點與弧段距離小于容限的情況通過插入垂足節點的方式轉化為距離在容限范圍內的節點問題，此時需要通過節點間鄰近搜索過程對這些距離在容限范圍內的節點情況進行搜索和處理。不同于Pullar算法中的聚類過程，本文采用節點間鄰近搜索的策略將這些通過容限相關的節點搜索出來，而后統一調整為同一坐標。

如圖4所示，通過節點v1進行鄰近點搜索時可將距離v1在容限范圍內的節點v2搜索出來，而繼續通過v2進行鄰近點搜索時可將距離v2在容限范圍內的節點v3搜索出來，直到通過v3進行鄰近點搜索時不再發現容限范圍內的節點為止。找到的v1、v2、v33個節點被稱為鄰近點簇，如果鄰近點簇中節點數目小于用戶設置的閾值則直接將這些點調整為與v1點坐標一致，如數目大于用戶設置的閾值則將這些點的坐標位置記錄下來并反饋給用戶進行手動編輯處理。整體處理流程如下：1) 依次遍歷矢量數據圖層，取出每個對象，對其節點建立網格索引，并將所有節點存儲到一個節點數組中。索引結構中需要同步記錄該節點所屬的數據圖層、對象、點數組索引等信息。2) 遍歷所有索引網格，依次取出每個索引網格內的節點v，以v為中心點，擴散一個容限的距

圖4 節點間鄰近搜索

Fig.4Vertexneighboringsearch

離，如找到距離節點v在容限范圍內的節點，則以此節點為當前節點繼續進行鄰近搜索，直到找不到容限范圍內的節點為止，而后計算找到的鄰近點簇需調整到的節點v1位置。3) 節點間鄰近搜索結束后，按照記錄的節點調整信息并調整數據。

2 實驗與分析

為驗證本文算法的有效性，使用C語言實現了上文描述的拓撲一致性處理改進算法，并與ArcGIS桌面軟件拓撲一致性處理的相關功能進行測試比較。實驗環境為一臺主頻2.6GHz的雙核處理器PC機，內存為2GB。由于疊加分析操作是對矢量數據質量要求較高的分析操作，且在疊加分析操作中涉及大量的節點間匹配計算、弧段間相交計算、多邊形生成計算等復雜處理，因此選用疊加分析操作作為拓撲一致性處理效果的驗證手段，即在拓撲一致性處理后使用疊加分析操作驗證拓撲一致性處理的有效性。首先選取兩個面數據，分別在ArcGIS和改進算法中進行拓撲一致性處理和后續疊加分析處理，而后對兩種處理結果進行比較分析。為了保證測試驗證的有效性，針對該數據分別使用“相交”和“對稱差”兩種疊加模式，且每種模式下都使用大小不等的兩種處理容限進行測試。如表1所示，ArcGIS的拓撲一致性處理和疊加分析操作在同樣的疊加模式下對于容限的改變較不敏感，而改進算法中結果對于容限的改變較為敏感。在4組實驗中，結果數據集總面積一項中表現出和ArcGIS較好的一致性，ArcGIS處理結果和改進算法處理結果總面積偏差都在十萬分之一以下，且有一組測試數據的總面積偏差在百萬分之一以下，即經過拓撲一致性改進算法處理后的數據在疊加分析操作過程中表現出較好的數據質量和處理效果。

表1 改進算法和ArcGIS對比測試結果

Table 1 The result comparison of improved algorithm and ArcGIS

序號疊加方式疊加容限ArcGIS總面積(m2)改進算法總面積(m2)面積偏差(m2)1相交5．25461348429912294．371348429614234．562．21042E-072相交0．00011348429912294．371348424580959．503．95374E-063對稱差5．25468183976303662．088183956850405．882．37699E-064對稱差0．00018183976303662．088183961789600．571．77347E-06

在保證拓撲一致性處理效果的基礎上，針對該改進算法的性能與ArcGIS進行進一步的對比測試，為了保證測試的有效性，分別針對常用的線數據類型和面數據類型，選用了多組規模不等的空間數據進行對比測試(表2)。由表2可知，無論是在線數據類型還是在面數據類型對比測試中，在多種數據規模下的改進算法性能都優于ArcGIS中的拓撲一致性處理方法，其中在線數據類型中平均性能提升約為41.75%(圖5)，在面數據類型中平均性能提升約為36.94%(圖6)。改進算法在保證處理結果有效性的基礎上具有較優的處理性能，是一種實用性較強的處理方法。

表2 線和面數據類型性能對比測試結果

Table 2 The comparison of line and polygon dataset performance

序號線數據類型面數據類型對象數目ArcGIS(s)改進算法(s)性能提升(%)對象數目ArcGIS(s)改進算法(s)性能提升(%)1105903．412．7120．531055327．2115．6142．632209797．273．9445．802037842．9327．1136．8533103110．135．5245．513065175．6743．5542．4544148113．568．2539．1639208110．1463．5642．2955152918．219．8445．9650550147．7365．1455．9166158221．3411．5545．8860549171．12119．7630．0177096425．7113．2548．4670618195．26139．1428．7487861526．3414．6444．4280248234．31166．5528．9298998129．1716．3443．9891674261．41185．2329．141010346733．5620．8637．84105555298．07201．4632．41

圖5 線數據集性能對比測試 圖6 面數據類型性能對比測試

Fig.5 Comparison of the line dataset performance Fig.6 Comparison of the polygon dataset performance

3 結語

在GIS矢量數據相關的各種空間分析中，拓撲一致性的處理效果與處理性能對于后續包括疊加分析、緩沖區分析、空間查詢等各種空間分析效果有較大的影響。本文首先針對已有的較為典型的拓撲一致性處理算法進行了闡述和分析，主要包括Milenkovic算法、Pullar算法、Harvey&Vauglin算法以及ArcGIS的處理方式，重點針對各算法的使用情況以及局限性進行了分析。在此基礎上提出了一種性能較優的改進算法，主要包括弧段間拓撲處理、節點與弧段間拓撲處理、節點間鄰近搜索3個核心過程，并重點針對處理過程中容限的設置與處理、算法的核心數據結構等內容進行了詳細闡述。通過3組實驗對該改進算法的處理效果和處理性能進行了對比驗證與分析，實驗結果表明，本文所描述的改進算法在保證處理效果有效的前提下具有較高的分析處理性能，是一種實用性較強的拓撲一致性處理算法。

[1] GOODCHILD M F.Statistical aspects of the polygon overlay problem[J].Harvard Papers on Geographic Information Systems,1978,6:1-22.

[2] HOFFMANN C M.Geometric and Solid Modeling[M].New York:Morgan Kaufmann,1989.

[3] OTTMANN T,THEIMT G,ULLRICH C.Numerical stability of geometric algorithms[A].Proceedings of the Third Annual Symposium on Computational Geometry[C].ACM,1987.119-125.

[4] BLAKEMORE M.Generalization and error in spatial databases[J].Cartographica,1984,21:131-139.

[5] SALESIN D,STOLFI J,GUIBAS L.Epsilon geometry:Building robust algorithms from imprecise computations[A].Proceedings of the Fifth Annual Symposium on Computational Geometry[C].ACM,1989.208-217.

[6] DOUGENIK J.WHIRLPOOL:A geometric processor for polygon coverage data[A].Proceedings of Auto-Carto 4[C].1980,2:304-311.

[7] CHRISMAN N R.Epsilon filtering:A technique for automated scale changing[A].Technical Papers of the 43rd Annual Meeting of the American Congress on Surveying and Mapping[C].Washington DC,1983.322-331.

[8] MILENKOVIC V J.Verifiable implementations of geometric algorithms using finite precision arithmetic[J].Artificial Intelligence,1988,37(1):377-401.

[9] PULLAR D V.Spatial overlay with inexact numerical data[A].Proceedings Auto-Carto 10[C].Baltimore,1991.313-329.

[10] HARVEY F,VAUGLIN F.No fuzzy creep! A clustering algorithm for controlling arbitrary node movement[A].Proceedings Auto-Carto 13[C].Seattle,ASPRS/ASCM,1997.

[11] ArcGIS 9.3 Help,2009,URL:http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm?TopicName=welcome.2009-12-30.

[12] 王少華,鐘耳順,盧浩,等.基于非均勻多級網格索引的矢量地圖疊加分析算法[J].地理與地理信息科學,2013,29(3):17-20.

Study on Topology Consistency Processes for Vector Data Overlay Analysis

WANG Shao-hua1,2,ZHONG Er-shun1,LI Shao-jun1,2,3,LU Hao2

(1.InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,Beijing100101;2.SuperMapSoftwareCo.Ltd.,Beijing100015;3.UniversityofChineseAcademyofSciences,Beijing100039,China)

Topology consistency issues of vector data need to be faced with primary,which in various vector data analysis processes including overlay analysis,buffer analysis and topological analysis.The topology consistency process is handling with inconsistencies of spatial data topological relations,which generated by acquisition,storage,compression and conversion of GIS vector data.It allows data to keep topology consistency within the tolerance range,so as to facilitate subsequent analysis functions.In this paper,a more efficient topology consistency processing improved algorithm is proposed,which is based on analyzing and summarizing the existing topology consistency processing algorithms.The algorithm contains three core processes,including arcs topology processing,vertexes and arcs topology processing and vertexes proximity searching.The comparison experiments show that the algorithm processing performance is improved and can ensure the processing results are correct,and it is a practical topology consistency processing algorithm

vector data;overlay analysis;uniform grid index;topology consistency

2014-01-28；

2014-04-17

交通運輸部科技項目(2012-364-X04-102);中國科學院重點部署項目(KZZD-EW-07-01-001);國家科技支撐計劃項目(2011BAH06B03);資源與環境信息系統國家重點實驗室自主研究項目(088RAC00YA);中國科學院國防科技創新基金項目(CXJJ-14-M13);北京市科技專項(Z141101004414011)

王少華(1983-)，男，博士，主要研究方向為GIS軟件技術。*通訊作者E-mail:luhao@supermap.com

10.3969/j.issn.1672-0504.2015.01.003

P208

A

1672-0504(2015)01-0012-05