操震洲姜林燕吳煜心

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

0 引 言

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

1 河流選取的指標(biāo)

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

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

河流權(quán)重指標(biāo)計(jì)算方法下所示（圖1）。

圖1 河流權(quán)重的計(jì)算方法

2 河網(wǎng)多尺度組織結(jié)構(gòu)

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

（1）逐河流執(zhí)行Douglas-Peucker算法，生成BLG樹(shù)，將各結(jié)點(diǎn)偏離量線性存貯，生成線性BLG樹(shù)結(jié)構(gòu)。

（2）計(jì)算河流的最小外接矩形，計(jì)算各河流的初始權(quán)重值。

（3）按河流層次關(guān)系河系樹(shù)，調(diào)整樹(shù)中父子結(jié)點(diǎn)的權(quán)重值。

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

河流2的線性BLG樹(shù)的生成過(guò)程如下所示（圖2）。其中，河流2的約束點(diǎn)有端點(diǎn)P21、P27，河流交匯點(diǎn)P23。

圖2 單條河流的結(jié)點(diǎn)偏離量計(jì)算過(guò)程

按以上方式建立各河流的線性BLG樹(shù)后，線性BLG樹(shù)的開(kāi)始兩個(gè)結(jié)點(diǎn)存貯了河流的權(quán)重值，可基于它進(jìn)行河流選取，而在其他結(jié)點(diǎn)存貯結(jié)點(diǎn)偏離量信息，可基于它進(jìn)行河流簡(jiǎn)化。由于該線性BLG樹(shù)已按河流的層次關(guān)系調(diào)整了權(quán)重值，所以能保證當(dāng)支流被選取時(shí)，其對(duì)應(yīng)的主流也會(huì)被選取。同時(shí)，該線性BLG樹(shù)修改了約束點(diǎn)的偏離量值，所以可以避免第一類(lèi)拓?fù)洳灰恢碌陌l(fā)生。

對(duì)于可能出現(xiàn)的第二類(lèi)拓?fù)洳灰恢?，可按Da Silva ACG等[11-12]的方法來(lái)處理。如圖3所示，實(shí)線C、虛線C’分別代表簡(jiǎn)化前后的河流。線段L1L2的端點(diǎn)L1落在多邊形v4v5v6v7內(nèi)，表明出現(xiàn)了拓?fù)洳灰恢?。此時(shí)可通過(guò)恢復(fù)結(jié)點(diǎn)的方式消除拓?fù)洳灰恢隆?/p>

圖3 拓?fù)洚惓Ｅ卸ú呗?/p>

該河網(wǎng)組織結(jié)構(gòu)可根據(jù)用戶需求快速生成保持拓?fù)湟恢滦缘亩喑叨群泳W(wǎng)數(shù)據(jù)。記當(dāng)前選取和簡(jiǎn)化的尺度分別為r1、r2，則當(dāng)前尺度下的河網(wǎng)數(shù)據(jù)生成過(guò)程如下:

①根據(jù)r1檢索河流，選取權(quán)重≥r1的所有河流;② 對(duì)所有選中的河流，選取偏離量≥r2的所有結(jié)點(diǎn);③ 對(duì)上一步新生成的所有線段，按圖3的方法檢測(cè)拓?fù)洳灰恢?，通過(guò)恢復(fù)結(jié)點(diǎn)消除拓?fù)洳灰恢?④ 輸出當(dāng)前尺度下的河網(wǎng)數(shù)據(jù)。

3 實(shí)驗(yàn)及分析

基于.NET平臺(tái)開(kāi)發(fā)了實(shí)驗(yàn)系統(tǒng)，測(cè)試河網(wǎng)多尺度組織結(jié)構(gòu)的有效性。數(shù)據(jù)源為Shapefile格式文件，實(shí)驗(yàn)程序讀取Shapefile格式河網(wǎng)數(shù)據(jù)，按本文方法建立河網(wǎng)多尺度組織結(jié)構(gòu)。實(shí)驗(yàn)程序根據(jù)用戶的設(shè)置，動(dòng)態(tài)生成任意尺度的河網(wǎng)數(shù)據(jù)，同時(shí)對(duì)簡(jiǎn)化后河網(wǎng)數(shù)據(jù)執(zhí)行拓?fù)洳灰恢碌臋z測(cè)與消除。以下為三個(gè)不同尺度下的河網(wǎng)數(shù)據(jù)視圖（圖4）。

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

4 結(jié) 語(yǔ)

河網(wǎng)數(shù)據(jù)多尺度簡(jiǎn)化涉及河流選取、簡(jiǎn)化算法、拓?fù)湟恢滦跃S護(hù)等內(nèi)容。本文提出的河網(wǎng)多尺度組織結(jié)構(gòu)在滿足拓?fù)湟恢滦缘那疤嵯聦?shí)現(xiàn)了河網(wǎng)的多尺度動(dòng)態(tài)生成。該結(jié)構(gòu)首先根據(jù)河流的尺寸與層次性計(jì)算河流權(quán)重，以權(quán)重作為河流選取的指標(biāo)，然后逐河流建立線性BLG樹(shù)，以結(jié)點(diǎn)偏離量作為河流的簡(jiǎn)化依據(jù)?；诤泳W(wǎng)多尺度組織結(jié)構(gòu)開(kāi)發(fā)了實(shí)驗(yàn)系統(tǒng)并驗(yàn)證了其有效性。但在拓?fù)湟恢滦跃S護(hù)算法的時(shí)間效率方面仍有待進(jìn)一步研究。