淺談線性地物自動綜合

王晉

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

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

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

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

1.自動綜合算法介紹

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

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

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

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

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

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

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

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

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

圖1

解算過程如下：

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

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

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

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

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

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

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

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

圖2

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

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

2.自動綜合的算法分析

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

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

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

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

3.結(jié)論

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

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

【參考文獻】

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

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

[3]郭慶勝，李沛川.地圖自動綜合方法的研究進展.地圖.雜志，1999：1.