Douglas-Peucker演算法

NO IMAGE

 

Douglas-Peucker演算法(該演算法名字夠嚇人,其實思想很簡單)

在數字化時,要對曲線進行取樣,即在曲線上取有限個點,將其變為折線,並且能夠在一定程度

上保持原有的形狀。

經典的Douglas-Peucker演算法步驟如下:

(1)在曲線首尾兩點A,B之間連線一條直線AB,該直線為曲線的弦;

(2)得到曲線上離該直線段距離最大的點C,計算其與AB的距離d;

(3)比較該距離與預先給定的閾值threshold的大小,如果小於threshold,則該直線段作為曲線的近似,該段曲線處理完畢。

(4)如果距離大於閾值,則用C將曲線分為兩段AC和BC,並分別對兩段取信進行1~3的處理。

(5)當所有曲線都處理完畢時,依次連線各個分割點形成的折線,即可以作為曲線的近似。