河網(wǎng)數(shù)據(jù)拓?fù)湟恢滦院喕椒?/h1>
2018-09-13 12:25:22操震洲姜林燕吳煜心
現(xiàn)代測繪 2018年4期
操震洲姜林燕吳煜心
（1.南京工業(yè)大學(xué)測繪科學(xué)與技術(shù)學(xué)院，江蘇 南京211816;2.江蘇省金威遙感數(shù)據(jù)工程有限公司，江蘇 南京210000）
0 引 言
在傳統(tǒng)制圖綜合領(lǐng)域，對河流選取與簡化等問題有較深入的研究。在河流選取方面，一般通過一元回歸模型、多元回歸模型、開方根規(guī)律等確定河流的總體選取數(shù)量[1]。在具體選取時，通常根據(jù)河流的長度、級別等指標(biāo)確定河流的重要程度，然后選取較重要河流、舍去較次要河流。例如，張青年，艾廷華，姜莉莉等[1-3]分別提出以河流等級、匯水區(qū)域面積、流域為選取指標(biāo)的水系綜合方法。竇世卿等[4-7]對河流的簡化進(jìn)行了研究，河流簡化主要涉及到簡化算法和簡化后數(shù)據(jù)的拓?fù)湟恢滦跃S護(hù)問題。Douglas-Peucker算法[8]是所有曲線簡化算法中公認(rèn)最優(yōu)秀的，但其時間復(fù)雜度高。為提高Douglas-Peucker算法的時間性能，艾波等[7]提出采用線性BLG樹結(jié)構(gòu)事先存貯結(jié)點偏離量的方法。采用該線性BLG樹能有效縮短曲線的簡化時間。在圖形簡化過程中，空間目標(biāo)之間的拓?fù)潢P(guān)系也會發(fā)生變化[9]，主要表現(xiàn)為出現(xiàn)拓?fù)洳灰恢?。簡化后?shù)據(jù)的拓?fù)湟恢滦员仨毜玫奖ＷC，這是數(shù)據(jù)可用性的前提。Saalfeld[10]對簡化后數(shù)據(jù)的拓?fù)洳灰恢聠栴}進(jìn)行了研究并提出了解決方法，但Saalfeld的方法是有局限性的。Da Silva ACG 等[11-12]對Saalfeld的方法進(jìn)行了改進(jìn)和完善，使之可適用于點、線、面的拓?fù)湟恢滦跃S護(hù)。河流選取既要考慮河流的尺寸大小，也要考慮河流的主、支流關(guān)系。當(dāng)支流被選取時，主流也應(yīng)被選取。在以上研究中，都未能同時顧及這兩個因素。另外，河流的簡化和拓?fù)湟恢滦蕴幚碣M時較長，目前已有算法在時間性能上不夠理想，不適合實時性要求高的應(yīng)用。
1 河流選取的指標(biāo)
面向電子顯示設(shè)備的要素選取通?；谝爻叽?，如牛方曲等[13]提出的以要素屏幕面積作為選取指標(biāo)的面要素多尺度顯示方法。在河流的選取中，河流尺寸是河流選取時應(yīng)考慮的第一個因素。在小尺度河網(wǎng)數(shù)據(jù)中，只需要顯示較大尺寸的河流，在大尺度河網(wǎng)數(shù)據(jù)中，則可顯示較小尺寸的河流。另外，河流分為主流與支流，主、支流之間構(gòu)成層次關(guān)系。例如，圖1中的河流1與河流2、3、4分別構(gòu)成了主流與支流的上下層關(guān)系（圖1的河流號標(biāo)記在各河流的首尾兩端處），河流2和河流5也構(gòu)成了主、支流層次關(guān)系。在選取時，若選取支流，則對應(yīng)的主流也應(yīng)被選取。因此，河流的層次性是選取時要考慮的第二個因素。
本文綜合考慮河流的尺寸與層次性，并統(tǒng)一量化為權(quán)重指標(biāo)，以該指標(biāo)作為河流選取的標(biāo)準(zhǔn)。權(quán)重指標(biāo)的計算方法為:首先計算各河流的最小外接矩形，以最小外接矩形的長邊值作為對應(yīng)河流的初始權(quán)重值;然后按河流層次關(guān)系建立河系樹，樹結(jié)點值為河流的初始權(quán)重值;對河系樹中各父子結(jié)點值進(jìn)行檢查并調(diào)整，從葉結(jié)點開始，若結(jié)點權(quán)重值大于其父結(jié)點值，則將其父結(jié)點權(quán)重修改為該結(jié)點的值，若結(jié)點權(quán)重值小于對應(yīng)父結(jié)點值，則無需調(diào)整。按調(diào)整后的權(quán)重大小選取河流，這樣既保證了尺寸大的河流先被選取，又保證當(dāng)某支流被選取后，其對應(yīng)的主流也一并被選取。
河流權(quán)重指標(biāo)計算方法下所示（圖1）。
圖1 河流權(quán)重的計算方法
2 河網(wǎng)多尺度組織結(jié)構(gòu)
通過曲線簡化方法生成多尺度河網(wǎng)。Douglas-Peucker算法是公認(rèn)最優(yōu)秀的曲線簡化算法，但其時間復(fù)雜度為O（n2）（n為結(jié)點數(shù)），不適合大數(shù)據(jù)量的實時簡化。為提高Douglas-Peucker算法的時間性能，先后提出了多種方法如BLG樹結(jié)構(gòu)、BLG樹的線性表結(jié)構(gòu)存貯等。本文方法是按Douglas-Peucker算法事先計算河流的各結(jié)點偏離量，并以線性BLG結(jié)構(gòu)存貯，然后按存貯的結(jié)點偏離量大小篩選結(jié)點以實現(xiàn)河流簡化的。該方法可將Douglas-Peucker算法的時間復(fù)雜度從O（n2）降為O（n）。在圖形簡化后，空間對象之間可能會出現(xiàn)拓?fù)洳灰恢?。拓?fù)洳灰恢骂愋涂煞譃閮煞N:① 由原來的相鄰、相交關(guān)系變?yōu)橄嚯x關(guān)系;② 由原來的相離關(guān)系變?yōu)橄噜徎蛳嘟魂P(guān)系。出現(xiàn)第一類拓?fù)洳灰恢碌脑蚴遣缓侠韯h除了多要素的公共交點或鄰接點，第二類拓?fù)洳灰恢卤憩F(xiàn)為出現(xiàn)不該有的線段相交和自相交。本文對河網(wǎng)拓?fù)湟恢滦缘木S護(hù)方法為:① 規(guī)定約束點不可刪除，這樣可避免第一類拓?fù)洳灰恢碌陌l(fā)生;② 對結(jié)點刪除后的新生成線段進(jìn)行判斷，消除不合理的相交，這樣可消除第二類拓?fù)洳灰恢?，保證簡化后河網(wǎng)的拓?fù)湟恢滦浴７Q河流的端點、多條河流間的交匯點為約束點，河網(wǎng)的多尺度組織結(jié)構(gòu)可按以下方法生成。
（1）逐河流執(zhí)行Douglas-Peucker算法，生成BLG樹，將各結(jié)點偏離量線性存貯，生成線性BLG樹結(jié)構(gòu)。
（2）計算河流的最小外接矩形，計算各河流的初始權(quán)重值。
（3）按河流層次關(guān)系河系樹，調(diào)整樹中父子結(jié)點的權(quán)重值。
（4）為保證河流約束點在簡化中不被刪除，將河流約束點偏離量修改為該河流的權(quán)重值，以保證約束點在簡化中總是被選取。
河流2的線性BLG樹的生成過程如下所示（圖2）。其中，河流2的約束點有端點P21、P27，河流交匯點P23。
圖2 單條河流的結(jié)點偏離量計算過程
按以上方式建立各河流的線性BLG樹后，線性BLG樹的開始兩個結(jié)點存貯了河流的權(quán)重值，可基于它進(jìn)行河流選取，而在其他結(jié)點存貯結(jié)點偏離量信息，可基于它進(jìn)行河流簡化。由于該線性BLG樹已按河流的層次關(guān)系調(diào)整了權(quán)重值，所以能保證當(dāng)支流被選取時，其對應(yīng)的主流也會被選取。同時，該線性BLG樹修改了約束點的偏離量值，所以可以避免第一類拓?fù)洳灰恢碌陌l(fā)生。
對于可能出現(xiàn)的第二類拓?fù)洳灰恢拢砂碊a Silva ACG等[11-12]的方法來處理。如圖3所示，實線C、虛線C’分別代表簡化前后的河流。線段L1L2的端點L1落在多邊形v4v5v6v7內(nèi)，表明出現(xiàn)了拓?fù)洳灰恢?。此時可通過恢復(fù)結(jié)點的方式消除拓?fù)洳灰恢隆?/p>
圖3 拓?fù)洚惓Ｅ卸ú呗?/p>
該河網(wǎng)組織結(jié)構(gòu)可根據(jù)用戶需求快速生成保持拓?fù)湟恢滦缘亩喑叨群泳W(wǎng)數(shù)據(jù)。記當(dāng)前選取和簡化的尺度分別為r1、r2，則當(dāng)前尺度下的河網(wǎng)數(shù)據(jù)生成過程如下:
①根據(jù)r1檢索河流，選取權(quán)重≥r1的所有河流;② 對所有選中的河流，選取偏離量≥r2的所有結(jié)點;③ 對上一步新生成的所有線段，按圖3的方法檢測拓?fù)洳灰恢?，通過恢復(fù)結(jié)點消除拓?fù)洳灰恢?④ 輸出當(dāng)前尺度下的河網(wǎng)數(shù)據(jù)。
3 實驗及分析
基于.NET平臺開發(fā)了實驗系統(tǒng)，測試河網(wǎng)多尺度組織結(jié)構(gòu)的有效性。數(shù)據(jù)源為Shapefile格式文件，實驗程序讀取Shapefile格式河網(wǎng)數(shù)據(jù)，按本文方法建立河網(wǎng)多尺度組織結(jié)構(gòu)。實驗程序根據(jù)用戶的設(shè)置，動態(tài)生成任意尺度的河網(wǎng)數(shù)據(jù)，同時對簡化后河網(wǎng)數(shù)據(jù)執(zhí)行拓?fù)洳灰恢碌臋z測與消除。以下為三個不同尺度下的河網(wǎng)數(shù)據(jù)視圖（圖4）。
圖4 多尺度河網(wǎng)數(shù)據(jù)視圖
4 結(jié) 語
河網(wǎng)數(shù)據(jù)多尺度簡化涉及河流選取、簡化算法、拓?fù)湟恢滦跃S護(hù)等內(nèi)容。本文提出的河網(wǎng)多尺度組織結(jié)構(gòu)在滿足拓?fù)湟恢滦缘那疤嵯聦崿F(xiàn)了河網(wǎng)的多尺度動態(tài)生成。該結(jié)構(gòu)首先根據(jù)河流的尺寸與層次性計算河流權(quán)重，以權(quán)重作為河流選取的指標(biāo)，然后逐河流建立線性BLG樹，以結(jié)點偏離量作為河流的簡化依據(jù)?；诤泳W(wǎng)多尺度組織結(jié)構(gòu)開發(fā)了實驗系統(tǒng)并驗證了其有效性。但在拓?fù)湟恢滦跃S護(hù)算法的時間效率方面仍有待進(jìn)一步研究。
猜你喜歡
基于小世界網(wǎng)絡(luò)的海河流域河網(wǎng)結(jié)構(gòu)及功能響應(yīng)水科學(xué)進(jìn)展(2023年4期)2023-10-07 11:23:44 關(guān)注減污降碳協(xié)同的一致性和整體性公民與法治(2022年5期)2022-07-29 00:47:28 注重教、學(xué)、評一致性 提高一輪復(fù)習(xí)效率教學(xué)考試(高考物理)(2021年5期)2021-11-08 10:31:22 IOl-master 700和Pentacam測量Kappa角一致性分析中醫(yī)眼耳鼻喉雜志(2021年1期)2021-07-22 07:38:14 基于PSR模型的上海地區(qū)河網(wǎng)脆弱性探討華東師范大學(xué)學(xué)報（自然科學(xué)版）(2019年3期)2019-06-24 05:29:09 Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點個數(shù)估計數(shù)學(xué)物理學(xué)報(2018年1期)2018-03-26 08:16:42 不同引水水源對平原河網(wǎng)影響分析水利科技與經(jīng)濟(jì)(2017年5期)2017-04-22 02:39:28 MIKE11模型在城市河網(wǎng)生態(tài)調(diào)水工程中的應(yīng)用水利科技與經(jīng)濟(jì)(2016年9期)2016-04-22 01:07:22 基于事件觸發(fā)的多智能體輸入飽和一致性控制燕山大學(xué)學(xué)報(2015年4期)2015-12-25 02:19:49 基于Raspberry PI為結(jié)點的天氣云測量網(wǎng)絡(luò)實現(xiàn)電子設(shè)計工程(2014年12期)2014-02-27 11:58:23
操震洲姜林燕吳煜心
（1.南京工業(yè)大學(xué)測繪科學(xué)與技術(shù)學(xué)院，江蘇 南京211816;2.江蘇省金威遙感數(shù)據(jù)工程有限公司，江蘇 南京210000）
0 引 言
在傳統(tǒng)制圖綜合領(lǐng)域，對河流選取與簡化等問題有較深入的研究。在河流選取方面，一般通過一元回歸模型、多元回歸模型、開方根規(guī)律等確定河流的總體選取數(shù)量[1]。在具體選取時，通常根據(jù)河流的長度、級別等指標(biāo)確定河流的重要程度，然后選取較重要河流、舍去較次要河流。例如，張青年，艾廷華，姜莉莉等[1-3]分別提出以河流等級、匯水區(qū)域面積、流域為選取指標(biāo)的水系綜合方法。竇世卿等[4-7]對河流的簡化進(jìn)行了研究，河流簡化主要涉及到簡化算法和簡化后數(shù)據(jù)的拓?fù)湟恢滦跃S護(hù)問題。Douglas-Peucker算法[8]是所有曲線簡化算法中公認(rèn)最優(yōu)秀的，但其時間復(fù)雜度高。為提高Douglas-Peucker算法的時間性能，艾波等[7]提出采用線性BLG樹結(jié)構(gòu)事先存貯結(jié)點偏離量的方法。采用該線性BLG樹能有效縮短曲線的簡化時間。在圖形簡化過程中，空間目標(biāo)之間的拓?fù)潢P(guān)系也會發(fā)生變化[9]，主要表現(xiàn)為出現(xiàn)拓?fù)洳灰恢?。簡化后?shù)據(jù)的拓?fù)湟恢滦员仨毜玫奖ＷC，這是數(shù)據(jù)可用性的前提。Saalfeld[10]對簡化后數(shù)據(jù)的拓?fù)洳灰恢聠栴}進(jìn)行了研究并提出了解決方法，但Saalfeld的方法是有局限性的。Da Silva ACG 等[11-12]對Saalfeld的方法進(jìn)行了改進(jìn)和完善，使之可適用于點、線、面的拓?fù)湟恢滦跃S護(hù)。河流選取既要考慮河流的尺寸大小，也要考慮河流的主、支流關(guān)系。當(dāng)支流被選取時，主流也應(yīng)被選取。在以上研究中，都未能同時顧及這兩個因素。另外，河流的簡化和拓?fù)湟恢滦蕴幚碣M時較長，目前已有算法在時間性能上不夠理想，不適合實時性要求高的應(yīng)用。
1 河流選取的指標(biāo)
面向電子顯示設(shè)備的要素選取通?；谝爻叽?，如牛方曲等[13]提出的以要素屏幕面積作為選取指標(biāo)的面要素多尺度顯示方法。在河流的選取中，河流尺寸是河流選取時應(yīng)考慮的第一個因素。在小尺度河網(wǎng)數(shù)據(jù)中，只需要顯示較大尺寸的河流，在大尺度河網(wǎng)數(shù)據(jù)中，則可顯示較小尺寸的河流。另外，河流分為主流與支流，主、支流之間構(gòu)成層次關(guān)系。例如，圖1中的河流1與河流2、3、4分別構(gòu)成了主流與支流的上下層關(guān)系（圖1的河流號標(biāo)記在各河流的首尾兩端處），河流2和河流5也構(gòu)成了主、支流層次關(guān)系。在選取時，若選取支流，則對應(yīng)的主流也應(yīng)被選取。因此，河流的層次性是選取時要考慮的第二個因素。
本文綜合考慮河流的尺寸與層次性，并統(tǒng)一量化為權(quán)重指標(biāo)，以該指標(biāo)作為河流選取的標(biāo)準(zhǔn)。權(quán)重指標(biāo)的計算方法為:首先計算各河流的最小外接矩形，以最小外接矩形的長邊值作為對應(yīng)河流的初始權(quán)重值;然后按河流層次關(guān)系建立河系樹，樹結(jié)點值為河流的初始權(quán)重值;對河系樹中各父子結(jié)點值進(jìn)行檢查并調(diào)整，從葉結(jié)點開始，若結(jié)點權(quán)重值大于其父結(jié)點值，則將其父結(jié)點權(quán)重修改為該結(jié)點的值，若結(jié)點權(quán)重值小于對應(yīng)父結(jié)點值，則無需調(diào)整。按調(diào)整后的權(quán)重大小選取河流，這樣既保證了尺寸大的河流先被選取，又保證當(dāng)某支流被選取后，其對應(yīng)的主流也一并被選取。
河流權(quán)重指標(biāo)計算方法下所示（圖1）。
圖1 河流權(quán)重的計算方法
2 河網(wǎng)多尺度組織結(jié)構(gòu)
通過曲線簡化方法生成多尺度河網(wǎng)。Douglas-Peucker算法是公認(rèn)最優(yōu)秀的曲線簡化算法，但其時間復(fù)雜度為O（n2）（n為結(jié)點數(shù)），不適合大數(shù)據(jù)量的實時簡化。為提高Douglas-Peucker算法的時間性能，先后提出了多種方法如BLG樹結(jié)構(gòu)、BLG樹的線性表結(jié)構(gòu)存貯等。本文方法是按Douglas-Peucker算法事先計算河流的各結(jié)點偏離量，并以線性BLG結(jié)構(gòu)存貯，然后按存貯的結(jié)點偏離量大小篩選結(jié)點以實現(xiàn)河流簡化的。該方法可將Douglas-Peucker算法的時間復(fù)雜度從O（n2）降為O（n）。在圖形簡化后，空間對象之間可能會出現(xiàn)拓?fù)洳灰恢?。拓?fù)洳灰恢骂愋涂煞譃閮煞N:① 由原來的相鄰、相交關(guān)系變?yōu)橄嚯x關(guān)系;② 由原來的相離關(guān)系變?yōu)橄噜徎蛳嘟魂P(guān)系。出現(xiàn)第一類拓?fù)洳灰恢碌脑蚴遣缓侠韯h除了多要素的公共交點或鄰接點，第二類拓?fù)洳灰恢卤憩F(xiàn)為出現(xiàn)不該有的線段相交和自相交。本文對河網(wǎng)拓?fù)湟恢滦缘木S護(hù)方法為:① 規(guī)定約束點不可刪除，這樣可避免第一類拓?fù)洳灰恢碌陌l(fā)生;② 對結(jié)點刪除后的新生成線段進(jìn)行判斷，消除不合理的相交，這樣可消除第二類拓?fù)洳灰恢?，保證簡化后河網(wǎng)的拓?fù)湟恢滦浴７Q河流的端點、多條河流間的交匯點為約束點，河網(wǎng)的多尺度組織結(jié)構(gòu)可按以下方法生成。
（1）逐河流執(zhí)行Douglas-Peucker算法，生成BLG樹，將各結(jié)點偏離量線性存貯，生成線性BLG樹結(jié)構(gòu)。
（2）計算河流的最小外接矩形，計算各河流的初始權(quán)重值。
（3）按河流層次關(guān)系河系樹，調(diào)整樹中父子結(jié)點的權(quán)重值。
（4）為保證河流約束點在簡化中不被刪除，將河流約束點偏離量修改為該河流的權(quán)重值，以保證約束點在簡化中總是被選取。
河流2的線性BLG樹的生成過程如下所示（圖2）。其中，河流2的約束點有端點P21、P27，河流交匯點P23。
圖2 單條河流的結(jié)點偏離量計算過程
按以上方式建立各河流的線性BLG樹后，線性BLG樹的開始兩個結(jié)點存貯了河流的權(quán)重值，可基于它進(jìn)行河流選取，而在其他結(jié)點存貯結(jié)點偏離量信息，可基于它進(jìn)行河流簡化。由于該線性BLG樹已按河流的層次關(guān)系調(diào)整了權(quán)重值，所以能保證當(dāng)支流被選取時，其對應(yīng)的主流也會被選取。同時，該線性BLG樹修改了約束點的偏離量值，所以可以避免第一類拓?fù)洳灰恢碌陌l(fā)生。
對于可能出現(xiàn)的第二類拓?fù)洳灰恢拢砂碊a Silva ACG等[11-12]的方法來處理。如圖3所示，實線C、虛線C’分別代表簡化前后的河流。線段L1L2的端點L1落在多邊形v4v5v6v7內(nèi)，表明出現(xiàn)了拓?fù)洳灰恢?。此時可通過恢復(fù)結(jié)點的方式消除拓?fù)洳灰恢隆?/p>
圖3 拓?fù)洚惓Ｅ卸ú呗?/p>
該河網(wǎng)組織結(jié)構(gòu)可根據(jù)用戶需求快速生成保持拓?fù)湟恢滦缘亩喑叨群泳W(wǎng)數(shù)據(jù)。記當(dāng)前選取和簡化的尺度分別為r1、r2，則當(dāng)前尺度下的河網(wǎng)數(shù)據(jù)生成過程如下:
①根據(jù)r1檢索河流，選取權(quán)重≥r1的所有河流;② 對所有選中的河流，選取偏離量≥r2的所有結(jié)點;③ 對上一步新生成的所有線段，按圖3的方法檢測拓?fù)洳灰恢?，通過恢復(fù)結(jié)點消除拓?fù)洳灰恢?④ 輸出當(dāng)前尺度下的河網(wǎng)數(shù)據(jù)。
3 實驗及分析
基于.NET平臺開發(fā)了實驗系統(tǒng)，測試河網(wǎng)多尺度組織結(jié)構(gòu)的有效性。數(shù)據(jù)源為Shapefile格式文件，實驗程序讀取Shapefile格式河網(wǎng)數(shù)據(jù)，按本文方法建立河網(wǎng)多尺度組織結(jié)構(gòu)。實驗程序根據(jù)用戶的設(shè)置，動態(tài)生成任意尺度的河網(wǎng)數(shù)據(jù)，同時對簡化后河網(wǎng)數(shù)據(jù)執(zhí)行拓?fù)洳灰恢碌臋z測與消除。以下為三個不同尺度下的河網(wǎng)數(shù)據(jù)視圖（圖4）。
圖4 多尺度河網(wǎng)數(shù)據(jù)視圖
4 結(jié) 語
河網(wǎng)數(shù)據(jù)多尺度簡化涉及河流選取、簡化算法、拓?fù)湟恢滦跃S護(hù)等內(nèi)容。本文提出的河網(wǎng)多尺度組織結(jié)構(gòu)在滿足拓?fù)湟恢滦缘那疤嵯聦崿F(xiàn)了河網(wǎng)的多尺度動態(tài)生成。該結(jié)構(gòu)首先根據(jù)河流的尺寸與層次性計算河流權(quán)重，以權(quán)重作為河流選取的指標(biāo)，然后逐河流建立線性BLG樹，以結(jié)點偏離量作為河流的簡化依據(jù)?；诤泳W(wǎng)多尺度組織結(jié)構(gòu)開發(fā)了實驗系統(tǒng)并驗證了其有效性。但在拓?fù)湟恢滦跃S護(hù)算法的時間效率方面仍有待進(jìn)一步研究。
猜你喜歡
水科學(xué)進(jìn)展(2023年4期)2023-10-07 11:23:44
公民與法治(2022年5期)2022-07-29 00:47:28
教學(xué)考試(高考物理)(2021年5期)2021-11-08 10:31:22
中醫(yī)眼耳鼻喉雜志(2021年1期)2021-07-22 07:38:14
華東師范大學(xué)學(xué)報（自然科學(xué)版）(2019年3期)2019-06-24 05:29:09
數(shù)學(xué)物理學(xué)報(2018年1期)2018-03-26 08:16:42
水利科技與經(jīng)濟(jì)(2017年5期)2017-04-22 02:39:28
水利科技與經(jīng)濟(jì)(2016年9期)2016-04-22 01:07:22
燕山大學(xué)學(xué)報(2015年4期)2015-12-25 02:19:49
電子設(shè)計工程(2014年12期)2014-02-27 11:58:23
