竇世卿，趙學(xué)勝，劉成軍，林亞文，趙艷芹

1. 中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院，北京100083； 2. 黑龍江科技大學(xué)礦業(yè)工程學(xué)院，黑龍江 哈爾濱 150022； 3. 北京地林偉業(yè)信息技術(shù)有限責(zé)任公司，北京 100036； 4. 黑龍江科技大學(xué)計算機與信息工程學(xué)院，黑龍江 哈爾濱 150022

?

河網(wǎng)線要素與DEM綜合的三維Douglas-Peucker算法

竇世卿1,2，趙學(xué)勝1，劉成軍2，林亞文3，趙艷芹4

1. 中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院，北京100083； 2. 黑龍江科技大學(xué)礦業(yè)工程學(xué)院，黑龍江 哈爾濱 150022； 3. 北京地林偉業(yè)信息技術(shù)有限責(zé)任公司，北京 100036； 4. 黑龍江科技大學(xué)計算機與信息工程學(xué)院，黑龍江 哈爾濱 150022

摘要：目前三維Douglas-Peucker(3D_DP)算法主要應(yīng)用于單一類型的DEM綜合。本文引入“彎曲調(diào)節(jié)指數(shù)”來改進(jìn)3D_DP算法，提出了一種三維空間河網(wǎng)要素與DEM綜合的新方法，即將河網(wǎng)線矢量提取成三維離散點數(shù)據(jù)集(增加高程屬性)，與DEM三維離散點數(shù)據(jù)集合并，在河網(wǎng)層次化選取基礎(chǔ)上，利用改進(jìn)的3D_DP算法對合并數(shù)據(jù)集進(jìn)行綜合操作。通過試驗結(jié)果的對比和分析表明，該方法通過彎曲調(diào)節(jié)指數(shù)的調(diào)節(jié)使河流自身所具有的彎曲形態(tài)與地形的主要特征得以同時保留，試驗效果良好，實現(xiàn)了三維空間河網(wǎng)要素與DEM數(shù)據(jù)在同一簡化因子作用下的綜合，提升了地圖綜合的質(zhì)量。

關(guān)鍵詞：彎曲調(diào)節(jié)指數(shù)；三維 Douglas-Peucker算法；地圖綜合

Douglas-Peucker(DP)算法是目前最具代表意義的二維線狀要素化簡算法[1-2]。目前，部分學(xué)者將其從二維推廣至三維，提出了三維Douglas-Peucker算法(3D_DP算法)，并應(yīng)用于DEM的綜合[3-5]；文獻(xiàn)[6]對算法進(jìn)行了改進(jìn)。隨后，3D_DP算法在許多領(lǐng)域得到了廣泛應(yīng)用，如黃土高原的地貌綜合[7]、等高線間接綜合[8-9]、DEM地形特征的提取[10]、規(guī)則格網(wǎng)地形的LOD建模[11]及其海底多波束測深數(shù)據(jù)的抽稀[12]等。這些研究證明該算法能夠保持制圖區(qū)域的主要地貌特征，刪除次要地貌，對隱含在DEM中的地貌結(jié)構(gòu)線并沒有破壞作用[3]。

河流與地貌在地理成因上存在著天然的耦合關(guān)系[13]，以往針對河網(wǎng)與DEM數(shù)據(jù)的綜合研究中，兩要素都是分開獨立進(jìn)行的，即河網(wǎng)作為矢量要素是依據(jù)其空間幾何特征，而DEM則是根據(jù)其地形粗糙度，綜合標(biāo)準(zhǔn)的不一致可能會在分析操作中出現(xiàn)幾何或拓?fù)涿躘14]。本文利用3D_DP算法進(jìn)行河網(wǎng)線要素和DEM的綜合方法研究，使兩要素在同一簡化因子的作用下進(jìn)行綜合操作。在使用3D_DP算法進(jìn)行兩要素綜合的過程中，河流在水平方向上自身所具有的彎曲形態(tài)將不能同時得以保留，尤其在局部平坦地區(qū)表現(xiàn)會更加突出，可能出現(xiàn)在某一閾值下，具有不同大小彎曲的河流要素點全部被綜合的情況。

為此，本文引入了“彎曲調(diào)節(jié)指數(shù)”來改進(jìn)3D_DP算法，提出一種三維空間河網(wǎng)要素和DEM綜合的方法。在該方法中，將河網(wǎng)線要素提取成三維離散數(shù)據(jù)點集(增加高程屬性)與DEM三維離散數(shù)據(jù)點集合并，然后基于改進(jìn)的3D_DP算法進(jìn)行綜合操作，并利用河北保定及周邊地區(qū)的河網(wǎng)數(shù)據(jù)和DEM，對所提算法及應(yīng)用的正確性和有效性進(jìn)行了試驗驗證和分析。

13D_DP算法原理

3D_DP算法實現(xiàn)步驟[3](如圖1)為：

(1) 確定原點和首基面：遍歷某指定三維離散點集中的所有離散點并兩兩求矢量積，確定矢量積絕對值最大的一對所確定的平面為首基面，并指定此最大矢量積的3個點分別為原點、初始錨點和初始漂浮點(分別對應(yīng)圖1中的O點、A點和B點)。

(2) 點集有序化：按照空間臨近原則對無序的三維離散點進(jìn)行排序處理。即將初始錨點A作為點列首點，然后依次尋找三維距離最近的下一個新點，最后將初始漂浮點B作為點列的末點，原點O不參與排序。

(3) 特征點的選?。河嬎闩判虻拿總€離散點到首基面的點面距，若最大的點面距小于規(guī)定的閾值，則刪除所有的點；若最大的點面距大于規(guī)定的閾值，則將有序點集從該點分為兩段，重復(fù)上述過程[3]。

圖1　3D_DP算法中的首基面與點面距Fig.1　Initial base plane and point-plane distance of the 3D_DP algorithm

2利用彎曲調(diào)節(jié)指數(shù)對3D_DP算法的改進(jìn)

本節(jié)引入“彎曲調(diào)節(jié)指數(shù)”，使其能夠區(qū)別反映出河流自身形態(tài)中的彎曲的大小，并用它來調(diào)節(jié)3D_DP算法中的點面距，從而得到偽點面距，然后使用偽點面距與預(yù)先設(shè)置的閾值進(jìn)行比較來決定河流要素點的取舍，最終實現(xiàn)河流自身整體形態(tài)與地形主要特征的同時保留。

2.1河流彎曲大小的判定和比較

彎曲是線狀河流目標(biāo)形態(tài)綜合的基本操作單元，一條河流包含有很多大小不一的彎曲。在計算機環(huán)境下，需要對彎曲做出數(shù)學(xué)化的定義，從而能夠?qū)澢拇笮∵M(jìn)行合理的劃分和識別[15]。

彎曲判定的方法有多種，本文選用了基于拐點的彎曲定義[16]。彎曲由很多線段組成，而每相鄰的兩線段之間都有一個轉(zhuǎn)折角，或正或負(fù)，本文規(guī)定逆時針為“+”，順時針為“-”，當(dāng)沿著線段前進(jìn)，轉(zhuǎn)折的方向發(fā)生改變時，轉(zhuǎn)角的正負(fù)性會發(fā)生改變，轉(zhuǎn)角發(fā)生改變的這個點稱為曲線的拐點。在拐點處，曲線轉(zhuǎn)角發(fā)生改變其實就是彎曲發(fā)生改變的地方。如圖2所示，可以判定P2點、P3點為曲線上的拐點，彎曲在拐點發(fā)生了轉(zhuǎn)向，而P1P2段為逆時針彎曲，P2P3段則為順時針彎曲。基于拐點的彎曲定義具有如下兩個特性：①正角彎曲和負(fù)角彎曲相間出現(xiàn)；②彎曲是相鄰的，涵蓋了曲線的所有點。

這里借助彎曲的寬度w、彎曲的長度l、彎曲的面積s、面積系數(shù)e和彎曲度f來描述彎曲所具有的特征：①彎曲的寬度w，即彎曲的口徑，如圖2中的P2P3直線段；②彎曲的長度l，P2P3之間弧段的總長度；③彎曲的面積s，彎曲的長度l與寬度w所圍的面積；④面積系數(shù)e，e=s/s0，s0為與彎曲周長等長的圓面積，e表示彎曲的凹凸程度；⑤彎曲度f，彎曲的長度l與寬度w的比值稱為彎曲度，即f=l/w。彎曲度的最小值是1，值越大，說明彎曲程度越大。

圖2　基于拐點的彎曲Fig.2　The bending based on the turning point

2.2彎曲調(diào)節(jié)指數(shù)

為了合理的表示并比較出曲線上每個彎曲的大小，充分體現(xiàn)彎曲長度和彎曲面積的大小對曲線彎曲的影響程度，并讓其具有唯一值，本文使用面積系數(shù)e、彎曲度f、彎曲長度比及彎曲面積比等幾個要素組合構(gòu)成彎曲調(diào)節(jié)指數(shù)(bending adjustment index)B，即

(i=1,2，…，n,為彎曲的序號)

(1)

假定dk為3D_DP算法中點Pk到基面的點面距，C為彎曲調(diào)節(jié)常數(shù)，則具有彎曲的河流點的偽點面距為

Dk=dk×(C×Bi+1)

(2)

本文在綜合時以基本的彎曲作為保留或刪除的單元，因此同一彎曲上的所有點使用相同的“彎曲調(diào)節(jié)指數(shù)Bi”，這樣可以在綜合后從視覺上保持河流彎曲的連續(xù)性，并保留彎曲本身的特性不發(fā)生變化。

通過式(2)可以看出，若想讓彎曲調(diào)節(jié)指數(shù)不起作用，可以令彎曲調(diào)節(jié)常數(shù)C取值為0，這時偽點面距就等于實際的點面距；C的取值也不能過大，如果太大，會使河流點的數(shù)量保留過多，影響數(shù)據(jù)的簡化效果。因此，對于C的取值，需要根據(jù)具體的地貌形態(tài)并通過試驗方可確定。

2.3地形地貌的劃分

采用彎曲調(diào)節(jié)指數(shù)來調(diào)節(jié)點面距，是為了避免尤其是平坦地區(qū)的河流在與DEM綜合時被過度綜合。彎曲調(diào)節(jié)指數(shù)調(diào)節(jié)程度的大小與地形地貌的類別有很大關(guān)系，通常來說，地勢平坦的地區(qū)，調(diào)節(jié)程度大，而地勢陡峭的地區(qū)，調(diào)節(jié)程度小，因此，需要進(jìn)行地形地貌類型的劃分，以區(qū)分彎曲調(diào)節(jié)指數(shù)在不同地形類別上對河流段的不同調(diào)節(jié)作用。

我國地域廣闊，各個地區(qū)的地形地貌的類別劃分有很大不同，本文將試驗區(qū)選在了河北省保定地區(qū)及周邊，結(jié)合國家習(xí)慣上對平原、山地的劃分標(biāo)準(zhǔn)[17]，對本文試驗區(qū)制定了地形類別的劃分標(biāo)準(zhǔn)，具體見表1。針對各類地形狀況通過試驗確定C值的大小。

表1地形地貌類別的劃分標(biāo)準(zhǔn)及對應(yīng)C值的命名

Tab.1StandardsforthedivisionofgeomorphologyandthecorrespondingCvalue

地形類別劃分平原丘陵低山區(qū)高山區(qū)海拔高度/m0～500500～10001000～3000彎曲調(diào)整常數(shù)命名C1C2C3

3河網(wǎng)要素和DEM數(shù)據(jù)綜合算法

關(guān)于河流的綜合，一般情況是先執(zhí)行選取操作，然后再對保留的河流進(jìn)行化簡處理。本文也遵循了地圖綜合的這一規(guī)則，并選擇了最具形狀代表意義的樹狀河流進(jìn)行試驗研究。

3.1層次化的河網(wǎng)綜合選取

河流的選取是一個復(fù)雜的問題，目前也有很多經(jīng)典的河流選取方法。文獻(xiàn)[18]以河流長度為主要標(biāo)準(zhǔn)，輔以河網(wǎng)密度和河流所處層次等標(biāo)準(zhǔn)進(jìn)行組合，從而進(jìn)行河流的綜合指數(shù)的計算。本文引用了這一方法，即

綜合指數(shù)=長度×等級α×(最大層次-層次+1)β

(3)

式中，河流密度以等級表示；層次值取決于河系樹結(jié)構(gòu)，主流所在層次為1，由主流到支流再到次級支流其層次值逐漸增大；α、β為經(jīng)驗參數(shù)。綜合指數(shù)能夠保證長度大、所處層次高、支流密度大的河流被優(yōu)先選取。本文選取了文獻(xiàn)[18]中試驗確定的數(shù)值α=0.3、β=0.7，結(jié)果較為滿意。按照式(3)計算出每條河流的綜合指數(shù)，并按綜合指數(shù)由大到小的順序?qū)恿鬟M(jìn)行排序，然后根據(jù)需要進(jìn)行河流的合理選取，河網(wǎng)的層次化分級部分結(jié)果如圖3所示。

圖3　河網(wǎng)層次化選取后各級效果圖Fig.3　The effect of levels after river network selection

3.2河網(wǎng)要素和DEM的綜合

本文所采用的三維空間河網(wǎng)線要素與DEM綜合算法的基本思想是依據(jù)河網(wǎng)對地形的高度依附性，將河網(wǎng)數(shù)據(jù)和DEM數(shù)據(jù)均提取為三維離散點數(shù)據(jù)集，合并成同一數(shù)據(jù)集，然后使用改進(jìn)后的3D_DP算法進(jìn)行綜合操作。具體綜合過程如圖4所示。

河網(wǎng)數(shù)據(jù)通常均為二維矢量數(shù)據(jù)，首先將河網(wǎng)數(shù)據(jù)按照3.1節(jié)所述方法進(jìn)行層次化分級后，提取為離散點集，然后與DEM數(shù)據(jù)疊加增加其高程屬性，成為三維離散點集。

使用改進(jìn)后的3D_DP算法對合并數(shù)據(jù)集進(jìn)行綜合時，其對DEM點集的綜合能夠直接根據(jù)3D_DP算法的簡化閾值的大小自動保留主要地貌特征，刪除次要地貌。對河網(wǎng)點集的綜合操作，則有如下說明：

(1) 需要加入相應(yīng)的河流綜合規(guī)則，即河網(wǎng)完成層次化選取后，已經(jīng)得以保留的河流不應(yīng)該在綜合時再由于閾值的偏大等原因而被全部簡化掉，因此制定以下規(guī)則：①在某一層次進(jìn)行綜合操作時，所有河系的主流、支流的起點和終點必須保留；②所有主流和支流的交點也必須保留。

(2) 要獲得令人較滿意的河網(wǎng)綜合結(jié)果，需要多次通過試驗效果的對比來確定3D_DP算法的簡化閾值和彎曲調(diào)節(jié)常數(shù)C的取值。

圖4　河網(wǎng)要素與DEM綜合方法流程圖Fig.4　Flowchart of generalization between rivers network and DEM

合并數(shù)據(jù)集在綜合操作完成以后，按照點集的屬性重新分離為“綜合后河網(wǎng)點集”和“綜合后DEM點集”，然后進(jìn)行河流和DEM的重建。DEM的重建采用Delaunay構(gòu)三角網(wǎng)的方法進(jìn)行，實際上重構(gòu)三角網(wǎng)的過程由于在空間拓?fù)潢P(guān)系上與河流并沒有直接的關(guān)系，若重建時不加考慮則不可避免的會出現(xiàn)“河流爬坡”的空間沖突現(xiàn)象，見圖5(a)。因為河流一般流經(jīng)谷底，可以認(rèn)為是山地隱性的山谷線的一部分，故本文利用綜合后的河流線段作為重構(gòu)三角網(wǎng)的約束邊，采用約束Delaunay構(gòu)三角網(wǎng)的方法[19-20]，使得“河流爬坡”的空間沖突現(xiàn)象得以消除，具體消除情況見圖5(b)。

圖5　采用約束Delaunay構(gòu)三角網(wǎng)法消除空間沖突現(xiàn)象Fig.5　The spatial conflict phenomenon is eliminated by constraint Delaunay method

4試驗及分析

4.1數(shù)據(jù)準(zhǔn)備與預(yù)處理

本研究采用C#編程實現(xiàn)了改進(jìn)的3D_DP算法、河系樹的自動構(gòu)建、河流綜合指數(shù)的計算和河網(wǎng)與DEM數(shù)據(jù)的綜合算法等，并使用OpenGL渲染顯示綜合前后的河網(wǎng)與地形效果圖。試驗區(qū)域和數(shù)據(jù)選擇了河北省保定地區(qū)及周邊約50 000 km2區(qū)域的DEM數(shù)據(jù)和同一地區(qū)的河流矢量數(shù)據(jù)。該區(qū)域地勢由西北向東南傾斜。地貌分山區(qū)和平原兩大類。西北部分以山區(qū)為主，東南部分以平原為主，高程分布為8～2893 m；本文對試驗區(qū)內(nèi)的微小河流段進(jìn)行了刪除處理，保留了5條完整的樹狀河系，共有各級河流131條，如圖6所示。

按照試驗要求對數(shù)據(jù)進(jìn)行了預(yù)處理，可以通過開方根公式確定綜合時某一層次河流被保留的條數(shù)。將試驗區(qū)按照地形地貌分為3類：平原、低山區(qū)和高山區(qū)，高程劃分標(biāo)準(zhǔn)見表1。

4.2試驗研究與分析

針對本試驗區(qū)，根據(jù)數(shù)據(jù)簡化百分比和試驗預(yù)期要求，本文采用3D_DP算法的3個簡化閾值200 m、500 m和800 m以及3種地貌分區(qū)的彎曲調(diào)節(jié)常數(shù)C1、C2、C3分別對應(yīng)不同的取值進(jìn)行了多次試驗和結(jié)果對比，并選取了彎曲調(diào)節(jié)指數(shù)在綜合過程中的調(diào)節(jié)作用發(fā)揮較好的3組進(jìn)行了統(tǒng)計，具體數(shù)據(jù)見表2。限于文章篇幅，本節(jié)選用閾值為800 m，彎曲調(diào)節(jié)常數(shù)取值C1=2、C2=C3=0.75調(diào)節(jié)的試驗效果圖進(jìn)行展示對比(圖7)。圖中線型表示試驗區(qū)部分河流，紅色為河流原始形狀，藍(lán)色為未使用彎曲指數(shù)調(diào)節(jié)的綜合結(jié)果，黑色為使用彎曲調(diào)節(jié)指數(shù)后的綜合結(jié)果。

圖6　試驗區(qū)DEM與河網(wǎng)原圖Fig.6　The original image of rivers and DEM in experimental area

圖7　閾值為800 m時河網(wǎng)和DEM綜合試驗結(jié)果對比圖Fig.7　Contrast among the simultaneous simplified results of rivers and DEM when the threshold for 800 m

通過以上對試驗結(jié)果和統(tǒng)計數(shù)據(jù)的對比，可以得出以下結(jié)論:

(1) 本文提出的基于改進(jìn)的3D_DP算法的河網(wǎng)要素與DEM綜合新方法是可行并有效的。該方法中，通過“彎曲調(diào)節(jié)指數(shù)”的調(diào)節(jié)，河網(wǎng)自身的彎曲形態(tài)與DEM的地形特征得以同時保留，實現(xiàn)了三維空間河網(wǎng)要素與DEM在同一簡化因子作用下的綜合，效果良好。本方法提高了地圖綜合的質(zhì)量，拓寬了3D_DP算法應(yīng)用范圍，為進(jìn)一步擴充矢量數(shù)據(jù)要素類型與DEM進(jìn)行綜合研究提供了新方法和新思路。

(2) 通過彎曲調(diào)節(jié)指數(shù)的調(diào)節(jié)，河流數(shù)據(jù)點的保留點數(shù)會增加，通過犧牲一點簡化率來提高地圖綜合整體的質(zhì)量是可行的。同時由于保留的河流數(shù)據(jù)點參與3D_DP算法過程中的基面選擇，因此DEM數(shù)據(jù)的保留點數(shù)也會有微小的變化，但對整體的綜合結(jié)果不會造成影響。

(3) 彎曲調(diào)節(jié)常數(shù)C的取值與多方面因素有關(guān)，如3D_DP算法所取簡化閾值的大小、試驗區(qū)的地形地貌類別以及地勢的相對起伏程度等。因此，對于具體地區(qū)應(yīng)用時，需要通過試驗確定其取值。隨著3D_DP算法的簡化閾值的增大，即數(shù)據(jù)保留率的降低，彎曲調(diào)節(jié)指數(shù)的調(diào)節(jié)作用就越趨明顯，彎曲調(diào)節(jié)常數(shù)C的取值也趨于增大；通過統(tǒng)計河流點數(shù)在調(diào)節(jié)前后的保留率差值并根據(jù)制圖綜合實際需要，可以適度調(diào)整彎曲調(diào)節(jié)常數(shù)C的取值。

表2　綜合算法試驗數(shù)據(jù)統(tǒng)計表

5結(jié)論

本文引入“彎曲調(diào)節(jié)指數(shù)”改進(jìn)了傳統(tǒng)3D_DP算法，提出了一種三維空間河網(wǎng)要素和DEM綜合的新方法，并通過相關(guān)試驗分析，得出如下結(jié)論：①通過“彎曲調(diào)節(jié)指數(shù)”的調(diào)節(jié)，使河網(wǎng)自身的彎曲形態(tài)與DEM的地形特征得以同時保留，初步實現(xiàn)了兩種要素在同一簡化因子作用下的同步綜合操作，提高了地圖綜合的質(zhì)量；②應(yīng)用彎曲調(diào)節(jié)指數(shù)，使河流和DEM數(shù)據(jù)點的保留點數(shù)會有少許增加，但對整體的綜合結(jié)果不會造成影響；③河網(wǎng)要素和DEM在同一簡化因子下的漸進(jìn)離散點選取過程，有利于多要素的多層次動態(tài)式綜合，可為他們建立LOD(細(xì)節(jié)層次)模型提供不同精度要求的綜合數(shù)據(jù)。

目前在試驗結(jié)果中，當(dāng)正角彎曲和負(fù)角彎曲連續(xù)交替出現(xiàn)形成“復(fù)合彎曲”時會出現(xiàn)個別過度綜合現(xiàn)象，針對“復(fù)合彎曲”的嚴(yán)密數(shù)學(xué)定義、表達(dá)及如何進(jìn)一步完善彎曲調(diào)節(jié)指數(shù)，將是下一步研究工作中首先要解決的問題。另外，對于綜合試驗結(jié)果好壞的判定只能通過視覺觀察確定，存在一定的主觀性，需要發(fā)展嚴(yán)密的數(shù)學(xué)方法和模型對其進(jìn)行定量的描述和評價，且對空間多種地理要素與DEM之間的綜合算法的研究還有待于進(jìn)一步完善與發(fā)展，如將更為廣泛的其他線狀地物如道路、電力線、行政邊界線等納入到綜合方法的范疇之中，將有助于此算法的進(jìn)一步發(fā)展和多要素數(shù)據(jù)綜合理論的進(jìn)步，這些問題將在以后的工作中進(jìn)行更深入的研究和探討。

參考文獻(xiàn)：

[1]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]. The Canadian Cartographer, 1973, 10(2): 112-122.

[2]楊得志, 王杰臣, 閭國年. 矢量數(shù)據(jù)壓縮的Douglas-Peucker算法的實現(xiàn)與改進(jìn)[J]. 測繪通報, 2002(7): 18-22.

YANG Dezhi, WANG Jiechen, Lü Guonian. Study of Realization Method and Improvement of Douglas-Peucher Algorithm of Vector Data Compressing[J]. Bulletin of Surveying and Mapping, 2002(7): 18-22.

[3]費立凡,何津,馬晨燕,等. 3維Douglas-Peucker算法及其在DEM自動綜合中的應(yīng)用研究[J]. 測繪學(xué)報, 2006, 35(3): 278-284.

FEI Lifan, HE Jin, MA Chenyan, et al. Three Dimensional Douglas-Peucker Algorithm and the Study of Its Application to Automated Generalization of DEM[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(3): 278-284.

[4]LI Yang, HU Peng, FAN Qingsong, et al. The Generalization Based on 3 Dimensional Douglas-Peucker Algorithm in New DEM Model[C]∥Proceedings of International Workshop on Education Technology and Training and International Workshop on Geoscience and Remote Sensing. Shanghai: IEEE, 2008: 283-286.

[5]FEI Lifan, HE Jin. A Three-dimensional Douglas-Peucker Algorithm and Its Application to Automated Generalization of DEMs[J]. International Journal of Geographical Information Science, 2009, 23(6): 703-718.

[6]何津, 費立凡. 再論三維Douglas-Peucker算法及其在DEM綜合中的應(yīng)用[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2008, 33(2): 160-163.

HE Jin, FEI Lifan. Further Study on Three Dimensional Douglas-Peucker Algorithm and Its Application to Generalization of DEM[J]. Geomatics and Information Science of Wuhan University, 2008, 33(2): 160-163.

[7]劉敏. 基于三維道格拉斯改進(jìn)算法的地貌自動綜合研究——以在黃土高原的實驗為例[D]. 西安: 西北大學(xué), 2007.

LIU Min. Relief Automated Generalization Based on the Improved Three Dimensional Douglas-Peucker Algorithm: A Case Study in the Loess Plateau[D]. Xi’an: Northwest University, 2007.

[8]黃麗娜,費立凡. 采用3D D-P算法的等高線三維綜合實驗研究[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2010, 35(1): 55-58.

HUANG Lina, FEI Lifan. Experimental Investigation on the Three Dimension Generalization of Contour Lines Using 3D D-P Algorithm[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1): 55-58.

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

HE Jin, FEI Lifan, HUANG Lina, 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.

[10]朱雪堅, 葉遠(yuǎn)智, 湯國安. 運用三維Douglas-Peucker算法提取DEM地形特征[J]. 測繪通報, 2014(3): 118-121. DOI: 10.13474/j.cnki.11-2246.2014.0105.

ZHU Xuejian, YE Yuanzhi, TANG Guoan. Three Dimensional Douglas-Peucker Algorithm Based Extraction of Topographical Features from DEM[J]. Bulletin of Surveying and Mapping, 2014(3): 118-121. DOI: 10.13474/j.cnki.11-2246.2014.0105.

[11]張俊峰, 費立凡, 黃麗娜, 等. 利用3D_DP和Quad_TIN的地形實時動態(tài)顯示算法研究[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2011, 36(3): 346-350.

ZHANG Junfeng, FEI Lifan, HUANG Lina, et al. Real-Time Dynamic Rendering Algorithm of Terrain Using 3D_DP Method and Quad_TIN Model[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3): 346-350.

[12]竇世卿, 劉成軍, 林亞文, 等. 基于改進(jìn)的三維Douglas-Peucker算法的多波束測深數(shù)據(jù)抽稀方法[J]. 科技導(dǎo)報, 2014, 32(19): 21-25.

DOU Shiqing,LIU Chengjun,LIN Yawen,et al. A Method of Multi-beam Echo Sounding System Data Thinning Based on Improved 3D Douglas-Peucker Algorithm[J]. Science & Technology Review, 2014, 32(19): 21-25.

[13]舒方國. 基于多Agent的等高線與河流協(xié)同綜合方法研究[D]. 南京: 南京師范大學(xué), 2012.

SHU Fangguo. Collaborative Map Generalization Method of Contours and Rivers Based on Multi-agent[D]. Nanjing: Nanjing Normal University, 2012.

[14]YANG Ling, ZHANG Liqiang, KANG Zhizhong, et al. An Efficient Rendering Method for Large Vector Data on Large Terrain Models[J]. Science in China Information Sciences, 2010, 53(6): 1122-1129.

[15]李雯靜, 邱佳, 林志勇, 等. 曲線彎曲識別與等高線簇結(jié)構(gòu)化方法[J]. 測繪學(xué)報, 2013, 42(2): 295-303.

LI Wenjing,QIU Jia,LIN Zhiyong,et al. Approach of Curve Bends Recognition and Contour Cluster Structuralization[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 295-303.

[16]沈志峰. 電子海圖島嶼多邊形簡化與合并算法研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2009.

SHEN Zhifeng.Research on Simplification and Aggregation Algorithm of Island Polygon in Electronic Chart[D]. Harbin: Harbin Engineering University, 2009.

[17]中國科學(xué)院地理研究所. 中國1∶1 000 000地貌圖制圖規(guī)范[S]. 北京: 科學(xué)出版社, 1987.

Institute of Geography Research of CAS. 1∶1 000 000 Geomorphologic Map Drawing Specification of China[S]. Beijing: Science Press, 1987.

[18]張青年. 顧及密度差異的河系簡化[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.

[19]楊敏, 艾廷華, 劉鵬程, 等. 等高線與水網(wǎng)數(shù)據(jù)集成中的匹配及一致性改正[J]. 測繪學(xué)報, 2012, 41(1): 152-158.

YANG Min, AI Tinghua, LIU Pengcheng, et al. The Matching and Consistency Correcting in the Integration of Contour and River Network[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 152-158.

[20]龍毅, 曹陽, 沈婕, 等. 基于約束D-TIN的等高線簇與河網(wǎng)協(xié)同綜合方法[J]. 測繪學(xué)報, 2011, 40(3): 379-385.

LONG Yi, CAO Yang, SHEN Jie, et al. Cooperative Generalization Method of Contour Cluster and River Network Based on Constrained D-TIN[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(3): 379-385.

(責(zé)任編輯：張艷玲)

修回日期： 2015-12-16

First author： DOU Shiqing(1977—)，female，PhD，associate professor，majors in the generalization and modeling for 3D GIS.

E-mail： 37929972@qq.com

E-mail： zxs@cumtb.edu.cn

The Three Dimensional Douglas-Peucker Algorithm for Generalization between River Network Line Element and DEM

DOU Shiqing1, 2,ZHAO Xuesheng1,LIU Chengjun2,LIN Yawen3,ZHAO Yanqin4

1. College of Geoscience and Surveying Engineering, China University of Mining &Technology (Beijing), Beijing 100083, China； 2. College of Mining Engineering, Heilongjiang University of Science and Technology, Harbin 150022, China； 3. Beijing Forestry Information Technology CO., LTD, Beijing 100036, China； 4. College of Computer and Information Engineering, Heilongjiang University of Science and Technology, Harbin 150022, China

Abstract：At present, the three dimensional Douglas-Peucker (3D_DP) algorithm is mainly used on generalization of a single type of DEM. This paper introduces the “bending adjustment index” to improve the 3D_DP algorithm, and puts forward a new method for generalizing river network and DEM in three-dimensional space. In this method, river network line vector data are extracted into 3D discrete point data sets which are added elevation attributes, and then they are merged with the 3D discrete point data sets of DEM. The generalization operations are made by the improved 3D_DP algorithm after the hierarchical selection of river networks. Through the contrast and analysis of the experimental results, the well experiment results have been achieved. Under the role of bending adjustment index, the overall distribution form of the rivers and the main terrain features can be reserved reasonably on the generalization. The river network and DEM data were generalized under the same simplified factor in this method. It improves the quality of the cartography generalization.

Key words：bending adjustment Index； 3D Douglas-Peucker algorithm； cartography generalization

Corresponding author：ZHAO Xuesheng

通信作者：趙學(xué)勝

第一作者簡介：竇世卿(1977—)，女，博士，副教授，研究方向為三維GIS綜合與建模。

收稿日期：2014-11-18

基金項目：國家自然科學(xué)基金(41171306)；黑龍江省自然科學(xué)基金(F201436)

中圖分類號：P208

文獻(xiàn)標(biāo)識碼：A

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

Foundation support： The National Natural Science Foundation of China (No.41171306 )；Natural Science Foundation of Heilongjiang Province (No.F201436)

引文格式：竇世卿，趙學(xué)勝，劉成軍,等.河網(wǎng)線要素與DEM綜合的三維Douglas-Peucker算法[J].測繪學(xué)報，2016,45(4)：450-457. DOI:10.11947/j.AGCS.2016.20140584.

DOU Shiqing,ZHAO Xuesheng,LIU Chengjun,et al.The Three Dimensional Douglas-Peucker Algorithm for Generalization between River Network Line Element and DEM[J]. Acta Geodaetica et Cartographica Sinica,2016,45(4):450-457. DOI:10.11947/j.AGCS.2016.20140584.