基于線性地物要素的綜合化簡算法設(shè)計與實現(xiàn)

摘? 要：我國河流水系分布眾多，為滿足生產(chǎn)需要，在眾多水系中提取主要的河流至關(guān)重要。文章采用開方根法和Douglas-peucker法，利用C#語言實現(xiàn)化簡程序，同時與GIS軟件化簡結(jié)果進行對比分析。研究表明，利用算法程序化簡的河流條數(shù)與GIS的相同為52條，但是河流節(jié)點數(shù)為965個，比GIS的化簡結(jié)果少了40個節(jié)點，且化簡水系圖更加平滑和美觀，自動化程度更高，可以用于從大量的河流中提取主要的河流。

關(guān)鍵詞：線狀地物要素;Douglas-peucker法;開方根法;自動綜合

中圖分類號：TP311? 文獻標(biāo)識碼：A 文章編號：2096-4706（2021）17-0017-05

Abstract： There are many river systems in China， in order to meet the needs of production， it is very important to extract the main rivers from many river systems. In this paper， the square root method and Douglas-peucker method are used to realize the simplification program in C# language， meanwhile， the simplification results of it are compared with those of GIS software. The research shows that the number of rivers simplified by the algorithm program is the same as that of GIS， which is 52， but the number of river nodes is 965， which is 40 nodes less than the simplification result of GIS， and the simplified river system map is smoother and more beautiful， with a higher degree of automation. It can be used to extract the main rivers from a large number of rivers.

Keywords： linear ground object element; Douglas-peucker method; square root method; automatic synthesis

0? 引? 言

計算機技術(shù)的快速發(fā)展，使得地圖制圖綜合技術(shù)由傳統(tǒng)的方法向數(shù)字化和智能化的方向轉(zhuǎn)變。測繪的成果主要表現(xiàn)為地表形態(tài)的地圖，因此對地球形態(tài)的認(rèn)識以及對地圖制作方法的改進是測繪學(xué)發(fā)展的重要標(biāo)志。當(dāng)前人類社會已經(jīng)進入信息化時代，制圖技術(shù)有了跨越式的發(fā)展。由傳統(tǒng)的地圖生產(chǎn)方式向數(shù)字化、自動化和智能化的方向轉(zhuǎn)變，在這個過程中，地圖制圖綜合作為地理信息系統(tǒng)和地圖生產(chǎn)過程中不可回避的問題，變得尤為重要。從整個地圖科學(xué)方面考慮，地圖綜合是人類認(rèn)識客觀存在的具體表現(xiàn)，是人類進行空間信息處理的核心概念。

在數(shù)字信息系統(tǒng)中，線性特征通常由采樣得到的離散點來描述。得到的采樣點個數(shù)越密集，對原始特征的描述能力就越強，所呈現(xiàn)的原始特征就越真實。隨著數(shù)據(jù)量的不斷增加，對數(shù)據(jù)的管理和分析變得愈發(fā)困難。因此，有必要對線性特征元素的數(shù)據(jù)進行壓縮。這個過程也稱為線性特征簡化，即用盡可能少的采樣點來描述原始特征，保證原始特征的真實形態(tài)特征能夠在允許的誤差范圍內(nèi)再現(xiàn)。從信息理論的角度來看，線性特征元素集成技術(shù)本質(zhì)上是一個問題的信息壓縮，從組合曲線點集中提取序列的一個子集，將這個子集作為新的信息來源，在規(guī)定的范圍內(nèi)，精確子集可以真實反映原始收集盡可能多的內(nèi)容，但盡量減少數(shù)量。本文以長江水系分布圖為研究對象，利用GIS對長江水系圖配準(zhǔn)、矢量化。提出了基于（C#語言）Douglas-peucker算法和開方根規(guī)律法編寫線性要素化簡程序，實現(xiàn)線性地物要素的自動綜合化簡，并對化簡結(jié)果進行對比分析。

1? 道格拉斯算法與開方根算法

1.1? Douglas-peucker算法

道格拉斯算法是一種將曲線近似為一系列的點并減少點數(shù)量的算法。它具有平移和旋轉(zhuǎn)不變性的優(yōu)點，在給定曲線和閾值后采樣結(jié)果是恒定的。公式為：

道格拉斯算法的優(yōu)缺點：

優(yōu)點是經(jīng)過平移和旋轉(zhuǎn)后不改變原有的特性，在給出具體的閾值和數(shù)據(jù)后，抽樣結(jié)果是一個定值。缺點是當(dāng)曲線擁有非常重要的地理意義且情況復(fù)雜時，Douglas-peucker算法的缺陷便顯露出來，大致情況為，在某一化簡尺度下經(jīng)過化簡的曲線會出現(xiàn)自相交或者相鄰的曲線之間出現(xiàn)相交的情況。因此，空間數(shù)據(jù)拓撲關(guān)系的正確與否至關(guān)重要，一旦出現(xiàn)錯誤就會導(dǎo)致無法正確地在地圖上顯示地理信息，更重要的問題是會導(dǎo)致評估和決策錯誤。為了保證化簡結(jié)果的準(zhǔn)確性，必須要做到前后拓撲關(guān)系正確以及解決化簡過程中出現(xiàn)相交與自相交的問題，并且在化簡之后也可能會出現(xiàn)某些重要特征點的缺失。

1.2? 開方根算法

開方根規(guī)律法是提出一種地圖概括的數(shù)量處置方法，用于解決資料地圖與新編地圖由于比例尺的變換而產(chǎn)生的地物數(shù)量簡化問題。公式為：

Nf=NA? ? ? ? ? ? ? ? ? ? ? ? ? （6）

其中，Af是新編地圖的比列尺分母，MA是原始地圖的比列尺分母，NA是原始地圖的地物數(shù)，Nf是新編地圖的地物數(shù)。

開方根算法的優(yōu)缺點：

開方根規(guī)律法公式直觀地顯示了制圖綜合時從重要到一般的選取指標(biāo)，是一個有序的選取等級系統(tǒng)。開方根公式是線性方程，在地圖比例尺固定不變的條件下，地物要素的選取比例保持一致。開方根公式的缺點是沒有考慮到地理差異，特別是未將制圖地物分布的密度變化考慮在內(nèi)。

1.3? 數(shù)據(jù)處理

將一幅滿足條件的長江水系簡圖通過ArcGIS10.2軟件進行影像配準(zhǔn)，已知長江水系簡圖中七個點的地理坐標(biāo)值，但是長江水系簡圖中x軸和y軸的比例是不協(xié)調(diào)的，這時候我們可以考慮讓x軸乘以一個常系數(shù)（這里是10 000），然后進行坐標(biāo)匹配。完成坐標(biāo)匹配之后，點擊添加控制點，此時即可完成長江水系簡圖校正。利用GIS的編輯工具將校正后的水系圖進行矢量化，矢量化完成以后，需要將河流的地理坐標(biāo)系向直角坐標(biāo)系轉(zhuǎn)化，然后坐標(biāo)系需要選擇投影坐標(biāo)系中的WGS 1984 world Mercator坐標(biāo)系。完成坐標(biāo)系轉(zhuǎn)換后，需要將要素折點轉(zhuǎn)點，如圖1所示。

利用GIS工具中的數(shù)據(jù)管理工具添加XY坐標(biāo)，將屬性數(shù)據(jù)導(dǎo)出為TXT文本格式，將導(dǎo)出的數(shù)據(jù)整理為Excel表格，并將一些不需要的數(shù)據(jù)刪除后得到所有節(jié)點的點名和坐標(biāo)數(shù)據(jù)。再將河流經(jīng)過坐標(biāo)投影后的線圖層中的屬性數(shù)據(jù)表導(dǎo)出、整理為Excel表格得到所有的線名，河流長度數(shù)據(jù)。分別如表1（河流局部數(shù)據(jù)）和表2（河流局部數(shù)據(jù)）所示。

2? 界面設(shè)計與核心代碼

2.1? 界面設(shè)計功能實現(xiàn)

利用Visual studio 2013編程軟件，采用面向?qū)ο缶幊碳夹g(shù)來完成線性要素化簡程序界面設(shè)計。根據(jù)程序功能的需要，添加相應(yīng)的組件（如菜單欄控件、工具欄控件、桌面控件（tabControl1）、openFileDialog1控件、saveFileDialog1控件等組件）來實現(xiàn)打開、保存、開方根計算、道格拉斯計算、數(shù)據(jù)顯示、圖形可視化等功能。程序功能界面如圖2所示。

2.2? 核心代碼

化簡模塊主要分為兩項，首先是通過開方根規(guī)律法對河流數(shù)據(jù)進行數(shù)量化簡，再用道格拉斯算法對已經(jīng)進行河流數(shù)量化簡的數(shù)據(jù)進行節(jié)點化簡和壓縮。下面給出了開方根算法和道格拉斯算法的核心代碼：

（1）開方根算法核心代碼為：

double L，C，K;//定義三個雙精度變量。

int A，B;

C=math.sqrt（A/B）;//利用開方根函數(shù)計算開方根。

K=C*L;

（2）首先要聲明線段起點和線段終點，新建一個待檢查的節(jié)點堆棧和壓縮結(jié)果的堆棧;定義一個讀取閾值，再設(shè)置一個初始起點和初始終點。將初始起點壓入結(jié)果堆棧，初始終點壓入待檢查的節(jié)點堆棧中。用while循環(huán)來執(zhí)行當(dāng)待檢查的節(jié)點堆棧元素，當(dāng)元素不為空時執(zhí)行循環(huán);若元素為空，則說明壓縮算法執(zhí)行完畢。While循環(huán)中的if判斷起點和終點之間是否還有其他節(jié)點，如果有則執(zhí)行下面的語句。道格拉斯算法的核心代碼為：

Pnt P0=new Pnt （）;//聲明線段起點。

Pnt P1=new Pnt（）;//聲明線段終點。

StackproPnt=new Stack（）;//待檢查的節(jié)點堆棧。

StackrePnt=new Stack（）;//壓縮結(jié)果的堆棧。

Int intYuZhi=Convert.ToInt16（toolStripComboBox1.Text）;//讀取閾值。

Po=oriPnt[0];//設(shè)置初始起點。

P1=oriPnt[intoriPntNum-1];//設(shè)置初始終點。

rePnt.Push（P0）;//初始起點壓入結(jié)果堆棧。

proPnt.Push（P1）;//初始終點壓入待檢查的節(jié)點堆棧。

while（proPnt.Count ！=0）//當(dāng)待檢查的節(jié)點堆棧元素不為空時，執(zhí)行循環(huán);若元素為空，則說明壓縮算法執(zhí)行完畢。

{if（P0.ID ！=P1.ID-1）

//設(shè)置一個線段距離最大的節(jié)點，并初始化它到線段的距離最小。

Pnt maxPnt=new Pnt（）;maxPnt.Dis=0;

//循環(huán)線段起點和終點之間的所有其他節(jié)點，若距離大于maxPnt則代替它。

for（int j=P0.ID+1;j<=P1.ID-1;j++）

{Pnt tempPnt=new Pnt（）;

tempPnt=oriPnt[j];

tempPnt.Dis=Distanct（P0，P1，tempPnt）;//調(diào)用一個自定義函數(shù)Distanct，返回值為點到線段的距離。

if（tempPnt.Dis>maxPnt.Dis）

{maxPnt=tempPnt;}

}

//找出距離線段距離最遠的節(jié)點以后，比較其距離和閾值的大小。

//若大于閾值，則將節(jié)點壓入到待檢查的節(jié)點堆棧，并將該節(jié)點設(shè)置為線段的終點。

If（maxPnt.Dis>intYuZhi）

{P1=maxPnt;proPnt.Push（maxPnt）;

}//若小于閾值，則將終點設(shè)置為線段起點，并壓入到結(jié)果堆棧中，并將待檢查堆棧頂部的節(jié)點設(shè)置為線段終點。

Else //判斷起點和終點之間是否還有其他節(jié)點，如果沒有則執(zhí)行：

{P0=P1;rePnt.Push（P0）;

proPnt.Pop（）;

if（proPnt.count ！=0）{P1=proPnt.Peek（）;}

}}

While（rePnt.count ！=0）//置換堆棧中節(jié)點的順序。

{proPnt.Push（rePnt.Pop（））;}

}

3? 結(jié)果分析

3.1? GIS軟件下化簡結(jié)果

將矢量化后的長江水系簡圖數(shù)據(jù)文件導(dǎo)入軟件，再將已投影的矢量化線狀圖層拖到窗體中。并對矢量化的線狀要素圖層進行要素折點轉(zhuǎn)點，通過開方根算法將原始比例尺為1：1 000 000的長江水系簡圖化簡為比例尺為1：4 000 000的水系圖，將利用開方根算法化簡后的河流按照河流長度的大小排序。并將小于閾值205 215.772 6 km的河流刪除，此時通過人機交互的方式對河流的數(shù)量進行化簡，化簡后的新編地形圖上的河流數(shù)量為52條。其次使用ArcGIS的制圖工具中的制圖綜合，利用Douglas-peucker算法進行河流節(jié)點的化簡與壓縮，對河流線狀要素進行綜合化簡的效果從總體上來說還是非常實用和美觀的。結(jié)果圖如圖3所示。

3.2? 算法化簡結(jié)果

打開線性要素綜合化簡程序所在的文件夾。打開文件夾以后，找到該程序并點擊運行按鈕即可。此時就會生成線性要素綜合化簡的界面，點擊打開按鈕，同時把河流ID和河流長度文檔以及河流坐標(biāo)文檔導(dǎo)入界面之中。然后點擊開方根算法按鈕，對河流要素的數(shù)量進行化簡，然而，采用的閾值是河流的長度小于205 215.772 6 km的長度，大于這個閾值的河流予以保留。

將開方根算法化簡后的河流數(shù)量保存，并使用道格拉斯算法按鈕對化簡后的河流數(shù)量進行河流節(jié)點化簡和節(jié)點壓縮，將結(jié)果保存。化簡后的河流線狀要素圖形如圖4所示。

3.3? 化簡結(jié)果對比

在ArcGIS10.2軟件支持下并不能很好地按一定的閾值對河流的數(shù)量化簡，只能通過操作人員的手動操作來刪除不需要的河流線性要素。這一點是比較麻煩的，不但給實際操作人員帶來非常大的工作量，而且還會產(chǎn)生很大的誤差。這就要求工作人員時刻仔細認(rèn)真，以避免不必要的麻煩和相應(yīng)的后續(xù)工作。

在使用線性地物要素綜合化簡程序的過程中主要用到兩個線性要素化簡算法，分別是開方根算法和道格拉斯算法。首先將相關(guān)的河流數(shù)據(jù)導(dǎo)入化簡界面中，利用開方根算法對河流數(shù)量進行化簡，再利用道格拉斯算法對化簡的結(jié)果進行河流節(jié)點化簡和壓縮。此過程中可以利用開方根算法對大量的河流線狀要素進行數(shù)量化簡，并利用道格拉斯算法對化簡的結(jié)果進行節(jié)點化簡和壓縮。此過程可以節(jié)省大量的時間，提高工作人員的工作效率，對線狀要素的綜合化簡效果更好。可以為滿足實際需求而做出相應(yīng)的改變。同時還減少了經(jīng)費的支出，節(jié)省了大量的人力財力。

將化簡前的長江水系簡圖數(shù)據(jù)、ArcGIS10.2軟件支持下的線性要素化簡可視化結(jié)果和線性地物要素綜合化簡程序的化簡結(jié)果進行整理，并將其河流的節(jié)點數(shù)和河流條數(shù)統(tǒng)計在同一張表中進行比較分析，如表3所示。

通過對化簡后的圖形和表格數(shù)據(jù)進行對比分析，得出以下結(jié)論：

（1）由上表可知，利用算法程序化簡與利用GIS軟件化簡的河流數(shù)量相同，都為52條，其中算法程序化簡河流的節(jié)點數(shù)量要比GIS軟件化簡數(shù)量少，且圖形更平滑。

（2）在圖形上，算法程序化簡的結(jié)果比GIS化簡的結(jié)果更優(yōu)化、平滑、美觀。

（3）在自動化方面，算法程序化簡比GIS化簡更優(yōu)化，其人工編輯的部分少，自動化程度更高。

4? 結(jié)? 論

由于計算機技術(shù)發(fā)展迅速，信息化的程度越來越高，在線性要素制圖方面可以實現(xiàn)綜合的化簡算法向自動化方向發(fā)展。將相關(guān)的算法與人工智能相結(jié)合，優(yōu)化算法結(jié)構(gòu)，使其更好地為工作人員服務(wù)。

然而，傳統(tǒng)的道格拉斯算法在計算過程中通常沒有考慮到記錄的中間距離最大的節(jié)點，導(dǎo)致循環(huán)時間和遞歸嵌套層次過深，影響了程序的運行效率。本文提出一種基于堆棧數(shù)據(jù)結(jié)構(gòu)的分段道格拉斯算法。從曲線的一端開始，取起始點和終止點作為改進道格拉斯算法的工作范圍。然后，確定最遠點的距離是否大于規(guī)定限差，從而完成線性要素的化簡。本文的Douglas-peucker算法，通常使用堆棧記錄中間結(jié)果，得到最終結(jié)果。為了保證曲線的極值點不被刪除，將曲線在彎曲極值點處分成兩段，彎曲極值點由中間點與相鄰兩個頂點的夾角來測量。

根據(jù)結(jié)果對比可以看出，雖然結(jié)果相差不大，但在相同的閾值下，線性地物要素綜合化簡算法程序的自動程度更高，結(jié)果更優(yōu)化。

參考文獻：

[1] 齊清文，姜莉莉.面向地理特征的制圖綜合指標(biāo)體系和知識法則的建立與應(yīng)用研究 [J].地理科學(xué)進展，2001（S1）：1-13.

[2] 王留召，梁洪有，米振通.地圖自動綜合的現(xiàn)狀及發(fā)展方向 [J].中州煤炭，2001（6）：15-16.

[3] 應(yīng)申，李霖.制圖綜合的知識表示 [J].測繪信息工程，2003（6）：26-28.

[4] 裵廷睿.主成分分析與系統(tǒng)聚類法在評估經(jīng)濟效益中的應(yīng)用 [J].湘潭大學(xué)自然科學(xué)學(xué)報，1995（2）：30-33.

[5] 陳波.道路網(wǎng)自動制圖綜合的研究和實踐 [D].鄭州：解放軍信息工程大學(xué)，2006.

[6]毛贊猷，朱良，周占鰲，等.新編地圖學(xué)教程：第2版 [M].北京：高等教育出版社，2008.

[7] 初宏晟，劉穎，宋國大.保持圖形特征的線狀要素的化簡方法 [C]//2008年（第十屆）中國科協(xié)年會.鄭州：中國科學(xué)技術(shù)協(xié)會，2008：562-565.

[8] 汪琦，陳飛翔，彭俊杰.適用于移動平臺的快速生成地形剖面線方法 [J].地球信息科學(xué)學(xué)報，2015，17（7）：830-836.

[9] 張利君.土地利用總體規(guī)劃制圖綜合方法研究 [D].上海：華東師范大學(xué)，2011.

[10] 李巧，董箭.道格拉斯-普克改進算法及其在海圖岸線制圖綜合中的應(yīng)用 [C]//第十屆東北三省測繪學(xué)術(shù)與信息交流會.漠河：中國測繪學(xué)會，2009：378-380.

作者簡介：陳鋒（1994—），男，漢族，安徽六安人，碩士研究生在讀，研究方向：礦山開采沉陷監(jiān)測。