王晉

【摘 要】本文主要對(duì)線性地物自動(dòng)綜合算法進(jìn)行了探討，并在對(duì)其中的幾種算法（Lang算法，Douglas-Peucker算法，Visvalgam-Whyatt算法）進(jìn)行實(shí)現(xiàn)的過(guò)程中有一些心得，希望與大家共享。

【關(guān)鍵詞】自動(dòng)綜合；基線；搜索區(qū)域

隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，計(jì)算機(jī)制圖已經(jīng)廣泛應(yīng)用于測(cè)繪領(lǐng)域中。但是計(jì)算機(jī)制圖不可能把地面全部景物毫無(wú)遺漏地表示出來(lái)，由于空間的限制，只能用有限的空間清晰地表達(dá)制圖區(qū)域的部分內(nèi)容。因此，根據(jù)實(shí)際工作的需要，隨著編圖比例尺的縮小，需要對(duì)資料圖的地類進(jìn)行取舍與概括，這就是我們要提到的自動(dòng)綜合。

地圖的自動(dòng)綜合是從原始的地圖數(shù)據(jù)庫(kù)（大比例尺）綜合得到較小比例尺的地圖數(shù)據(jù)庫(kù)，并生成可視化的地圖產(chǎn)品。它是實(shí)現(xiàn)測(cè)繪自動(dòng)化非常重要的一項(xiàng)內(nèi)容。目前，自動(dòng)綜合的研究類型和內(nèi)容很多，其中每一類型的算法也比較多，本文主要對(duì)線性地物自動(dòng)綜合的幾種算法進(jìn)行探討。

1.自動(dòng)綜合算法介紹

線性地物的自動(dòng)綜合是自動(dòng)綜合中較為重要的一項(xiàng)內(nèi)容。其目的就是使存儲(chǔ)量最少，保持線的彎曲特征。有的學(xué)者總結(jié)了線性要素自動(dòng)綜合應(yīng)該遵循的4條原則：

（1）小彎曲刪除，大彎曲保留。

（2）2個(gè)彎曲，3個(gè)彎曲可合并成一個(gè)彎曲，依此類推。

（3）獨(dú)立性強(qiáng)的彎曲應(yīng)保留或夸大。

（4）自然的線不能變成幾何的線。

目前提出的主要具體算法有：nth點(diǎn)算法，Douglas-Peucker算法，垂距算法，角度算法，對(duì)于每一種算法，其評(píng)價(jià)的基本要求是：變形量最少；數(shù)據(jù)壓縮量最大；目標(biāo)的完整性；關(guān)系的完整性；參數(shù)盡量少；參數(shù)和地圖綜合結(jié)果應(yīng)當(dāng)明顯，效果好，效率高。

1）Independ point algorithms（獨(dú)立點(diǎn)算法）：這種算法沒(méi)有考慮與相鄰點(diǎn)的幾何關(guān)系而孤立地進(jìn)行取舍。例如：nth點(diǎn)算法，對(duì)于一條直線保留了nth個(gè)點(diǎn)，其余的全被消除，而且這種選取也是隨機(jī)的。顯爾易見(jiàn)，這種算法很難保持圖形形狀，從而產(chǎn)生很大的變形。因此，現(xiàn)在很少有人再用這種算法。

2）Local processing algorithms（局部處理算法）：顧名思義，對(duì)于一個(gè)點(diǎn)的取舍要根據(jù)與之相鄰點(diǎn)的特征。研究表明：這種算法產(chǎn)生的變形較小，但是它不如下面的幾種算法。

3）Constrained extended local processing algorithms（強(qiáng)制延伸局部處理算法）：這種算法的搜索區(qū)域不再局限在相鄰點(diǎn)上，而是根據(jù)距離，角度，或頂點(diǎn)個(gè)數(shù)延伸。最具代表性的是Lang algorithms，它是早期開(kāi)發(fā)的算法之一。這種算法中，區(qū)域的延伸要受到“ look-ahead”參數(shù)的控制，要消除的頂點(diǎn)個(gè)數(shù)由垂直距離允許值e決定。算法圖解如圖1所示：

圖1

解算過(guò)程如下：

（1）首先確定一條基線，基線由起點(diǎn)與終點(diǎn)（起點(diǎn)+look-ahead）構(gòu)成；

（2）計(jì)算每個(gè)點(diǎn)到基線的垂直距離，如果有一個(gè)值超出了允許值ε，重新構(gòu)成基線（起點(diǎn)不變，終點(diǎn)向后退一個(gè)），重新計(jì)算，直到所有距離值都小于允許值ε。然后重新確定基線，算法繼續(xù)。

對(duì)于這種算法，如果look-ahead和ε的值設(shè)置恰當(dāng)，能夠產(chǎn)生很好的綜合效果，對(duì)于變形量和數(shù)據(jù)壓縮可以控制；但是，參數(shù)較多，參數(shù)值的確定較難。

（3）Unconstrained extended local processing algorithms（自然延伸局部處理算法）：這種算法的搜索區(qū)域不再局限在相鄰點(diǎn)內(nèi)，但是它不象上一個(gè)算法受 “l(fā)ook-ahead”參數(shù)的控制，而是受圖形復(fù)雜度的限制。Reumann and Witkam 描述了這種算法：

由兩條平行線組成的搜索區(qū)域向前延伸，直到和某一直線相交（每條平行線到基線的距離為ε），所有落在該區(qū)域內(nèi)的點(diǎn)（除第一點(diǎn)和最后一點(diǎn)外）都被消除，從而又產(chǎn)生一個(gè)新的搜索區(qū)域，算法繼續(xù)。

（4）Global algorithms：其中Douglas and Peucker算法最為有名，作一條連接起點(diǎn)與終點(diǎn)的直線，作為基線，如果每個(gè)點(diǎn)到基線的距離都小于ε，這些點(diǎn)被消除，基線取代折線，否則，在距離最大的頂點(diǎn)處分為兩部分，算法繼續(xù)。算法如圖2所示。

這種算法應(yīng)用非常廣泛，首先是the globle tolerance band 概念具有很強(qiáng)的直觀感染力；其次，它是應(yīng)用于GIS中最早的算法。

Visvalingam and Whyatt 指出了允許帶寬算法的不足，他們認(rèn)為：選取超過(guò)允許距離中最遠(yuǎn)距離的點(diǎn)作為臨界點(diǎn)是不科學(xué)的，因?yàn)檫@個(gè)點(diǎn)可能是不準(zhǔn)確的或是具有最小特征的點(diǎn)。為了保持圖形的形狀和特征，他們提出一種新的算法，這種算法根據(jù)各點(diǎn)的影響區(qū)域而對(duì)該點(diǎn)進(jìn)行取舍。一個(gè)點(diǎn)的影響區(qū)域就是該點(diǎn)和與其相鄰各點(diǎn)形成的三角形的面積。

圖2

這種算法比較簡(jiǎn)單，圖形上的每個(gè)頂點(diǎn)（除起、終點(diǎn)外）都形成一個(gè)區(qū)域三角形，具有最小影響面積的點(diǎn)被去掉，當(dāng)某點(diǎn)被去掉后，與其相鄰點(diǎn)需要重新計(jì)算。算法如圖3所示：

研究表明：Visvalingam-Whyatt算法在保持線的性狀方面具有優(yōu)勢(shì)，而Douglas-Peucler算法在數(shù)據(jù)壓縮方面具有優(yōu)勢(shì)。

2.自動(dòng)綜合的算法分析

對(duì)于以上的幾種算法進(jìn)行比較，可以發(fā)現(xiàn)它們都有一定的不足之處和一定的適用范圍：

（1）Mahes Visvalingam等針對(duì)大比例尺道路的綜合，對(duì)Douglas-Peucker 和Visvalingam算法進(jìn)行了比較，其結(jié)論是：Douglas-Peucker算法得不到彎曲特征的綜合效果，在點(diǎn)最少的簡(jiǎn)化條件下，它比Visvalingam算法優(yōu)越，通過(guò)實(shí)驗(yàn)，他認(rèn)為壓縮到40%時(shí)，兩種算法對(duì)于道路（大比例尺）而言，都會(huì)產(chǎn)生變形。

（2）Erick.VanHom考慮地圖數(shù)據(jù)庫(kù)中的線在計(jì)算機(jī)顯示器上顯示時(shí)，由于分辨率的限制和顯示比例尺的縮小，采用Douglas-Peucker方法會(huì)使線的圖形產(chǎn)生變形，因此在用該方法之前，先用點(diǎn)的重定位技術(shù)，即先把點(diǎn)歸算到最近的網(wǎng)格上，該方法也會(huì)產(chǎn)生線的自交問(wèn)題，解決辦法是手工糾正。

（3）Douglas-Peucker算法同USGSB算法，nth點(diǎn)算法，垂距算法，角度算法的比較結(jié)果是：綜合時(shí)應(yīng)當(dāng)區(qū)分自然的線要素和人文的線要素。

3.結(jié)論

對(duì)于以上的各種算法，我們不能簡(jiǎn)單地進(jìn)行評(píng)價(jià)，它們都具有各自的使用范圍，因此，在線性地物自動(dòng)綜合中要根據(jù)實(shí)際工作的需要，采用適當(dāng)?shù)乃惴ā?/p>

地圖自動(dòng)綜合是一項(xiàng)工程性任務(wù)，必須從工程設(shè)計(jì)的角度看待地圖自動(dòng)綜合問(wèn)題，也就是說(shuō)，設(shè)計(jì)的地圖自動(dòng)綜合系統(tǒng)應(yīng)能完成地圖綜合任務(wù)，生產(chǎn)出滿足用戶要求的產(chǎn)品。 [科]

【參考文獻(xiàn)】

[1]烏巧倫，劉瑜，張晶等.地理信息系統(tǒng)—原理、方法和應(yīng)用.科學(xué)出版社，2002.

[2]郭慶勝，李沛川.地圖自動(dòng)綜合系統(tǒng)的概念框架設(shè)計(jì).測(cè)繪信息與工程.雜志，1999：1.

[3]郭慶勝，李沛川.地圖自動(dòng)綜合方法的研究進(jìn)展.地圖.雜志，1999：1.