河網(wǎng)數(shù)據(jù)拓撲一致性簡化方法

操震洲姜林燕吳煜心

（1.南京工業(yè)大學測繪科學與技術學院，江蘇 南京211816;2.江蘇省金威遙感數(shù)據(jù)工程有限公司，江蘇 南京210000）

0 引 言

在傳統(tǒng)制圖綜合領域，對河流選取與簡化等問題有較深入的研究。在河流選取方面，一般通過一元回歸模型、多元回歸模型、開方根規(guī)律等確定河流的總體選取數(shù)量[1]。在具體選取時，通常根據(jù)河流的長度、級別等指標確定河流的重要程度，然后選取較重要河流、舍去較次要河流。例如，張青年，艾廷華，姜莉莉等[1-3]分別提出以河流等級、匯水區(qū)域面積、流域為選取指標的水系綜合方法。竇世卿等[4-7]對河流的簡化進行了研究，河流簡化主要涉及到簡化算法和簡化后數(shù)據(jù)的拓撲一致性維護問題。Douglas-Peucker算法[8]是所有曲線簡化算法中公認最優(yōu)秀的，但其時間復雜度高。為提高Douglas-Peucker算法的時間性能，艾波等[7]提出采用線性BLG樹結構事先存貯結點偏離量的方法。采用該線性BLG樹能有效縮短曲線的簡化時間。在圖形簡化過程中，空間目標之間的拓撲關系也會發(fā)生變化[9]，主要表現(xiàn)為出現(xiàn)拓撲不一致。簡化后數(shù)據(jù)的拓撲一致性必須得到保證，這是數(shù)據(jù)可用性的前提。Saalfeld[10]對簡化后數(shù)據(jù)的拓撲不一致問題進行了研究并提出了解決方法，但Saalfeld的方法是有局限性的。Da Silva ACG 等[11-12]對Saalfeld的方法進行了改進和完善，使之可適用于點、線、面的拓撲一致性維護。河流選取既要考慮河流的尺寸大小，也要考慮河流的主、支流關系。當支流被選取時，主流也應被選取。在以上研究中，都未能同時顧及這兩個因素。另外，河流的簡化和拓撲一致性處理費時較長，目前已有算法在時間性能上不夠理想，不適合實時性要求高的應用。

1 河流選取的指標

面向電子顯示設備的要素選取通?；谝爻叽纾缗７角萚13]提出的以要素屏幕面積作為選取指標的面要素多尺度顯示方法。在河流的選取中，河流尺寸是河流選取時應考慮的第一個因素。在小尺度河網(wǎng)數(shù)據(jù)中，只需要顯示較大尺寸的河流，在大尺度河網(wǎng)數(shù)據(jù)中，則可顯示較小尺寸的河流。另外，河流分為主流與支流，主、支流之間構成層次關系。例如，圖1中的河流1與河流2、3、4分別構成了主流與支流的上下層關系（圖1的河流號標記在各河流的首尾兩端處），河流2和河流5也構成了主、支流層次關系。在選取時，若選取支流，則對應的主流也應被選取。因此，河流的層次性是選取時要考慮的第二個因素。

本文綜合考慮河流的尺寸與層次性，并統(tǒng)一量化為權重指標，以該指標作為河流選取的標準。權重指標的計算方法為:首先計算各河流的最小外接矩形，以最小外接矩形的長邊值作為對應河流的初始權重值;然后按河流層次關系建立河系樹，樹結點值為河流的初始權重值;對河系樹中各父子結點值進行檢查并調(diào)整，從葉結點開始，若結點權重值大于其父結點值，則將其父結點權重修改為該結點的值，若結點權重值小于對應父結點值，則無需調(diào)整。按調(diào)整后的權重大小選取河流，這樣既保證了尺寸大的河流先被選取，又保證當某支流被選取后，其對應的主流也一并被選取。

河流權重指標計算方法下所示（圖1）。

圖1 河流權重的計算方法

2 河網(wǎng)多尺度組織結構

通過曲線簡化方法生成多尺度河網(wǎng)。Douglas-Peucker算法是公認最優(yōu)秀的曲線簡化算法，但其時間復雜度為O（n2）（n為結點數(shù)），不適合大數(shù)據(jù)量的實時簡化。為提高Douglas-Peucker算法的時間性能，先后提出了多種方法如BLG樹結構、BLG樹的線性表結構存貯等。本文方法是按Douglas-Peucker算法事先計算河流的各結點偏離量，并以線性BLG結構存貯，然后按存貯的結點偏離量大小篩選結點以實現(xiàn)河流簡化的。該方法可將Douglas-Peucker算法的時間復雜度從O（n2）降為O（n）。在圖形簡化后，空間對象之間可能會出現(xiàn)拓撲不一致。拓撲不一致類型可分為兩種:① 由原來的相鄰、相交關系變?yōu)橄嚯x關系;② 由原來的相離關系變?yōu)橄噜徎蛳嘟魂P系。出現(xiàn)第一類拓撲不一致的原因是不合理刪除了多要素的公共交點或鄰接點，第二類拓撲不一致表現(xiàn)為出現(xiàn)不該有的線段相交和自相交。本文對河網(wǎng)拓撲一致性的維護方法為:① 規(guī)定約束點不可刪除，這樣可避免第一類拓撲不一致的發(fā)生;② 對結點刪除后的新生成線段進行判斷，消除不合理的相交，這樣可消除第二類拓撲不一致，保證簡化后河網(wǎng)的拓撲一致性。稱河流的端點、多條河流間的交匯點為約束點，河網(wǎng)的多尺度組織結構可按以下方法生成。

（1）逐河流執(zhí)行Douglas-Peucker算法，生成BLG樹，將各結點偏離量線性存貯，生成線性BLG樹結構。

（2）計算河流的最小外接矩形，計算各河流的初始權重值。

（3）按河流層次關系河系樹，調(diào)整樹中父子結點的權重值。

（4）為保證河流約束點在簡化中不被刪除，將河流約束點偏離量修改為該河流的權重值，以保證約束點在簡化中總是被選取。

河流2的線性BLG樹的生成過程如下所示（圖2）。其中，河流2的約束點有端點P21、P27，河流交匯點P23。

圖2 單條河流的結點偏離量計算過程

按以上方式建立各河流的線性BLG樹后，線性BLG樹的開始兩個結點存貯了河流的權重值，可基于它進行河流選取，而在其他結點存貯結點偏離量信息，可基于它進行河流簡化。由于該線性BLG樹已按河流的層次關系調(diào)整了權重值，所以能保證當支流被選取時，其對應的主流也會被選取。同時，該線性BLG樹修改了約束點的偏離量值，所以可以避免第一類拓撲不一致的發(fā)生。

對于可能出現(xiàn)的第二類拓撲不一致，可按Da Silva ACG等[11-12]的方法來處理。如圖3所示，實線C、虛線C’分別代表簡化前后的河流。線段L1L2的端點L1落在多邊形v4v5v6v7內(nèi)，表明出現(xiàn)了拓撲不一致。此時可通過恢復結點的方式消除拓撲不一致。

圖3 拓撲異常判定策略

該河網(wǎng)組織結構可根據(jù)用戶需求快速生成保持拓撲一致性的多尺度河網(wǎng)數(shù)據(jù)。記當前選取和簡化的尺度分別為r1、r2，則當前尺度下的河網(wǎng)數(shù)據(jù)生成過程如下:

①根據(jù)r1檢索河流，選取權重≥r1的所有河流;② 對所有選中的河流，選取偏離量≥r2的所有結點;③ 對上一步新生成的所有線段，按圖3的方法檢測拓撲不一致，通過恢復結點消除拓撲不一致;④ 輸出當前尺度下的河網(wǎng)數(shù)據(jù)。

3 實驗及分析

基于.NET平臺開發(fā)了實驗系統(tǒng)，測試河網(wǎng)多尺度組織結構的有效性。數(shù)據(jù)源為Shapefile格式文件，實驗程序讀取Shapefile格式河網(wǎng)數(shù)據(jù)，按本文方法建立河網(wǎng)多尺度組織結構。實驗程序根據(jù)用戶的設置，動態(tài)生成任意尺度的河網(wǎng)數(shù)據(jù)，同時對簡化后河網(wǎng)數(shù)據(jù)執(zhí)行拓撲不一致的檢測與消除。以下為三個不同尺度下的河網(wǎng)數(shù)據(jù)視圖（圖4）。

圖4 多尺度河網(wǎng)數(shù)據(jù)視圖

4 結 語

河網(wǎng)數(shù)據(jù)多尺度簡化涉及河流選取、簡化算法、拓撲一致性維護等內(nèi)容。本文提出的河網(wǎng)多尺度組織結構在滿足拓撲一致性的前提下實現(xiàn)了河網(wǎng)的多尺度動態(tài)生成。該結構首先根據(jù)河流的尺寸與層次性計算河流權重，以權重作為河流選取的指標，然后逐河流建立線性BLG樹，以結點偏離量作為河流的簡化依據(jù)?；诤泳W(wǎng)多尺度組織結構開發(fā)了實驗系統(tǒng)并驗證了其有效性。但在拓撲一致性維護算法的時間效率方面仍有待進一步研究。