抽稀

在處理矢量化數據時,記錄中往往會有很多重複數據,對進一步數據處理帶來諸多不便。多餘的數據一方面浪費了較多的存儲空間,另一方面造成所要表達的圖形不光滑或不符合標準。因此要通過某種規則,在保證矢量曲線形狀不變的情況下, 最大限度地減少數據點個數,這個過程稱為抽稀。

基本概念

數據經過抽稀後,數量大量減少,並且基本保證能反映原圖形或曲線的基本形狀特徵,能夠為進一步的處理節省空間和時間。

抽稀在GIS矢量數據處理,圖形數據壓縮處理中有廣泛的套用。

算法介紹

曲線抽稀的關鍵是定義抽稀因子,抽稀因子的不同決定的抽稀算法的多樣性,在現有抽稀理論中,有按步長,線段長度,垂距等來定義抽稀因子。

步長法

步長法是沿連續曲線每隔一定的步長抽取一點,其餘點全部壓縮掉,然後在相鄰抽取點間用直線連續或曲線擬合逼近。這種方法主要有兩點不足:一,曲線上的特徵點,如曲線拐彎處,曲線變化較大的點可能因抽稀被壓縮掉,導致曲線變形;二,在某些情況下,仍會留下部分多餘點無法刪除,如曲線中有一段比較直,而步長又較小,會導致此段直線上有多個抽取點,而實際上只要保留直線段的首尾點即可。因此,抽取後的曲線與原曲線有一定的誤差,誤差大小與步長的設定及曲線擬合方法有關。如果能綜合考慮步長和曲率,可能會有更好的效果,但目前對步長和曲率沒有明確的規定,一般是由編程人員根據實際情況自行決定。

線段過濾法

線段過濾法是指當某一段的長度小於某一過濾值時,就以該段的中點代替該段,如同此段的兩端退化到中點一樣。線段過濾法同步長法一樣,過濾值的大小決定著抽稀算法的精度,一般也是由編程人員自行確定。

道格拉斯-普克(Douglas-Peuker)算法

Douglas-Peuker算法 (DP算法))一般從整體角度來考慮一條完整的曲線或一段確定的線段,其基本思路為:

1)對曲線的首末點虛連一條直線,求曲線上所有點與直線的距離,並找出最大距離值dmax,用dmax與事先給定的閾值D相比:

2)若dmax<D,則將這條曲線上的中間點全部捨去;

若dmax≥D,保留dmax對應的坐標點,並以該點為界,把曲線分為兩部分,對這兩部分重複使用該方法,即重複1),2)步,直到所有dmax均<D,即完成對曲線的抽稀。

顯然,本算法的抽稀精度也與閾值相關,閾值越大,簡化程度越大,點減少的越多,反之,化簡程度越低,點保留的越多,形狀也越趨於原曲線。

DP算法的抽稀精度與上兩種方法相比,有明顯提高,一因其閾值一般取相應地物最大允許誤差,二因算法能做到在刪除與保留之間達到較好的平衡,即能充分減少點的數量,又能儘量保留特徵點,但由於在編程實現時要用到循環或遞歸,當點數很多時,效率會受到影響。

垂距限值法

垂距限值法與DP算法原理一樣,但其並非從整體角度考慮一條完整曲線,而是從第一點開始依次篩選,去除冗餘點。即以第一點為起點,計算第二點至第一點和第三點連線的垂直距離,若此距離大於某閾值,則保留第二點,並將其作為新起點,計算第三點至第二點和第四點連線的距離;否則,去除第二點,計算第三點至第一點和第四點連線距離,依次類推,直至曲線上最後一點。其閾值一般取相應地物最大允許誤差或更小 。

垂距限值法抽稀精度與DP算法一樣,但循環簡單,易於編程處理。是一種較理想的抽稀算法。

相關詞條

相關搜尋

熱門詞條

聯絡我們