基于Douglas—Peucker的矢量數(shù)據(jù)壓縮算法

摘 要：由于Douglas-Peucker算法未考慮空間對(duì)象間的拓?fù)潢P(guān)系，易造成矢量空間數(shù)據(jù)壓縮后的面狀地物公共邊出現(xiàn)“裂縫”現(xiàn)象，出現(xiàn)失真問題。針對(duì)該問題，該文提出了Douglas-Peucker一種改進(jìn)算法，通過實(shí)驗(yàn)驗(yàn)證，改進(jìn)的算法不僅能較好地保留圖形特征，而且提高了壓縮精度。

關(guān)鍵詞：Douglas-Peucker算法 數(shù)據(jù)壓縮 深度匹配搜索算法

中圖分類號(hào)：P208 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）05（b）-0248-01

隨著GIS技術(shù)的不斷發(fā)展和應(yīng)用，GIS中大數(shù)據(jù)量的空間數(shù)據(jù)傳輸與無線通信網(wǎng)絡(luò)帶寬窄、以及移動(dòng)終端設(shè)備硬件條件有限的矛盾日益凸現(xiàn)出來。數(shù)據(jù)壓縮就成為解決該矛盾的有效方法之一。

矢量數(shù)據(jù)壓縮主要分為無損壓縮和有損壓縮兩大類，對(duì)于有損壓縮算法研究?jī)?nèi)容較多，如角度限值法[1]、Douglas-Peucker算法；如Zhilin Li等提出的基于“客觀綜合的自然規(guī)律”的線狀要素的化簡(jiǎn)算法[2]；S.T.Wu等提出的一種基于星形的Douglas-Peucker算法[3]；郭慶勝提出的純幾何的基于面積的漸進(jìn)式化簡(jiǎn)算法和基于彎曲以及三角形單元的漸進(jìn)式化簡(jiǎn)算法。這些算法從不同側(cè)面提高的壓縮效率及精度。該文擬考慮壓縮對(duì)象間拓?fù)潢P(guān)系，該文提出了Douglas-Peucker一種改進(jìn)算法，通過實(shí)驗(yàn)驗(yàn)證，改進(jìn)的算法不僅能較好地保留圖形特征，而且提高了壓縮精度。

1 傳統(tǒng)的Douglas-Peucker算法

矢量數(shù)據(jù)壓縮算法中比較經(jīng)典的是Douglas-Peucker算法，其基本思路如下：

Step1：設(shè)定限差，將任一曲線的首末點(diǎn)相連，求除首位點(diǎn)之外的中間點(diǎn)到首位連線的距離，并得到最大距離值，用與限差進(jìn)行比較；

Step2：若，這條曲線上的中間點(diǎn)全部舍去；

Step3：若，保留對(duì)應(yīng)的中間點(diǎn)，將首尾兩點(diǎn)與改點(diǎn)連接，形成新的兩條直線段，對(duì)新形成的直線段，重復(fù)step1和step2；

Step4：如此循環(huán)判斷，直到?jīng)]有滿足條件為止。

Douglas-Peucker算法簡(jiǎn)單，實(shí)現(xiàn)容易。具有較強(qiáng)的壓縮效率，但Douglas-Peucker算法同時(shí)也具有一些缺點(diǎn)，表現(xiàn)如下：

（1）從首或尾任意端點(diǎn)開始執(zhí)行Douglas-Peucker算法，得到的保留點(diǎn)結(jié)果可能不一樣，對(duì)于面狀地物壓縮，易出現(xiàn)相鄰兩個(gè)多邊形的邊界壓縮不一致；

（2）Douglas-Peucker算法壓縮結(jié)構(gòu)受的取值影響較大，不同的取值結(jié)果偏差較大，局部地方易出現(xiàn)是真現(xiàn)象。

2 基于Douglas-Peucker矢量數(shù)據(jù)壓縮算法

針對(duì)Douglas-Peucker算法存在的問題，本文提出了基于深度匹配搜索的Douglas-Peucker一種改進(jìn)算法，通過實(shí)驗(yàn)驗(yàn)證，改進(jìn)的算法不僅能較好地保留圖形特征，而且提高了壓縮精度。改進(jìn)后的Douglas-Peucker算法基本步驟為：

Step1：利用深度匹配搜索算法提取相鄰多邊形的公共點(diǎn)，并將其存入一個(gè)動(dòng)態(tài)數(shù)組；

Step2：調(diào)用加入徑向壓縮限差的Douglas-Peucker算法，對(duì)任意一個(gè)多邊形進(jìn)行化簡(jiǎn)；

Step3：求出曲線中垂向最大距離的點(diǎn)及其徑向最大距離并與給定的限差進(jìn)行比較，若均小于給定的垂向和徑向壓縮限差，則確定曲線上所有中間點(diǎn)為初步需要?jiǎng)h除的點(diǎn)集，并轉(zhuǎn)到下一步；反之，繼續(xù)進(jìn)行分段壓縮；

Step4：判斷初步確定的需要?jiǎng)h除的點(diǎn)集中的點(diǎn)是否在公共點(diǎn)數(shù)組中，若是，轉(zhuǎn)到下一步；若否，刪除相應(yīng)非公共點(diǎn)；

Step5：判斷篩選出的公共點(diǎn)是否已被標(biāo)記，若是，刪除該點(diǎn)，反之，在公共點(diǎn)數(shù)組中標(biāo)記該公共點(diǎn)。依次重復(fù)step2-5，直到所有點(diǎn)處理完成。

3 試驗(yàn)驗(yàn)證

本文采用一組矢量數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，選取垂向距離限差D=0.1，徑向距離限差R=1進(jìn)行算法實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如下：

圖1和圖2分別為采用Douglas-Peucker算法和本文的改進(jìn)算法后得到的局部放大圖。

從圖1和圖2比較可以看出，圖1出現(xiàn)了多處細(xì)縫，顯得較為粗糙；圖1中出現(xiàn)的失真現(xiàn)象在圖2中得到消除，并且圖形效果比圖1美觀。

4 結(jié)語

針對(duì)GIS中空間數(shù)據(jù)量大、無線通信網(wǎng)絡(luò)帶寬窄以及移動(dòng)終端設(shè)備硬件條件有限等特點(diǎn)，本文首先介紹傳統(tǒng)的Douglas-Peucker算法的基本思想，針對(duì)傳統(tǒng)的Douglas-Peucker算法中存在的不足進(jìn)行改進(jìn)。通過試驗(yàn)驗(yàn)證，改進(jìn)的算法在壓縮圖形的過程中能更好的保持圖形的特征，避免了失真現(xiàn)象，且在一定程度上控制了面積偏差，增加了壓縮精度

參考文獻(xiàn)

[1]郭慶勝.地圖自動(dòng)綜合理論與方法[M].北京：測(cè)繪出版社，2002.

[2]王立勝，閔曉瑜，畢妤.一種面向移動(dòng)用戶的空間矢量數(shù)據(jù)壓縮算法[J].自動(dòng)化技術(shù)與應(yīng)用，2004，23（12）：20-22.

[3]翟戰(zhàn)強(qiáng)，管華，王雙亨.一種快速空間矢量數(shù)據(jù)壓縮方法[J].計(jì)算機(jī)工程，2003，29（2）：94—95.