基于拓撲原子事件的拓撲關系局部更新技術

夏晨翕，代琬璐，陳 霄，胡 奇

1. 中國人民解放軍31680部隊，四川 成都 611200；

2. 西南交通大學 地球科學與環(huán)境工程學院，四川 成都 611756；

3. 西安欏析時空軟件科技有限公司，陜西 西安 710048

0 引 言

空間關系包括度量、順序和拓撲3種關系，這些基本關系都是空間數(shù)據(jù)組織、查詢、分析和推理的基礎。拓撲關系是GIS發(fā)展的重要標志，代表了語義層次上最重要的一類空間關系[1]。在GIS中，地理實體間的拓撲關系能清楚地反映實體間的關系和邏輯結構?？臻g數(shù)據(jù)存入數(shù)據(jù)庫之后，為了維持數(shù)據(jù)的現(xiàn)勢性和數(shù)據(jù)質量，需要對原有點、線、面要素數(shù)據(jù)進行編輯更新操作，常常會引起拓撲關系的改變，在修改空間要素數(shù)據(jù)后，一般需要對更改后的空間數(shù)據(jù)進行拓撲重構[2]。

在拓撲的局部更新中，國外學者PAPADIAS和THEODORIDIS提出了空間關系最小邊界矩形（MBR）[3]使得空間拓撲關系局部更新理論研究進入新階段。國內(nèi)的程雙偉在MBR的基礎上，結合優(yōu)化的拓撲生成相關算法，在拓撲關系更新中提出了一種簡便、靈活的局部拓撲更新方法，從而使局部拓撲更新成為可能[4]。徐立在對局部拓撲更新中，提出了兩種思路，一是確定拓撲發(fā)生變化的范圍，在變化范圍內(nèi)進行拓撲局部更新；二是將拓撲更新細分為原子事件，根據(jù)拓撲編輯實時更新拓撲數(shù)據(jù)，并對兩種算法進行比較，通過實例進行算法驗證[5]。

拓撲原子事件是指在進行拓撲編輯過程中對拓撲要素的最基本操作[5]，只能同時編輯一種要素，拓撲原子事件不可再分，并且具有原子性和獨立性。地理網(wǎng)絡拓撲關系的原子事件分為兩大類：結點拓撲原子事件和弧段拓撲原子事件[6-7]。針對結點拓撲原子事件的操作包括：結點的添加、刪除、修改；針對弧段拓撲原子事件的操作包括：弧段的添加、刪除、修改。本文重點根據(jù)地理事件對地理網(wǎng)絡拓撲關系的影響規(guī)律，研究地理事件（點、線）引起的地理網(wǎng)絡拓撲關系局部重構的方法，設計相應算法，并結合實際地理網(wǎng)絡數(shù)據(jù)，進行算法驗證。

1 算法原理

幾何數(shù)據(jù)變化能夠影響拓撲關系發(fā)生變化，所以可以利用幾何數(shù)據(jù)變化規(guī)律找出拓撲關系發(fā)生變化的要素，進而確定所需要素，再進行拓撲更新操作。

首先對變化要素最小外接矩形范圍內(nèi)的所有要素進行相交斷鏈處理，此時可能會有新的結點產(chǎn)生。然后將編輯要素時新增或刪除的結點添加到相交斷鏈產(chǎn)生的結點集合中。與這些結點相關聯(lián)的弧段及結點本身需要進行拓撲重新構建，與此類結點相鄰的其他結點不需要拓撲重構，只需要修改拓撲信息即可。依據(jù)此規(guī)律很容易確定哪些要素需要進行拓撲更新操作，即變化區(qū)域的選定。最后再修改邊界要素拓撲數(shù)據(jù)信息，保證拓撲重構區(qū)域和已有拓撲關系保持一致，局部更新完成（圖1）。

圖1 拓撲局部更新流程Fig.1 Topology local update process

2 變化范圍提取

2.1 幾何變化影響拓撲變化規(guī)律

在網(wǎng)絡拓撲更新中，由于幾何要素的變化而引起拓撲關系改變，如幾何要素新增或刪除時，變化結點的相鄰結點和變化弧段的關聯(lián)結點可以終止拓撲關系，變化沿弧段方向延伸。

2.2 結點分類

根據(jù)幾何變化影響拓撲變化的規(guī)律，將參與局部拓撲更新的結點按以下形式分類。拓撲更新過程中，由于結點幾何發(fā)生變化的結點為第一類結點；當結點擬合到已有結點上，可結點相關聯(lián)弧段個數(shù)發(fā)生變化，結點同樣歸為第一類結點。如結點或弧段幾何發(fā)生變化引起已有結點拓撲發(fā)生變化的結點歸為第二類變化點。與第二類相鄰但不是第二類或第一類的結點為第三類結點。

2.3 變化要素提取

由于此方式是根據(jù)結點要素變化情況提取變化要素，所以需要先確定變化要素區(qū)域內(nèi)的結點分類情況。因此，在局部拓撲更新之前需要對變化要素最小外接矩形范圍內(nèi)的所有幾何要素進行相交斷鏈處理，再作結點擬合，根據(jù)分類準則依次區(qū)分第一類結點、第二類結點及第三類結點。

2.4 變化范圍確定

在網(wǎng)絡拓撲關系中，有些要素拓撲關系發(fā)生變化，需要修改拓撲數(shù)據(jù)，而有些要素間的拓撲關系發(fā)生改變，如結點的鄰接、弧段的鄰接關系，則不需要更新數(shù)據(jù)庫[8]。按照是否需要更新數(shù)據(jù)將拓撲關系發(fā)生變化的要素分為兩類，一是需要更新數(shù)據(jù)的要素，二是不需要更新數(shù)據(jù)但部分拓撲關系發(fā)生改變的要素。

1）拓撲更新范圍確定。依據(jù)多邊形追蹤算法，按照分類的結點，從任意一個第二類結點出發(fā)，在弧段不經(jīng)過第一結點的前提，經(jīng)過網(wǎng)絡中已有弧段，將所有第二類結點相連，變化要素始終位于搜索方向右側，并且保證搜索區(qū)域的最小性，該過程圍成的多邊形區(qū)域為要素拓撲關系發(fā)生變化區(qū)域，如圖2中黃色弧段圍成的多邊形區(qū)域，則此范圍內(nèi)要素拓撲關系需要全部重新構建。

2）參與拓撲更新計算范圍確定。在第二類結點及更新數(shù)據(jù)范圍的基礎上，依據(jù)多邊形追蹤算法，從任意一個第三類結點出發(fā)，且弧段不經(jīng)過第二類結點確定區(qū)域經(jīng)過的弧段，保證搜索區(qū)域最小化的同時，按照拓撲關系更新范圍方法確定區(qū)域的過程，構建新的范圍，如圖2中綠色弧段圍成的區(qū)域，則在此范圍內(nèi)的所有要素拓撲關系發(fā)生變化，包括變化要素的相鄰關系[9]，但只有部分要素需要更新數(shù)據(jù)庫。

圖2 拓撲局部范圍圖Fig.2 Local range of topology

2.5 范圍邊界懸垂弧處理操作

在選取要素變化范圍時，出現(xiàn)懸垂弧的情況，需要對懸垂弧特殊記錄。在后續(xù)選擇的變化區(qū)域中更新拓撲時，懸垂弧需要作為已有要素不需要重新生成。在范圍選取時，當變化要素較多時，可能會出現(xiàn)多邊形內(nèi)包含多邊形的情況，即島多邊形，此時需要更新的變化要素是在島內(nèi)多邊形以外的區(qū)域。如果島內(nèi)只存在單個結點或者是單弧情況，處理方法和懸垂弧相同。

2.6 特殊情況變化要素處理

1）結點移動。在網(wǎng)絡拓撲關系中，結點移動前后，與該結點相關聯(lián)弧段始終不與其他要素相交，則可以判斷節(jié)點的移動沒有影響網(wǎng)絡拓撲關系的改變。此種情況只用對結點的幾何坐標和屬性信息進行修改，不需要更新拓撲關系。若結點的移動使得結點的關聯(lián)弧段與其他要素相交，即網(wǎng)絡拓撲發(fā)生變化，則需要將結點移動后的相關聯(lián)的弧段與其最小外接矩形范圍內(nèi)要素進行相交斷鏈處理，再確定拓撲關系變化區(qū)域，并對變化區(qū)要素作拓撲關系更新。

多邊形拓撲關系中由于結點的移動操作，可能沒有影響弧段和結點拓撲關系，但結點移動前后所在區(qū)域發(fā)生了變化。之前的方法便不能發(fā)現(xiàn)拓撲關系的改變，需要做特殊判斷。判斷的基本思路是：查找到移動結點和相關聯(lián)弧段所在的最小多邊形區(qū)域，如圖3中左圖結點A在多邊形B外，右圖結點A在多邊形B內(nèi)，當移動完成后再判斷該結點和相關弧段所在的最小多邊形區(qū)域。若兩次區(qū)域相同，則判定該結點的移動沒有引起拓撲變化；否則，多邊形拓撲發(fā)生變化。當多邊形拓撲發(fā)生變化時可以按照移動后結點及相關弧段的新增和移動前弧段刪除進行拓撲更新操作。結點移動前后，結點所在最小多邊形可以使用面積判斷法。

圖3 結點所在多邊形位置確定Fig.3 Determination of polygon position of node

此外，也存在一種特殊情況：結點編輯使得該弧段所在多邊形發(fā)生改變，弧段的拐點從多邊形內(nèi)移動到多邊形外。此時可以使用結點替換操作，將替換的結點看成是第一類結點處理。

2）弧段幾何編輯操作。對于弧段的編輯操作主要有對組成弧段的上點的幾何位置修改和組成弧段上點的新增和刪除。操作完成后，判斷該弧段是否與其他要素相交，進而確定拓撲關系是否發(fā)生變化。若發(fā)生變化，則進行拓撲更新操作，否則不進行，只修改結點的幾何坐標和屬性信息。

3）弧段的移動操作。弧段的移動涉及至少兩個結點的移動，需要確保兩個結點在移動前后與關聯(lián)弧段拓撲關系保持不變，且弧段不與其他要素產(chǎn)生新結點，拓撲才不會變化。實際應用中這種情況較少，所以弧段的移動一般看成是新弧段的添加和舊弧段的刪除便可完成拓撲更新。

3 拓撲更新過程

需要更新的范圍一經(jīng)劃定，就不必關注拓撲編輯的過程，只需要在范圍內(nèi)按照不同要素類型進行拓撲關系更新即可。此時應將范圍內(nèi)的全部要素進行拓撲關系重新生成，在生成過程中若遇到選定范圍的邊界處，只需要修改對應結點和弧段的拓撲信息，便能和原拓撲關系保持一致[10]。拓撲更新主要流程如圖4所示。

圖4 拓撲更新流程圖Fig.4 Topology update flow chart

3.1 變化范圍內(nèi)要素處理

1）一般要素處理方法。對于變化區(qū)域多邊形范圍內(nèi)的要素，主要包括第一類結點和與第一類點直接相關聯(lián)的弧段要素。由于其幾何數(shù)據(jù)都發(fā)生變化，并且引起了拓撲數(shù)據(jù)的變化，則對于這類要素按照網(wǎng)絡拓撲關系進行拓撲構建。按照第一類結點的規(guī)定，是新增、刪除或擬合操作的結點，則第一類結點中，對于新增和擬合到原有結點，直接相連的所有弧段需要重新生成，并重新生成拓撲關系。處理新增結點如果在已有弧段上，則需要找到新增結點所在的弧段。如新增結點為第一類結點，新增結點所在弧段的首末結點為第二類結點，按照結點分類操作處理即可[11]。對于擬合到已有結點，需要用新結點替換原有結點，給原有結點重新編號，當作第一類結點處理，并進行拓撲重構。

2）刪除結點處理方法?；《尉庉嬤^程中，一般相交斷鏈之后會有結點新增，除懸垂弧情況等特殊情況之外，系統(tǒng)會自動刪除結點操作，其他結點的刪除更多的是手動刪除。按照拓撲中對結點刪除后的操作處理需要進行炸開操作，故處理方法稍不同于新增和擬合結點處理方法。

對于手動刪除的結點，在拓撲關系中，結點的刪除意味著該結點相鄰的弧段不再連通，那么就應在刪除結點處新增對應關聯(lián)弧段數(shù)個結點，并對與刪除結點相關聯(lián)的弧段重新編號。對這類結點做特殊處理方法同結點刪除操作一樣。此處相當于懸垂弧情況，當需要使得其中的部分弧段相連，必須進行手動操作選擇需要連接的弧段。

在刪除結點處新增該結點相連弧段數(shù)個結點，并對相連的所有弧段重新編號，修改該結點相鄰結點拓撲關系，同時刪除原結點。其他處理過程和第一類結點拓撲生成相同。

對于變化區(qū)域內(nèi)要素，除刪除結點需要特殊處理外，其他所有要素不需要關注拓撲編輯過程，只需將區(qū)域內(nèi)要素拓撲關系重新生成即可。當區(qū)域內(nèi)拓撲重新生成完成后，將變化區(qū)域內(nèi)要素的拓撲關系全部刪除。

對于在范圍內(nèi)的第一類結點，需要全部重新生成并編號，并且與第一類結點關聯(lián)的弧段應全部重新生成并編號，進行結點擬合操作，重構該范圍內(nèi)的拓撲關系，算法同網(wǎng)絡拓撲關系生成過程。在變化區(qū)域內(nèi)，存在不和第一類結點直接相連的弧段，即構成邊界范圍時形成的懸垂弧，則按邊界要素處理，不參與拓撲重構。

3.2 變化范圍編輯要素處理

在變化范圍內(nèi)的所有要素拓撲重構完成后，應和已有拓撲關系保持一致性，修改邊界要素的關聯(lián)信息。

1）結點修改。在局部拓撲關系發(fā)生變化的要素中，結點主要分為三類，變化區(qū)域內(nèi)結點、變化區(qū)域邊界結點和變化區(qū)域外結點。對于第一類結點，重構拓撲關系；第三類結點拓撲關系不需要更新操作；第二類結點沒有進行拓撲重構，但關聯(lián)關系發(fā)生了變化，需要進行結點修改操作，即修改結點表中結點關聯(lián)弧段信息，以便實現(xiàn)變化區(qū)域內(nèi)外拓撲一致性[12]。在網(wǎng)絡拓撲關系中邊界上存在的第三類結點拓撲信息不用拓撲更新操作。

2）弧段修改。在網(wǎng)絡拓撲關系中，由于弧段沒有記錄左右多邊形信息，則變化范圍邊界的弧段要素拓撲信息不更新。在多邊形拓撲關系中，還應進行組成變化范圍多邊形弧段的修改操作，主要修改邊界弧段的左右多邊形信息[13]，此處需要注意邊界構成中懸垂弧處理方法。當變化區(qū)域內(nèi)重構的拓撲關系與變化范圍外要素拓撲關系保持一致時，局部拓撲更新完成。

4 實驗分析

拓撲數(shù)據(jù)更新主要是當局部要素幾何信息發(fā)生變化后，可能影響范圍內(nèi)要素拓撲信息的變化，就需要對這些拓撲發(fā)生變化的要素進行拓撲更新，保證與全局要素的拓撲關系一致性。當一定區(qū)域內(nèi)多個要素發(fā)生變化時，需要進行更大范圍更新操作，本案例模擬多個局部拓撲要素發(fā)生變化后，對拓撲關系影響范圍，并按照第3節(jié)方法更新拓撲要素。實驗數(shù)據(jù)采用模擬地理網(wǎng)絡數(shù)據(jù)，數(shù)據(jù)主要包括地理道路線要素。ArcMap中構建出地理網(wǎng)絡數(shù)據(jù)，并新建點要素圖層用來存儲線弧段的首末結點以及相交斷鏈產(chǎn)生的結點信息。為區(qū)分不同弧段，所有的弧段有唯一編號。

當對該區(qū)域要素進行相交斷鏈處理后，之前存在相交的弧段會在交點處新建節(jié)點，并把弧段分成兩部分。對于結點間存在的偏差，需要將小于閾值的結點作預處理操作，當對區(qū)域內(nèi)所有相交斷鏈后產(chǎn)生的結點進行匹配操作，從而構建網(wǎng)絡拓撲關系。有關網(wǎng)絡拓撲關系構建算法比較完善，此處不再過多贅述。

本例中進行的操作包括弧段添加、弧段刪除以及結點刪除。確定了變化要素后，將變化要素與其最小外接矩形范圍內(nèi)所有要素進行相交斷鏈處理，過程同弧段相交斷鏈處理。再將新增或刪除的結點加入第一類結點中。按照第二類結點分類依據(jù)，分別找出所有第二類結點。按照前述的變化范圍選取方法，找出所有拓撲關系發(fā)生變化并需進行拓撲更新的要素。如圖5高亮弧段為變化要素影響的拓撲范圍，其中存在的懸垂弧做特殊標記，則高亮范圍內(nèi)所有要素需重新構建拓撲關系。

圖5 基于網(wǎng)絡數(shù)據(jù)相交斷鏈的結點分布和拓撲更新范圍Fig.5 Distribution of nodes and topology update scope based on network data intersection and chain break

對應變化范圍內(nèi)的所有要素需要全部重新生成，再由拓撲更新算法對區(qū)域內(nèi)所有要素進行拓撲重構。在拓撲構建過程中，遇到更新范圍邊界時，需要修改第二類結點的關聯(lián)弧段信息，其他邊界弧段在網(wǎng)絡多邊形生成過程中不需要進行弧段信息修改操作即可完成拓撲更新，并保持更新范圍內(nèi)外拓撲關系的一致性（圖6）。

圖6 拓撲發(fā)生變化后要素分布Fig.6 Feature distribution after topology change

依據(jù)局部拓撲變化規(guī)律，進行局部拓撲更新要素范圍劃定，對幾種特殊情況進行分述，使得此方法劃定范圍更準確。實驗使用模擬數(shù)據(jù)進行拓撲關系構建中關鍵算法實現(xiàn)，對局部拓撲更新區(qū)域選擇或要素提取進行了示范，更近一步描述拓撲變化范圍選取過程和方法。在拓撲范圍確定過程中，如果范圍出現(xiàn)島多邊形，在內(nèi)部要素較多時對內(nèi)部要素特殊標記效率較高，但當內(nèi)部要素少時，效率反而不高。

5 結 論

本文運用地理網(wǎng)絡模擬數(shù)據(jù)進行拓撲更新過程模擬操作，依據(jù)各個要素變化情況進行對比分析，從理論上分析當多種要素發(fā)生變化后，更新要素范圍的確定過程和拓撲局部更新思路的確定過程。根據(jù)地理事件對地理網(wǎng)絡拓撲關系影響規(guī)律，研究了點、線引起的地理網(wǎng)絡拓撲關系局部重構的方法。從地理事件對地理網(wǎng)絡拓撲關系影響變化規(guī)律出發(fā)，利用幾何變化引起拓撲關系變化的方法，確定拓撲關系發(fā)生變化范圍并提取變化要素，結合已有拓撲局部更新理論方法，對已有算法進行相應優(yōu)化，研究設計出地理網(wǎng)絡拓撲局部更新方法。