簡化線狀要素算法實現及比較研究

陳炫巖+劉福江

摘 要：在GIS研究中，地圖矢量數據通常用線狀圖形表達，研究主要集中在線狀要素自動簡化模型建立上。為對比不同線狀要素簡化算法的特點，分別對面積和道格拉斯匹克兩種線要素簡化算法進行了簡化，并通過橫向和縱向對算法進行比較。實驗結果發現，道格拉斯匹克算法隨簡化率升高，保留點下降速率相對柔和，在相同簡化率的情況下，道格拉斯匹克算法單位長度偏移更小。因此，從整體上考慮，道格拉斯匹克算法性能更優。

關鍵詞：制圖綜合；線狀要素簡化；基于面積的算法；道格拉斯匹克算法

DOIDOI：10.11907/rjdk.172089

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0029-03

0 引言

空間數據多尺度表達問題是GIS研究的重點，也是地圖自動綜合的瓶頸。地圖矢量數據都可用線狀圖形來表達，這就使多尺度研究的焦點主要集中在線要素自動簡化模型的建立上。許多學者已經對此問題作了大量研究，Douglas DH和Peucker TK[1]提出DP算法，其采用首尾相連進行迭代化簡；Li Zhi-lin和Openshaw[2]提出基于客觀綜合的自然規律的線劃要素化簡的方法；VisvaLingam 和Whyatt[3]提出基于最小面積的重復式點刪除方法；Salfeld[4]提出基于邏輯一致的Douglas算法；郭慶勝[5]提出漸進式化簡算法；武芳[6]提出面向地圖基于遺傳算法的線要素化簡算法等。線簡化算法種類繁多[7-8]，本文以道格拉斯匹克（DP）算法和最小面積算法為例，縱向研究每種算法的簡化特點，并橫向比較兩種算法的優劣。

1 算法概述

1.1 基于面積的線要素簡化

迭代計算相鄰3點圍成面積，如果大于先前設定的面積，則保留這3個點，并向下遍歷；若小于先前設定的面積，則刪除中間的點，繼續向下遍歷選點，直至遍歷整條線段。

1.2 道格拉斯匹克線要素簡化

先選擇首尾兩點連接，遍歷兩點之間的所有點，找到距離首尾連線垂距最大的點，若最大垂距小于設定閾值，則刪除中間的所有點；若最大垂距大于設定閾值，則保留此點，并將其與首尾相連，得到兩根新的線段。分別對新線段進行如上操作，直至判斷完整個曲線上的點。

2 研究方法及技術路線

首先明確線狀要素簡化的原因，是為了滿足不同比例尺下的地圖信息表達[9-10]。首先明確一個概念——簡化率，因為線狀要素簡化的方法是先將其降維，轉化為一系列離散的點狀要素，再合理選取這些描述線要素的點要素，重新形成簡化后的線要素。所以，簡化率定義為：

α=Ndelete/Nsum（1）

其中，α為簡化率，Ndelete為刪除的點數，Nsum為簡化前的總點數。

另外，在不同比例尺下，盡管是同一條線段，也要用不同數量的點對其進行描述，即地圖綜合。所以，假設曲線原圖比例尺為1：n，簡化前的總點數為Nsum，若要轉換到1：N比例尺下，應該保留的點數Nreserve為：

Nreserve=nN×Nsum（2）

又有：

Ndelete=Nsum-Nreserve（3）

所以：

Ndelete=Nsum×1-nN（4）

又有：

α=Ndelete/Nsum（5）

所以：

α=1-nN（6）

基于以上公式，首先縱向評估每種算法在不同簡化率下的化簡效果，得到對應的閾值和保留點數Nreserve的對應關系，在Excel中擬合曲線，得到兩者之間的函數關系，進而得到閾值與比例尺之間的函數關系，定量描述出兩種簡化算法的簡化特點。至此，可以實現在比例尺無級縮放條件下的閾值選擇。

另一方面，橫向對比兩種方法，在同樣的簡化率下，用兩種方法分別對同一條曲線進行簡化，得到簡化后的曲線。將簡化后的曲線和原曲線在ArcGIS中打開，計算出相交面積，通過控制簡化率一致，從面積差異來對比評估兩種方法的簡化效果。

3 簡化結果縱向分析

3.1 基于面積的線要素簡化

3.1.1 實驗數據及流程

選取一條初始點數為164的曲線作為實驗數據，將其坐標值導入.txt文件，使用C++程序讀入文件，經過簡化算法后輸出到.txt文件，再導入Excel中畫出曲線。

3.1.2 簡化結果

選取不同閾值，得到不同保留結果，計算出簡化率，進而求出相應的比例尺分母放大倍數，即找到此方法閾值對應的縮放尺度。另外，得到設定閾值和保留點數的對應關系后，根據對應關系產生的散點，在Excel中使用冪函數進行擬合，顯示擬合方程，即可得到由離散點到連續化的映射，從而得到比例尺無級縮放條件下對應的簡化閾值。

基于以上對應關系，得到設定閾值與保留點數之間的散點關系，在Excel中將散點進行擬合，得到初步的連續函數。在此函數中，即可得到比例尺無級變化下對應的閾值。此函數關系為：

y=2 125.1x-0.396（7）

相關系數為：

R2=0.993 7

可以發現，在基于面積的線要素簡化方法中，保留函數與冪函數相近，在初期保留點數下降較快，但是隨著閾值不斷增大，保留點數緩慢收斂于2，即首尾兩點，相應函數表達式如上文所示。

3.2 基于道格拉斯匹克的線要素簡化

3.2.1 實驗數據及流程

數據及流程同3.1.1，采用同一根線控制變量，研究簡化特點。

3.1.2 簡化結果

基于以上對應關系，同樣可以得到在道格拉斯匹克算法下設定閾值與保留點數之間的散點關系。在Excel中將散點擬合，得到初步的連續函數，此函數關系為：endprint

y=317.31x-0.57（8）

相關系數為：

R2=0.993 1

對比基于面積的線簡化算法，道格拉斯匹克算法的保留函數柔和很多，下面分析兩種保留函數保留點數下降的速率。

分別對兩個保留函數求導，得到其導函數，可知導函數為其簡化速率。兩者相除，則可知簡化速率的相對倍數。

基于面積的簡化方式的簡化速率為：

v1=-841.539 6x-1.396（9）

基于道格拉斯匹克算法的簡化方式的簡化速率為：

v2=180.900 9x-1.57（10）

所以，面積簡化算法的簡化速率為DP算法的v1/v2倍：

v1v2=4.651 9x0.174（11）

4 簡化結果橫向分析

選擇簡化率為80%的兩種算法進行簡化結果的橫向比較分析。基于面積的簡化線閾值為40，簡化率為80%，保留點數為32；基于道格拉斯匹克的簡化線閾值為50，簡化率為80%，保留點數為32。

將簡化結果與源數據相交，求得相交的面積區域總和。統計結果為40個相交區域，面積最大值為49 918.111 021，面積最小值為49.419 953，面積總和為479 090.813 592，單位長度面積偏移量為20.020 091 4。

同理，將基于道格拉斯匹克算法的簡化結果與源數據相交，求得相交的面積區域總和。統計結果為56個相交區域，面積最大值為62 933.889 761，面積最小值為15.621 068，面積總和為330 143.467 505，單位長度面積偏移量為13.795 928 05。

以下定量比較兩種方法的簡化效果，統計結果如表3所示。

經過分析對比可以得到，當線簡化的簡化率相同時，基于面積簡化的效果不如基于道格拉斯匹克算法簡化的結果。可以從單位長度面積偏移量對比，也可以從相交區域的面積總和值進行對比。但是從最大值和最小值的角度來看，基于面積的算法是從局部進行簡化的，而道格拉斯匹克算法是從空間分布整體進行簡化的。因此，基于道格拉斯匹克算法的Max值大于基于面積算法的Max值。

5 結語

由分析結果可以得到，基于面積簡化的偏移面積總和與基于道格拉斯匹克算法的簡化線的偏移面積總和之差為：

△Sum=Sum（Area）-Sum（DP）

當兩個算法簡化率相同時，可通過計算面積之差來比較簡化效果。這里選擇簡化率為80%時的面積數據，得到△Sum=6.224 163 4。當簡化率相同且達到一定值時，基于面積和基于道格拉斯匹克算法的簡化面積偏移量相差并不大，但是可以定量反映出兩種簡化效果的差別。

本文通過建立每一種簡化算法對應的閾值T和保留點數Nreserve的函數關系，近似擬合曲線得到一般規律。利用一般規律來確定簡化線的閾值大小，進而確定對應的簡化率以及縮放的比例尺等。下一步可以繼續研究當簡化率大小不同時，兩種算法簡化面積偏移的變化，也可以繼續模擬擬合曲線，以進一步定量研究兩種算法的優劣。

參考文獻：

[1] DOUGLAS DH，PEUCKER TK.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].The CanadianCartographer，1973，10（2）：112-122.

[2] ZHILIN LI，STAN OPENSHAW.Algorithms for automated line generalization based on a natural principle of objective generalization[J].Geographical Information Systems，1992，6（5）：373-389.

[3] MVISVALINGAM，JD WHYATT.Line generalization by repeated elimination of the smallest area[J].The Cartographic Journal，1993，30（1）：46-51.

[4] SAALFELD A.Topologically consistent line simplification with the douglas-peuckeralgorithm[J].Cartography and Geographic Information Science，1999，26（1）：7-18.

[5] 郭慶勝.線狀要素圖形綜合的漸進方法研究[J].武漢測繪科技大學學報，1998，23（1）：52-56.

[6] 武芳，錢海忠，鄧紅艷，等.面向地圖自動綜合的空間信息智能處理[M].北京：科學出版社，2008：164-170.

[7] 劉鵬程，羅靜，艾廷華，等.基于線要素綜合的形狀相似性評價模型[J].武漢大學學報信息科學版，2012，37（1）：114-117.

[8] 雷偉剛，童小華，劉大杰.基于曲線擬合的線要素綜合數據整體處理方法[J].武漢大學學報：信息科學版，2006（10）：896-899.

[9] 李霖，于忠海，朱海紅，等.地圖要素圖形沖突處理方法——以線狀要素（道路、水系和境界）為例[J].測繪學報，2015，44（5）：563-569.

[10] 鄧敏，彭東亮，徐震，等.一種基于彎曲結構的線狀要素Morphing方法[J].中南大學學報：自然科學版，2012（7）：2674-2682.endprint