顧及節(jié)點約束的境界線與道路拓撲沖突處理方法研究

欒磊洋 徐鯤 符季穎

（北京建筑大學測繪與城市空間信息學院，北京 100044）

線化簡是有選擇性地去掉曲線上的點，并對其它點進行合理位移，在化簡點要素的條件下很好地保持線要素的形態(tài)，最終實現(xiàn)要素在客戶端高效的多尺度漸進式可視化。本文提出一種顧及節(jié)點約束的境界線與道路拓撲沖突處理方法，通過幾何重構、建立多尺度層次結構判斷不同類型線要素產生沖突未顧及的偽節(jié)點與特殊節(jié)點，通過得到的約束節(jié)點集合對Douglas-Pecker 與Li-Openshaw 結合算法進行改進，試驗結果表明，該方法能夠在避免拓撲沖突的情況下實現(xiàn)境界線要素的化簡。

1 境界線要素數(shù)據概況

境界線數(shù)據形態(tài)表達有以下特征，如圖1 所示。

第一，國界線與省界線、省界線與市界線不存在重疊關系。

第二，省界、市界間重疊部分均有2 條重合且方向相反的境界線。

圖1 數(shù)據形態(tài)表達

2 境界線要素拓撲沖突處理方案設計

2.1 拓撲沖突產生原因

拓撲關系沖突指空間對象間的拓撲關系存在不合理性，常見的拓撲關系沖突包括存在懸點、多次相交以及部分重疊等情況。在境界線要素化簡過程中，其位置和形態(tài)可能會產生拉伸、扭曲等狀況，從而導致化簡后境界線要素與其他類型線要素產生拓撲沖突。

2.2 拓撲沖突類型

境界線與道路的交叉點（以下簡稱偽節(jié)點）與特殊節(jié)點在線要素化簡過程中存在重要的意義，偽節(jié)點、特殊節(jié)點的位置是需要重點考慮的問題，通過對比分析，總結得到以下4 種拓撲關系變化類型：（1）線線相交于一點化簡后變?yōu)榫€線相離。（2）線線相交于多點化簡后變?yōu)榫€線相交于一點。（3）線線相離化簡后變?yōu)榫€線相交于一點。（4）線線相離化簡后變?yōu)榫€線相較于多點。

2.3 拓撲沖突判別方法

2.3.1 偽節(jié)點的判別

根據圖2(a)可知，道路線與境界線相交處并無可選點，可以通過打斷重構的方法，在相交處打斷形成新的交點(“偽節(jié)點”)坐標，如圖2(b)所示，重構公式（1）如下。

圖2 偽節(jié)點判別

2.3.2 特殊節(jié)點的判別

由于道路經過多個省、市、縣，以道路與市界線的交點將道路分段，以化簡前分段道路與對應市界線這一尺度的拓撲關系為第一狀態(tài)，化簡后分段道路與對應市界線的尺度的拓撲關系為第二狀態(tài)。以2 個或2 個以上狀態(tài)建立多尺度層次結構，檢測某一路段2 個或者2 個以上狀態(tài)空間關系的一致性即可判斷哪一路段存在化簡沖突。其中以道路與市級境界線的交點為分段點建立多尺度層次結構，如表1 所示。

2.4 融合Douglas-Pecker 和Li-Openshaw 的改進算法

融合Douglas-Pecker 和Li-Openshaw 的改進算法的計算流程如下：

2.4.1 以境界線要素某一節(jié)點為起始點，采用Douglas-Pecker 算法開始化簡，根據設定的綜合閾值D，根據下式逐一判斷線要素節(jié)點的距離值d，將滿足閾值條件的節(jié)點進行保留，不滿足閾值D 的節(jié)點在刪除前要考慮前文提及的約束節(jié)點的情況，根據增加的屬性信息判斷是否屬于約束節(jié)點，若為約束節(jié)點，則進行保留，若為待簡化節(jié)點，根據化簡策略，不同時、連續(xù)化簡兩個相鄰點，考慮該節(jié)點的前一個節(jié)點是否被化簡，若前一個節(jié)點被保留，則可刪除該節(jié)點，若前一個節(jié)點被刪除，則該節(jié)點應繼續(xù)保留，依次循環(huán)視域范圍內所有的節(jié)點，直到最后一個節(jié)點。

表1 多尺度層次結構

2.4.2 根據下式（2）計算出圓形最小可視目標SVO（smallest visual object）的尺寸R。

圖3 改進算法

2.4.3 對于采用D-P 算法化簡后的境界線要素的節(jié)點生成的新的曲線，以任意一段曲線的起始端點為圓心，R 為直徑，應用Li-Openshaw 算法進行境界線要素的化簡，以某一段線段為例，首先根據約束節(jié)點的屬性信息判斷該線段上屬于分界點類型約束節(jié)點，以分界點前后兩個節(jié)點為基礎，對曲線進行分段處理，逐次對分段曲線進行化簡；其次，當以R 為半徑交曲線線段于某一點時，首先判斷園內是否存在約束節(jié)點，若存在，則跳過Li-Openshaw 算法對該點的化簡，接下來以約束節(jié)點作為圓心，以R 為直徑，繼續(xù)對境界線進行化簡；若不存在，應用Li-Openshaw 算法取圓心與相交點的中心作為新的節(jié)點，以相交點為圓心，R 為半徑繼續(xù)進行曲線的化簡，循環(huán)化簡直至最后一段曲線被化簡完成。

2.4.4 對于曲線上節(jié)點分布較為密集的區(qū)域，以二分之一R或者三分之一R 對境界線要素進行化簡；對于曲線上節(jié)點分布較為稀疏的區(qū)域，以2R 或者3R 對境界線要素進行化簡，甚至直接跳過該區(qū)域。

2.4.5 至此，化簡完成。

如圖3 所示，其中R 為圓形最小可視目標SVO 的尺寸，R1代表節(jié)點到前后節(jié)點連線的最短距離，i，j 為計數(shù)單位。

采用改進算法對境界線要素進行化簡后，與Douglas-Pecker算法、Li-Openshaw 算法進行比較。如圖4 所示，采用傳統(tǒng)化簡方法導致化簡后境界線與道路線拓撲關系發(fā)生變化，采用本文方法可避免產生拓撲錯誤。

圖4 改進算法化簡效果

3 結論

本文提出一種顧及節(jié)點約束的境界線要素化簡方法，設計了針對境界線要素化簡后與其它類型線要素存在拓撲沖突的化簡方案，該方案首先分析拓撲沖突的產生原因以及判別方法；其次，對視域內線要素節(jié)點采用幾何重構、多尺度層次結構等方法進行判別；最后，采用融合Douglas-Pecker 和Li-Openshaw 的改進算法對視域內線要素進行化簡。結果表明，該方案很好地避免了境界線與道路線化簡后存在的拓撲沖突，并且在拓撲關系一致性的條件下，保證化簡前后線狀要素的整體形態(tài)。