楊紅雷1，陳 杰2

（1．長安大學(xué)地測學(xué)院，陜西西安 710000；2．山西大同大學(xué)地測與安全工程系，山西大同 037003）

作者簡介：楊紅雷（1991－），男，長安大學(xué)地測學(xué)院碩士研究生，測繪工程專業(yè)。

陳 杰（1982－），男，山西臨汾人，講師，碩士，畢業(yè)于中南大學(xué)地圖學(xué)與地理信息系統(tǒng)專業(yè)。

摘 要：地圖綜合是當(dāng)前國際GIS和制圖學(xué)領(lǐng)域的一個(gè)重要研究問題，化簡是地圖綜合的一類基本算子，線要素是地圖綜合操作的主要對(duì)象，又是基礎(chǔ)的并且至關(guān)重要的要素。論文首先歸納和總結(jié)常用的曲線簡化的算法；然后，以一境界線為實(shí)驗(yàn)對(duì)象，結(jié)合常用的幾種簡化算法對(duì)其進(jìn)行不同程度的簡化；最后，分別從幾個(gè)指標(biāo)來評(píng)價(jià)各方法的優(yōu)劣。

關(guān)鍵詞：曲線化簡；算法比較；分析評(píng)價(jià)

Abstract：Map generalization is an international field of GIS and Cartography important research issue currently．Simplification is a map of a class of integrated basic operator．Line feature is not only the main object map integrated operation，but also the basic and essential elements．Firstly，induction and summarized common curve simplification algorithm；Then，as experimental subjects to a boundary line，combined with several commonly used simplified algorithm to simplify the different degrees；Final－ly，from several indicators to evaluate the pros and cons of each method respectively．

Key words：curve simplification；algorithm comparison；analysis and evaluation

1 引 言

隨著地理空間信息應(yīng)用領(lǐng)域不斷擴(kuò)展，地圖綜合服務(wù)需求也變得的多樣化。線要素是地圖綜合操作的主要對(duì)象，一般地圖內(nèi)容中線要素可占80％以上?，F(xiàn)今簡化算法的主要共同特征是對(duì)節(jié)點(diǎn)或特征點(diǎn)的數(shù)據(jù)進(jìn)行壓縮，剔除和刪減不必要的點(diǎn)。

一般來講，考慮的曲線要素都在二維平面內(nèi)進(jìn)行操作。在實(shí)際操作中，對(duì)于信息量很大的要素，簡化是必要的。簡化時(shí)，目的是為了避開反映特征的點(diǎn)要素的丟失，以保持線性圖形特征的形態(tài)。典型的且應(yīng)用廣泛的方法有道格拉斯－普克（Douglas－Peucker）算法［1］、垂距法［2］、光欄法（偏角法或扇形法）［3］、角度法［4］、垂比弦法［5］、弧比弦算法［6］以及針對(duì)不同方法的相應(yīng)改進(jìn)等。每種方法都有其本身的優(yōu)點(diǎn)，對(duì)于不同的曲線要素有不同的算法進(jìn)行，這由它們本身所存在的局限性和曲線本身特征所決定。無論是什么方法，其本質(zhì)上都是為了壓縮數(shù)據(jù)量，優(yōu)化曲線的化簡過程，更合理保持圖形基本形態(tài)特征。在圖形制作過程中，面臨的邊界線、道路線、河流以及海岸線等都需要涉及曲線簡化，簡化在地理信息系統(tǒng)、地圖學(xué)以及計(jì)算機(jī)方面具有廣闊的應(yīng)用前景，它的研究具有十分重要的理論意義和應(yīng)用價(jià)值。

論文首先介紹了典型的四種曲線簡化的算法，然后，分別從不同的評(píng)價(jià)指標(biāo)來對(duì)給定的曲線簡化的效果進(jìn)行評(píng)價(jià)，最后，分析了各簡化方法優(yōu)劣及適用條件。

2 化簡算法

2．1 道格拉斯－普克法（Douglas－Peucker）

該方法簡化過程：連接首末節(jié)點(diǎn)形成一條直線，求得所有節(jié)點(diǎn)的垂直距離，找到最大值M，再與容差D比較：如果M小于D，剔除中間所有的點(diǎn)；如果M大于等于D，保留M處的節(jié)點(diǎn)，以該點(diǎn)為邊界點(diǎn)，將曲線一分為二，重復(fù)操作，直至結(jié)束。

該算法是一種整體算法，這樣可以更好地保證圖形的整體效果，將重要節(jié)點(diǎn)保留，使圖形變形穩(wěn)定，保持圖形形態(tài)特征。道格拉斯－普克算法能準(zhǔn)確剔除不重要的節(jié)點(diǎn)，保證圖形整體精度。由于該算法為遞歸算法，壓縮數(shù)據(jù)時(shí)比較復(fù)雜，也是其不足之處。

2．2 垂距法

垂距法的簡要思路：依次連接由相鄰三節(jié)點(diǎn)組成的三元組，求得中間點(diǎn)的垂距，跟設(shè)定參數(shù)最大距離D相比：如果M小于D，刪除中間點(diǎn)；如果M大于等于D，保留并將其作為下一個(gè)三元組的第一個(gè)點(diǎn)，依次繼續(xù)處理，最終計(jì)算到末點(diǎn)結(jié)束。

垂距法算法簡單，易于操作。但由于其為局部算法，每次只是從一個(gè)三元組考慮，不能整體把握?qǐng)D形特征，于是化簡中可能出現(xiàn)圖形特征的較大改變。就算是設(shè)定的最大距離比較小，但由于相鄰點(diǎn)間變化不大，也可能造成中間的最大值點(diǎn)被刪掉，圖形特征完全反映不出來。綜合考慮，對(duì)于線要素的化簡，垂距法要根據(jù)實(shí)際條件來使用，以達(dá)到化簡效果。

2．3 光欄法

光欄法的理解從偏角或扇形的概念入手。在處理曲線時(shí)，先在曲線上做一個(gè)扇形，也可看成是偏角，得到一個(gè)區(qū)域，通過判斷節(jié)點(diǎn)是否在劃定的區(qū)域內(nèi)選擇節(jié)點(diǎn)去留。下面通過圖形解釋，如圖1所示：

圖1 光欄法示意圖

（1）首先在P1處確定扇形區(qū)域。設(shè)定d為參數(shù)，過P2做P1P2的垂線，在d／2處交于兩點(diǎn)，跟P1相連，確定扇形或偏角區(qū)域。（2）接著跟蹤第三點(diǎn)，確定第三點(diǎn)的位置。如果該點(diǎn)在鎖定范圍內(nèi)，刪除第二點(diǎn)，然后以第三點(diǎn)為原第二點(diǎn)，重復(fù)1操作中的步驟。（3）如果新的點(diǎn)又跑出該區(qū)域，則由新的邊界交點(diǎn)替代原交點(diǎn)。（4）重新進(jìn)行以上操作，若節(jié)點(diǎn)在范圍內(nèi)，重復(fù)2步驟，直至有節(jié)點(diǎn)在所劃定區(qū)域外為止。（5）若節(jié)點(diǎn)在所劃定范圍外，則以該節(jié)點(diǎn)的前一節(jié)點(diǎn)為初始，開始重復(fù)以上操作，直至結(jié)束。

2．4 角度法

該方法的基本思想是：每次順序取曲線上的三個(gè)點(diǎn)，計(jì)算有三個(gè)點(diǎn)組成的夾角X，并與給定的最大角度Y進(jìn)行比較：如果X大于等于Y，則將中間的點(diǎn)刪除；如果X小于Y，保留該點(diǎn)。之后依次順序進(jìn)行處理，直至結(jié)束。如圖2所示：

（1）首先，將節(jié)點(diǎn)P1剔除掉，那么，現(xiàn)在我們看到的是節(jié)點(diǎn)線要素P0P1P2變成P0P2，曲線方向改變大小為∠1＋∠2＝∠①；（2）現(xiàn)在，假若去掉的是節(jié)點(diǎn)P2，曲線方向改變大小為∠3＋∠4＝∠②；（3）同樣的，節(jié)點(diǎn)P3被刪除，曲線方向改變大小為∠5＋∠6＝∠③。從節(jié)點(diǎn)線要素方向控制的角度，節(jié)點(diǎn)是否重要主要的判斷標(biāo)準(zhǔn)為節(jié)點(diǎn)與前后相鄰節(jié)點(diǎn)夾角的補(bǔ)角大小。補(bǔ)角越大，節(jié)點(diǎn)對(duì)曲線的轉(zhuǎn)折作用越大，節(jié)點(diǎn)越重要，選擇保留。

圖2 基于角度的節(jié)點(diǎn)重要性程度

3 評(píng)價(jià)指標(biāo)

線要素簡化算法評(píng)價(jià)指標(biāo)有從局部的位置精度描述，也有側(cè)重線要素的整體形態(tài)結(jié)構(gòu)。本文主要是比較簡化前后線要素的形狀逼近程度，重點(diǎn)趨于幾何精度的評(píng)價(jià)標(biāo)準(zhǔn)［7］。評(píng)價(jià)算法的好與不好，主要比較在簡化程度相同時(shí)，能保持較高的幾何位置精度，即能夠更好地保持圖形形態(tài)特征［8］。對(duì)于線狀要素化簡算法的評(píng)價(jià)化簡算法一般從面積差、彎曲度、最大拐角比率、化簡變化趨勢、化簡結(jié)果一致性和自相交性等方面來評(píng)價(jià)［9］。此間，關(guān)于面積差、彎曲度和最大拐角比率3個(gè)標(biāo)準(zhǔn)，無論用什么方法化簡，都必須選取合適的參數(shù)，使得曲線化簡前后的節(jié)點(diǎn)個(gè)數(shù)大致相等，若節(jié)點(diǎn)數(shù)相差很多，就沒法比較，無可比性。

這里最后加幾個(gè)評(píng)價(jià)指標(biāo)圖來說明一下。

4 實(shí)例分析

本實(shí)驗(yàn)選用內(nèi)蒙古1∶1000萬邊界線（初始節(jié)點(diǎn)為2025個(gè)），如圖3所示。針對(duì)該邊界線，分別用道格拉斯－普克法、光欄法、垂距法、角度法對(duì)其進(jìn)行簡化，采用相同的壓縮比率以確保保留相同數(shù)量的節(jié)點(diǎn)，來進(jìn)行比較分析?；啿捎脡嚎s比率為32∶1。

由于初始節(jié)點(diǎn)的數(shù)據(jù)量足夠大，因此各種方法化簡過程中節(jié)點(diǎn)個(gè)數(shù)相差的極個(gè)別個(gè)數(shù)可忽略不計(jì)，對(duì)比較分析幾乎無影響。

對(duì)應(yīng)的面積如表1：

表1 不同方法在相同壓縮比率下的化簡面積對(duì)比

圖3 不同方法在相同壓縮比率下的簡化對(duì)比

明顯看出化簡保留線性特征最好的是道格拉斯－普克算法，然后依次是光欄法、垂距法、角度法；道格拉斯－普克法和光欄法能較好的保持圖形特征，面積形變較小，面積保持較穩(wěn)定，而垂距法和角度法較差。

隨著壓縮比率不斷增大，各種方法出現(xiàn)的面積對(duì)應(yīng)的曲線變化趨勢如圖4：

圖4 4種方法的化簡變化趨勢對(duì)應(yīng)的曲線對(duì)比

由圖4的曲線變化趨勢可知：（1）隨著壓縮比的增大，道格拉斯－普克算法和光欄算法面積變形較穩(wěn)定；（2）角度法在一定的范圍內(nèi)較穩(wěn)定，當(dāng)超過一定的壓縮比率，面積變形逐漸變大；（3）垂距法的面積變化波動(dòng)相對(duì)比較隨機(jī)，不穩(wěn)定。同時(shí)，可知垂距法受初始圖形的形狀因素的影響較大。

化簡變化趨勢能明顯檢驗(yàn)化簡適用性。判斷標(biāo)準(zhǔn)是曲線化簡后的點(diǎn)數(shù)是否呈單調(diào)變化。根據(jù)如圖5，能夠比較出：（1）道格拉斯－普克算法和光欄算法的在面積變形穩(wěn)定的前提下，化簡變化趨勢的穩(wěn)定性也高；垂距法的線性程度相對(duì)較弱；（2）角度法面積穩(wěn)定時(shí)，壓縮比率小，而當(dāng)化簡變化趨勢線性化程度高時(shí)，面積變形較大。

圖5 4種方法的化簡變化趨勢

圖5是對(duì)應(yīng)圖4面積變形下4種方法的圖表節(jié)點(diǎn)變化統(tǒng)計(jì)的綜合比較，該趨勢比較反映的是一個(gè)線性化程度?；嗂厔莸谋容^主要看的是各自化簡方法本身節(jié)點(diǎn)的單調(diào)程度。因此，我們在進(jìn)行化簡趨勢的分析時(shí)，在一定意義上，直觀明了。

在化簡過程中，對(duì)于角度法的化簡中，出現(xiàn)了交叉的現(xiàn)象。如圖6所示：

圖6 化簡過程中所出現(xiàn)的自相交現(xiàn)象

經(jīng)過查閱文獻(xiàn)資料等，發(fā)現(xiàn)對(duì)于很多種方法均存在自相交現(xiàn)象，如道格拉斯－普克法和光欄法。因此，本實(shí)驗(yàn)對(duì)于角度法的自相交現(xiàn)象并非偶然，對(duì)于特定的曲線節(jié)點(diǎn)，化簡出現(xiàn)自相交現(xiàn)象可通過一定的方法解決。

就道格拉斯－普克法和光欄法之間的比較不很明顯。因此，對(duì)這兩種方法進(jìn)行進(jìn)一步對(duì)比，通過面積差和彎曲度進(jìn)行對(duì)比分析。

令初始面積S0，化簡后面積Si，面積差為ΔSi。則計(jì)算公式為

ΔSi＝Si－S0 　（1）

又：令始曲線的長度L，化簡后的長度Li，彎曲度（反映曲線迂回特征）的計(jì)算公式：

ΔLi＝Li／L0 ?。?）

由表2明顯看出，在相同壓縮比率的情況下，道格拉斯－普克法比光欄法的面積差小一個(gè)數(shù)量級(jí)，化簡后的整體偏移量要比光欄法小。在相同的壓縮比率的情況下，道格拉斯－普克法的彎曲度比光欄法的彎曲度大，化簡線狀要素更接近原 始曲線的線劃特征。

表2 相同壓縮比率下面積差和彎曲度的比較

5 結(jié)論及不足

道格拉斯－普克法在曲線化簡中能夠整體的保持圖形的特征形態(tài)，因此一直以來作為跟其他化簡算法及改進(jìn)算法比較的經(jīng)典算法有其合理性。光欄法的化簡效果也不錯(cuò)。對(duì)比各種分析方法，關(guān)于面積差、彎曲度等幾何精度方向的評(píng)估以及位置精度評(píng)估，雖操作手段不同，但基本思想如出一轍。在實(shí)際運(yùn)用過程中，根據(jù)不同需求有所側(cè)重地選擇合適的化簡及評(píng)價(jià)方法。

該實(shí)驗(yàn)整體上能客觀反映分析與評(píng)價(jià)，但還是存在一定的局限性。幾何精度并不是判斷化簡效果優(yōu)劣的唯一指標(biāo)?；喰Ч麜r(shí)常要兼顧曲線形狀特征、空間關(guān)系等。對(duì)于不同的圖形，有不同的圖形特征，進(jìn)行比較評(píng)價(jià)時(shí)，評(píng)價(jià)標(biāo)準(zhǔn)必定不完善，在處理過程中可能會(huì)出現(xiàn)偏差。此外，對(duì)于不同的化簡算法，都存在優(yōu)劣性，面對(duì)不同的地理特征、地形要素等，對(duì)于化簡算法的選擇要綜合考慮，考慮算法自身對(duì)不同線要素、比例尺和設(shè)定參數(shù)以及算法的適合用性等，并采取相應(yīng)的手段進(jìn)行比較分析。

參考文獻(xiàn)

［1］ Douglas D，Peueker T．Algorithms for the reduction of the number of points required to represent a digitized line of its caricature［J］．1973，10（2）：112－123．

［2］ 彭認(rèn)燦，董箭．垂距法與道格拉斯－普克法刪除冗余頂點(diǎn)效率的比較［J］．測繪通報(bào)，2010，3（1）：66－67．

［3］ 于曉艷．等高線簡化法評(píng)價(jià)體系研究［碩士學(xué)位論文］［D］．南京：南京大學(xué)，2011．

［4］ 劉慧敏．地圖空間信息量的度量方法研究［博士學(xué)位論文］［D］．長沙：中南大學(xué)，2012．

［5］ 鄧敏，陳杰，李志林，等．線目標(biāo)化簡中節(jié)點(diǎn)重要性度量方法比較及垂比弦法的改進(jìn)［J］．地理與地理信息科學(xué)， 2009，25（1）：40－43．

［6］ 劉慧敏，樊子德，徐震，等．曲線化簡的弧比弦算法改進(jìn)及其評(píng)價(jià)［J］．地理與地理信息科學(xué)，2011，27（1）：45－48．

［7］ 朱鯤鵬，武芳，陳波，等．基于約束條件的線要素化簡算法質(zhì)量評(píng)估［J］．測繪科學(xué)，2007，32（3）：28－29．

［8］ 武芳，朱鯤鵬．線要素化簡算法幾何精度評(píng)估［J］．武漢大學(xué)學(xué)報(bào)信息科學(xué)，2008，33（6），600－603．

［9］ 陳波，朱鯤鵬，薛本新．現(xiàn)狀要素化簡算法的分析評(píng)估［J］．測繪科學(xué)技術(shù)學(xué)報(bào)，2007，24（2）：121－124．