顧及拓撲一致性的水系三維曲線化簡

劉民士，龍　毅，費立凡

1. 南京師范大學(xué)地理科學(xué)學(xué)院，江蘇 南京210023； 2. 虛擬地理環(huán)境教育部重點實驗室，江蘇 南京210023； 3. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京210023； 4. 滁州學(xué)院地理信息與旅游學(xué)院,安徽 滁州 239000; 5. 安徽省地理信息集成應(yīng)用協(xié)同創(chuàng)新中心，安徽 滁州 239000

?

顧及拓撲一致性的水系三維曲線化簡

劉民士1,2,3,4,5，龍毅1,2,3，費立凡4,5

1. 南京師范大學(xué)地理科學(xué)學(xué)院，江蘇 南京210023； 2. 虛擬地理環(huán)境教育部重點實驗室，江蘇 南京210023； 3. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京210023； 4. 滁州學(xué)院地理信息與旅游學(xué)院,安徽 滁州 239000; 5. 安徽省地理信息集成應(yīng)用協(xié)同創(chuàng)新中心，安徽 滁州 239000

摘要：鑒于常規(guī)曲線化簡方法應(yīng)用于水系曲線化簡時難以顧及水系要素的三維特征及其拓撲關(guān)系，本文提出了一種顧及拓撲一致性的水系三維曲線化簡方法。該方法首先對D-P算法進行三維擴展,實現(xiàn)水系中單條河流三維曲線化簡，然后構(gòu)建水系樹結(jié)構(gòu)表達其拓撲關(guān)系，最后按照水系樹的層次順序依次進行河流曲線化簡和干流與支流的拓撲關(guān)系重構(gòu)。試驗結(jié)果表明，該方法化簡精度高，既能保持水系的三維形態(tài)特征，又能保證河流交匯處的拓撲一致性。

關(guān)鍵詞：D-P算法；拓撲關(guān)系；三維曲線化簡；水系化簡

地貌與水系的自動綜合是地圖自動綜合的重要研究內(nèi)容，而水系作為地貌的骨架線，它的綜合對其他要素有一定的控制和制約作用，其重要性通常要高于地貌要素[1]。近年來，關(guān)于水系的綜合研究眾多，主要集中在水系選取方法上，取得了較多的成果[2-4]，而對水系曲線化簡的研究較少。究其原因，是因為水系各河流之間的等級結(jié)構(gòu)使其差異明顯，更適合于選取，并且通常也認為水系的形態(tài)相對簡單，采用常規(guī)的曲線化簡方法即可。

目前，曲線化簡方法分為以下3類：一是基于幾何特征分析的曲線化簡方法，這類方法也稱作點位信息度量方法[5]，即從幾何特征角度分析曲線上各點的信息量大小，從而決定點是否選取，這類方法主要有D-P法[6]及其改進方法[7-9]、LI-OPENSHOW法[10-11]；二是基于結(jié)構(gòu)特征分析的曲線化簡方法，這類方法以曲線的彎曲結(jié)構(gòu)為分析對象，通過對彎曲進行提取、結(jié)構(gòu)組織與特征分析從而確定彎曲的保留與刪除[12-15]；三是基于數(shù)學(xué)分析的曲線化簡方法，主要有采用分形分析方法[16-17]和小波分析方法[18-19]。

然而，以上曲線化簡方法都是針對二維曲線，且是對單條曲線處理。因此，當(dāng)應(yīng)用到水系曲線化簡時，就存在以下兩個問題：一是化簡難以體現(xiàn)三維形態(tài)特征，特別是面對水系的“疊水”現(xiàn)象，難以保留其“疊水”特征(如圖1所示)，雖然文獻[20]提出利用3D D-P算法對等高線進行三維綜合化簡，但該方法的本質(zhì)是將等高線看成三維散點，進行“體”的綜合，并不是直接對三維曲線進行化簡，故其并不適合于水系三維曲線化簡；二是難以維護河流之間的拓撲關(guān)系，常規(guī)處理方法是將河流數(shù)據(jù)在交匯點處先分段再化簡，如文獻[21]采用分段D-P化簡方法保留交匯點從而維護其拓撲關(guān)系，然而，河流分段將破壞河流曲線的整體形態(tài)特征。事實上，要保持水系拓撲關(guān)系的一致性，并不意味著水系交匯點的幾何位置在化簡過程不能變化，反而，從多尺度表達的角度上看，水系交匯點的幾何位置原本就應(yīng)該隨著水系綜合的程度而相應(yīng)變化。

因此，本文對D-P算法進行三維曲線化簡擴展，提出一種顧及拓撲一致性的水系三維曲線化簡方法，在化簡過程中既能保持水系三維形態(tài)，又能保證水系拓撲關(guān)系。

1顧及拓撲一致性的水系三維曲線化簡方法

1.1基本思路

顧及拓撲一致性的水系三維曲線化簡方法，需要解決兩個問題：一是如何保持三維形態(tài)特征；二是如何維護水系中河流之間的拓撲關(guān)系。針對前者，將D-P算法進行三維曲線化簡擴展，以點到空間直線的三維點線距代替平面上的點線距，從而使特征點的選取能顧及到整個三維形態(tài)特征。對于后者，通過構(gòu)建水系樹結(jié)構(gòu)表達河流拓撲關(guān)系，并按照先干流后支流的順序進行化簡，在化簡之后，檢測河流交匯點處的拓撲關(guān)系并進行拓撲重構(gòu)，從而保持河流交匯處的拓撲一致性。

圖1　水系的“疊水”特征Fig.1　The superimposed characteristic of water system

1.2D-P算法在三維曲線化簡上的擴展

圖2　三維擴展D-P算法的三維點線距表達Fig.2　Three-dimensional point-line distance principle of 3D extended D-P algorithm

1.3水系樹結(jié)構(gòu)建立

水系樹結(jié)構(gòu)的構(gòu)建關(guān)鍵在于建立干流與支流的關(guān)系，文獻[22]給出完整的河系樹結(jié)構(gòu)建立方法，但其構(gòu)建的河系樹結(jié)構(gòu)只包含河流編號之間的父子關(guān)系，缺少河流交匯點信息，且該方法通過人為指定確定主干流，不利于全自動處理，尤其是當(dāng)水系數(shù)據(jù)中包含多個河系，多條主干流時。為了便于水系中河流交匯點的描述與處理，本文設(shè)計了一個河流信息結(jié)構(gòu)RS，其包括河流本身標識BID、該河流匯入的河流標識TID(“父”河流或干流河流)以及河流匯點坐標SP3個要素。該結(jié)構(gòu)的設(shè)計是基于每一條河流僅匯入一條干流河流或不匯入任何河流，如果是后者，則該河流為主干流。從樹的邏輯結(jié)構(gòu)來看，水系樹結(jié)構(gòu)是由節(jié)點組成的，每個節(jié)點包括一個數(shù)據(jù)域和若干個指針域，RS即為該節(jié)點的數(shù)據(jù)域，而其指針域則存儲干流與支流的關(guān)系。

水系樹結(jié)構(gòu)的建立過程分為河流信息結(jié)構(gòu)構(gòu)造(RS構(gòu)造)、主干流確定，干流-支流關(guān)系建立3步：①RS構(gòu)造：RS包括BID、TID、SP3要素，其中BID可直接從當(dāng)前河流數(shù)據(jù)中獲取，SP可通過比較河流兩個端點高程的大小確定(高程值小即為河流匯點SP)，TID則通過遍歷其他所有河流的所有點，找到與SP坐標一致的點，該點所在的河流標識即為TID；②主干流確定：由于主干流不匯入任何河流，因此當(dāng)某河流RS結(jié)構(gòu)中的TID數(shù)據(jù)為空(其值可設(shè)為-1)，則為主干流，故RS構(gòu)造后主干流即可確定；③干流-支流關(guān)系建立：采用從上至下的層次構(gòu)建方法，即從主干流開始，依次建立各干流-支流的關(guān)系。首先從主干流的RS結(jié)構(gòu)中獲取其河流標識，記為BID0；然后依次遍歷其他所有河流RS結(jié)構(gòu)中的干流河流標識，記為TIDi；最后查找與BID0相等的TIDi，將相匹配的河流記為主干流的一級支流。同理，根據(jù)一級支流確定二級支流，依次進行，整個水系樹結(jié)構(gòu)建立成功。圖3為水系示意圖，其中數(shù)字1—10為各條河流，字母A—J則為各個交匯點，圖4為根據(jù)圖3構(gòu)建的水系樹結(jié)構(gòu)圖，其中字母A—J表示交匯點SP，第1個數(shù)字表示結(jié)點當(dāng)前河流的編號BID，第2個數(shù)字表示匯入河流編號TID，其中，-1表示河流不存在。

圖3　水系示意圖Fig.3　Schematic diagram of water system

圖4　水系樹結(jié)構(gòu)Fig.4　Tree structure of water system

1.4拓撲關(guān)系變化檢測與重構(gòu)

干流化簡后，原有交匯點處拓撲關(guān)系可能破壞，因此需要進行拓撲關(guān)系變化檢測與拓撲重構(gòu)，拓撲重構(gòu)過程又分為干流交匯點重新生成和支流匯點移位兩個過程。

1.4.1拓撲關(guān)系變化檢測

交匯點處拓撲關(guān)系是否變化，是在干流化簡后，判斷該交匯點是否仍然存在于干流曲線上。由于單條河流曲線上高程值是單調(diào)變化的，從河流源點到匯點高程逐漸降低，因此，可以從干流源點開始依次遍歷曲線上點，判斷該點的高程Zi與交匯點高程Zsp的關(guān)系：如果Zi=Zsp，則遍歷結(jié)束，交匯點存在，拓撲關(guān)系沒有變化；如果Zi

1.4.2干流交匯點重新生成

當(dāng)干流中的交匯點刪除后，需要生成新的交匯點，新的交匯點應(yīng)取支流匯點到干流的舊交匯點相鄰兩點(未被刪除)所構(gòu)空間直線的垂足。如圖5所示，干流R1的交匯點Qi刪除后，從支流R2的匯點Pn作空間直線Qi-1Qi+1的垂足O為新的交匯點?？紤]到空間直線Qi-1Qi+1相對于支流前進的方向有可能后退，即PnO與PnPn-1所成夾角θ小于90°(圖5(b))，此時，支流流向不合常理，因此從Pn點逆流向上依次取支流上的點，重新計算相應(yīng)的垂足O與角度θ，直到θ大于90°為止(圖5(b)中O′點為新交匯點)。

圖5　拓撲重構(gòu)過程Fig.5　Process of topology reconstruction

1.4.3支流匯點移位

新交匯點O生成之后，就需將支流的匯點移位到該點位置，因此將河流R2的SP結(jié)構(gòu)中的匯點SP重置為O點；同時，修改R2的河流數(shù)據(jù)，根據(jù)在上述干流交匯點重新生成過程獲得到支流匯點的前一點Pi(圖5(a)中為Pn，5(b)中為Pn-1)，將Pi后續(xù)點刪除，并在Pi之后插入O點。

2試驗與分析

2.1試驗設(shè)計

試驗過程采用兩份1∶5萬水系數(shù)據(jù)，數(shù)據(jù)1是丘陵地貌區(qū)域的水系，其等高線間距為10 m，河流條數(shù)28條(圖6(a))；數(shù)據(jù)2是黃土地貌區(qū)域的水系，其等高線間距為20 m，河流條數(shù)21條(圖6(b))。試驗采用D-P化簡方法[6]、分段D-P化簡方法[21]和本方法對數(shù)據(jù)進行9種尺度的化簡(壓縮率為0.1到0.9)?？紤]到原始河流數(shù)據(jù)通常為二維數(shù)據(jù)，必須先對水系數(shù)據(jù)進行三維化處理，水系三維化方法采用文獻[23]提出的根據(jù)等高線進行反距離權(quán)重內(nèi)插與分段線性內(nèi)插相結(jié)合的方法，對河流源點與匯點采用反距離權(quán)重插值計算高程，對其他內(nèi)部點先計算河流與等高線的交點，然后以相鄰交點對河流分段，之后采用流水線線性內(nèi)插方法計算高程。此外，為了能得到固定的壓縮率，采用“智能阻尼震蕩法”[24]，通過一個可變步長智能調(diào)整閾值，直到化簡結(jié)果滿足預(yù)設(shè)的壓縮率為止。算法步驟如下，給定初始閾值dis、閾值調(diào)整的初始步長step、一個目標壓縮率rat_o和目標壓縮率的容差tol：

(1) 采用閾值dis進行化簡并計算壓縮率rat_c，并令diff=rat_c-rat_o；

(2) 如果|diff|≤tol，結(jié)束；否則，分以下4種情況分別處理返回步驟(1)：①如果diff<0，且上一次diff<0，則dis=dis+step；②如果diff<0，且上一次diff>0，則step=step/2，dis=dis+step；③如果diff>0，且上一次diff>0，則dis=dis-step；④如果diff>0，且上一次diff<0，則step=step/2，dis=dis-step。

圖6　水系試驗數(shù)據(jù)Fig.6　Experimental data of water system

2.2化簡精度對比分析

線化簡算法評價的研究很多，但主要集中在位置精度和形態(tài)結(jié)構(gòu)特征兩個方面[25]。文獻[26]提出應(yīng)從幾何精度、結(jié)構(gòu)形態(tài)、空間關(guān)系和適用范圍4個方面評估曲線化簡算法，其中前兩者分別對應(yīng)于位置精度與形態(tài)結(jié)構(gòu)特征。因此，考慮到水系化簡的實際情況，分別從幾何精度、結(jié)構(gòu)形態(tài)與空間關(guān)系3個方面對本方法進行評估。

2.2.1幾何精度評估

幾何精度評估的指標很多，如矢量位移、面積偏差、長度變化、曲折度等，各指標都存在一定的相關(guān)性。本文采用水系二維長度變化、三維長度變化(化簡后水系長度減去原始水系長度)為評價指標，將本方法與D-P法和分段D-P法對比分析。

圖7為數(shù)據(jù)1的水系長度變化對比圖，水系二維總長度為35 973.6m，三維總長度為37 086.9m。從二維長度變化來看，3種算法在各個壓縮率上結(jié)果都相差不大(圖7(a))，相比較而言，D-P算法的變化最??；從三維長度變化來看，D-P算法和分段D-P算法相差不大，而本方法的變化則要遠小于另外兩種方法，且隨著壓縮率的增加差距更大(圖7(b))。

圖7　3種化簡方法對數(shù)據(jù)1的水系長度變化對比Fig.7　Contrast among length change of water system using three methods in data 1

圖8為數(shù)據(jù)2的水系長度變化對比圖，河流二維總長度為87 109.1m，三維總長度為87 433.6m。從二維長度變化來看，3種算法差別很小，但仍然表現(xiàn)為隨壓縮率增大差距逐漸增大，相比較而言，本方法變化最小，D-P法次之(圖8(a))；從三維長度變化來看，本方法在各個壓縮率上的變化要明顯小于其他兩種算法，D-P法的變化比分段D-P法略小(圖8(b))。

圖8　3種化簡方法對數(shù)據(jù)2的水系長度變化對比Fig.8　Contrast among length change of water system using three methods in data 2

2.2.2結(jié)構(gòu)形態(tài)評估

評價曲線的形態(tài)結(jié)構(gòu)特征可從分維數(shù)和特征點保持兩方面進行[26]。文獻[26]提出基于分形理論評估化簡后曲線形態(tài)的一般方法，通過比較化簡后曲線分維數(shù)與原始曲線分維數(shù)的相似程度，從而判定算法優(yōu)劣。本文采用二維分維數(shù)與三維分維數(shù)為評價指標，前者基于二維曲線計算，后者基于三維曲線計算。分維數(shù)采用“腳規(guī)”法計算，通過不同步長量測曲線長度，并以線性回歸模型擬合[17,26]。

表1為本方法與D-P法化簡后水系分維數(shù)計算結(jié)果，其中數(shù)據(jù)1的原始二維分維數(shù)為1.038 16，三維分維數(shù)為1.037 89；數(shù)據(jù)2的原始二維分維數(shù)為1.036 84，三維分維數(shù)為1.036 83。圖8為根據(jù)表1生成的分維數(shù)變化(原始分維數(shù)減去化簡后分維數(shù))對比圖。對于二維分維數(shù)，本方法與D-P法相差不大，僅在個別壓縮尺度上，D-P法的變化更??；對于三維分維數(shù)，本方法在各個化簡尺度數(shù)據(jù)上的變化都明顯小于D-P法，尤其是數(shù)據(jù)1(圖9(a))表現(xiàn)更突出。

表1　本方法與D-P法化簡后水系分維數(shù)計算結(jié)果

圖9　D-P法與本方法化簡后水系分維數(shù)對比Fig.9　Contrast between fractal dimension of water system using this method and D-P algorithm

特征點保持主要考察不同化簡方法對二維、三維特征點的保留情況。圖10為本方法與D-P法在同一化簡尺度下水系特征點保留對比圖(部分)，其中圓點為本方法保留特征點，三角形點為D-P法保留特征點。從二維特征點保持來看，兩種方法差異不大，其保留的特征點都能較好呈現(xiàn)曲線的二維特征；然而，從三維特征點保持來看(借助地形)，本方法保留的特征點更好，尤其是像A、B等“疊水”位置，本方法保留的兩點為曲線上三維拐點，顯然優(yōu)于D-P保留的兩點。

2.2.3空間關(guān)系評估

水系的空間關(guān)系評估，主要是評價河流之間的拓撲關(guān)系一致性，即河流交匯處的拓撲關(guān)系能否保持。圖11為上述試驗數(shù)據(jù)在3種算法化簡后的部分結(jié)果圖(圖11(a)為本方法與D-P的對比，圖11(b)為本方法與分段D-P法的對比)，圖中灰色曲線為原始水系數(shù)據(jù)，黑色曲線為D-P算法化簡結(jié)果，紅色曲線為分段D-P算法化簡結(jié)果，綠色曲線為本方法化簡結(jié)果。如圖所示，D-P法不能保持河流交匯處的拓撲關(guān)系(圖11(a)紅色虛線圓圈處)，分段D-P算法和本方法能夠保持其拓撲關(guān)系一致性，但分段D-P算法通過對干流曲線分段，降低了干流曲線化簡精度，而本方法通過重構(gòu)交匯點，使之不影響干流化簡精度(圖11(b))。

圖11　3種算法化簡后拓撲一致性結(jié)果對比(部分)Fig.11　Contrast among topological consistency of water system using three methods

3結(jié)論

本文提出了顧及拓撲一致性的三維水系化簡方法，通過構(gòu)建水系樹結(jié)構(gòu)、三維曲線擴展的D-P算法以及拓撲一致性檢測與拓撲重構(gòu)處理方法，實現(xiàn)了保持拓撲一致性的水系三維形態(tài)化簡并進行了試驗驗證。結(jié)果顯示：①該方法能保證河流間的拓撲關(guān)系，避免常規(guī)河流化簡出現(xiàn)的拓撲不一致現(xiàn)象，且其拓撲一致性處理更合理；②該方法化簡精度可靠，能最大限度地保證三維形態(tài)，隨著綜合尺度的增大，效果相對更優(yōu)。該方法的不足之處在于常規(guī)河流數(shù)據(jù)大多不包含高程信息，需在化簡之前先將河流曲線數(shù)據(jù)三維化，因此，設(shè)計一種快速高精度的水系高程信息提取方法非常關(guān)鍵，這也是后續(xù)的研究方向之一。

參考文獻：

[1]王家耀,孫群,王光霞,等. 地圖學(xué)原理與方法[M]. 北京: 科學(xué)出版社, 2006: 209-339.

WANG Jiayao, SUN Qun, WANG Guangxia, et al. Principle and Method of Cartography[M]. Beijing: Science Press, 2006: 209-339.

[2]張青年. 顧及密度差異的河系簡化[J]. 測繪學(xué)報, 2006, 35(2): 191-196.

ZHANG Qingnian. Generalization of Drainage Network with Density Differences[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(2): 191-196.

[3]艾廷華,劉耀林,黃亞鋒.河網(wǎng)匯水區(qū)域的層次化剖分與地圖綜合[J]. 測繪學(xué)報, 2007, 36(2): 231-236, 243.

AI Tinghua, LIU Yaolin, HUANG Yafeng. The Hierarchical Watershed Partitioning and Generalization of River Network[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(2): 231-236, 243.

[4]STANISLAWSKI L V. Feature Pruning by Upstream Drainage Area to Support Automated Generalization of the United States National Hydrography Dataset[J]. Computers, Environment and Urban Systems, 2009, 33(5): 325-333.

[5]鄧敏,陳杰,李志林,等. 曲線簡化中節(jié)點重要性度量方法比較及垂比弦法的改進[J]. 地理與地理信息科學(xué), 2009, 25(1): 40-43.

DENG Min, CHEN Jie, LI Zhilin, et al. An Improved Local Measure Method for the Importance of Vertices in Curve Simplification[J]. Geography and Geo-Information Science, 2009, 25(1): 40-43.

[6]DOUGLAS D H, PEUCKER T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[7]VAN OOSTEROM P, SCHENKELAARS V. The Development of an Interactive Multi-scale GIS[J]. International Journal of Geographical Information Systems, 1995, 9(5): 489-507.

[8]毋河海. 基于多叉樹結(jié)構(gòu)的曲線綜合算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2004, 29(6): 479-483.

WU Hehai. Multi-Way Tree Structure Based on Curve Generalization Method[J]. Geomatics and Information Science of Wuhan University, 2004, 29(6): 479-483.

[9]陳軼, 彭認燦, 鄭義東, 等. 基于Douglas雙側(cè)多叉樹的曲線綜合算法研究[J]. 測繪學(xué)報, 2010, 39(3): 310-315.

CHEN Yi, PENG Rencan, ZHENG Yidong, et al. Line Generalization Based on Douglas Both-sides Multi-way Tree[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3): 310-315.

[10]LI Zhilin, OPENSHAW S. Algorithms for Automated Line Generalization1 Based on a Natural Principle of Objective Generalization[J]. International Journal of Geographical Information Systems, 1992, 6(5): 373-389.

[11]朱鯤鵬, 武芳, 王輝連, 等. Li-Openshaw算法的改進與評價[J]. 測繪學(xué)報, 2007, 36(4): 450-456.

ZHU Kunpeng, WU Fang, WANG Huilian, et al. Improvement and Assessment of Li-Openshaw Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 450-456.

[12]艾廷華, 郭仁忠, 劉耀林. 曲線彎曲深度層次結(jié)構(gòu)的二叉樹表達[J]. 測繪學(xué)報, 2001, 30(4): 343-348.

AI Tinghua, GUO Renzhong, LIU Yaolin. A Binary Tree Representation of Curve Hierarchical Structure in Depth[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(4): 343-348.

[13]WANG Zeshen, MüLLER J C. Line Generalization Based on Analysis of Shape Characteristics[J]. Cartography and Geographic Information Systems, 1998, 25(1): 3-15.

[14]錢海忠, 武芳, 陳波, 等. 采用斜拉式彎曲劃分的曲線化簡方法[J]. 測繪學(xué)報, 2007, 36(4): 443-449, 456.

QIAN Haizhong, WU Fang, CHEN Bo, et al. Simplifying Line with Oblique Dividing Curve Method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 443-449, 456.

[15]DU Shihong.Analyzing Topological Changes for Structural Shape Simplification[J]. Journal of Visual Languages & Computing, 2014, 25(4): 316-332.

[16]MULLER J C. Fractal and Automated Line Generalization[J]. The Cartographic Journal, 1987, 24(1): 27-34.

[17]王橋. 線狀地圖要素的自相似性分析及其自動綜合[J]. 武漢測繪科技大學(xué)學(xué)報, 1995, 20(2): 123-128.

WANG Qiao. Self-Similarity Analysis of Cartographic Lines and the Automated Line Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1995, 20(2): 123-128.

[18]吳紀桃, 王橋. 小波分析在GIS線狀數(shù)據(jù)圖形簡化中的應(yīng)用研究[J]. 測繪學(xué)報, 2000, 29(1): 71-75.

WU Jitao, WANG Qiao. A Study on Automatic Cartographic Generalization Using Wavelet Analysis in GIS[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(1): 71-75.

[19]朱長青,王玉海,李清泉, 等. 基于小波分析的等高線數(shù)據(jù)壓縮模型[J]. 中國圖象圖形學(xué)報, 2004, 9(7): 841-845.

ZHU Changqing, WANG Yuhai, LI Qingquan, et al. A Model to Compress Contour Data Based on Wavelet Analysis[J]. Journal of Image and Graphics, 2004, 9(7): 841-845.

[20]何津, 費立凡, 黃麗娜, 等. 三維Douglas-Peucker算法的等高線間接綜合方法研究[J]. 測繪學(xué)報, 2013, 42(3): 467-473.

HE Jin, FEI Lifan, HUANG Li’na, et al. Study on the Method of Indirect Generalization for Contour Lines Based on the 3D Douglas-Peucker Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3): 467-473.

[21]應(yīng)申, 李霖. 基于約束點的曲線一致性化簡[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2003, 28(4): 488-491.

YING Shen, LI lin. Consistent Line Simplification Based on Constraint Points[J]. Geomatics and Information Science of Wuhan University, 2003, 28(4): 488-491.

[22]毋河海. 河系樹結(jié)構(gòu)的自動建立[J]. 武漢測繪科技大學(xué)學(xué)報, 1995, 20(S): 7-14.

WU Hehai. Automatic Establishment of River Tree Structure[J]. Journal of the Wuhan Technical University of Surveying and Mapping, 1995, 20(S): 7-14.

[23]黃麗娜. 基于廣義DEM的地貌與水系要素一體化綜合研究[D]. 武漢: 武漢大學(xué), 2010: 97-99.

HUANG Li’na. Study on the Integrated Generalization of Relief and Water System Based on General DEM[D]. Wuhan: Wuhan University, 2010: 97-99.

[24]何津, 費立凡. 解決圖形沖突的受限變形所涉及的數(shù)學(xué)原則—以道路與建筑物的關(guān)系為例[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2007, 32(4): 326-330.

HE Jin, FEI Lifan. Mathematical Methods Involved in Constrained Reshaping for Solving Graphic Conflicts between Streets and Buildings[J]. Geomatics and Information Science of Wuhan University, 2007, 32(4): 326-330.

[25]鄧敏, 樊子德, 劉慧敏. 層次信息量的線要素化簡算法評價研究[J]. 測繪學(xué)報, 2013, 42(5): 767-773, 781.

DENG Min, FAN Zide, LIU Huimin. Performance Evaluation of Line Simplification Algorithms Based on Hierarchical Information Content[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5): 767-773, 781.

[26]武芳, 鄧紅艷, 錢海忠, 等. 地圖自動綜合質(zhì)量評估模型[M]. 北京: 科學(xué)出版社, 2009: 95-138.

WU Fang, DENG Hongyan, QIAN Haizhong, et al. Quality Assess Model of Map Automatic Generalization[M]. Beijing: Science Press, 2009: 95-138.

(責(zé)任編輯：宋啟凡)

修回日期： 2016-01-06

First author： LIU Minshi( 1983—), lecturer, PhD candidate，majors in automatic map generalization.

E-mail： liuminshi1983@126.com

E-mail： longyi@njnu.edu.cn

Line Simplification of Three-dimensional Drainage Considering Topological Consistency

LIU Minshi1,2,3,4,5，LONG Yi1,2,3，F(xiàn)EI Lifan4,5

1. School of Geography Science, Nanjing Normal University, Nanjing 210023,China; 2. Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing 210023,China; 3. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023,China; 4. School of Geographic Information and Tourism, Chuzhou University, Chuzhou 239000, China; 5. Anhui Center for Collaborative Innovation in Geographical Information Integration and Application, Chuzhou 239000, China

Abstract：In view of the fact that drainage line simplification using conversional methods is usually hard to keep the three-dimensional characteristics and topological relationships, this paper proposes a new method of three-dimensional drainage line simplification which maintains topological consistency. It firstly expends the conversional D-P algorithm to three-dimensional in order to keep three-dimensional characteristics during the simplification. Then it constructs tree structures for drainage lines to express their topological relations. Finally, it simplifies river lines and reconstructs topological relations of main streams and their branches according to the hierarchical order of water system tree. The experimental results show that this method has a higher accuracy in simplification and can maintain not only three-dimensional shape characteristics of water system but also the topological consistency at river confluences.

Key words：D-P algorithm; topological relationship; three-dimensional line simplification; water system simplification

Corresponding author：LONG Yi

通信作者：龍毅

第一作者簡介：劉民士(1983—)，講師，博士生，主要從事地圖自動綜合的理論與方法研究。

收稿日期：2015-06-01

基金項目：國家自然科學(xué)基金(41171350;41301514;41501496)；滁州學(xué)院校級培育項目(2014PY03)

中圖分類號：P208

文獻標識碼：A

文章編號：1001-1595(2016)04-0494-08

Foundation support： The National Natural Science Foundation of China (Nos.41171350; 41301514; 41501496);The Cultivation Projiect of Chuzhou University (No.2014PY03)

引文格式：劉民士，龍毅，費立凡.顧及拓撲一致性的水系三維曲線化簡[J].測繪學(xué)報，2016,45(4)：494-501. DOI:10.11947/j.AGCS.2016.20150288.

LIU Minshi，LONG Yi，F(xiàn)EI Lifan.Line Simplification of Three-dimensional Drainage Considering Topological Consistency[J]. Acta Geodaetica et Cartographica Sinica,2016,45(4):494-501. DOI:10.11947/j.AGCS.2016.20150288.