Douglas-Peukcer算法由D.Douglas和T.Peueker于1973年提出，是線狀要素抽稀的經(jīng)典算法。用它處理大量冗余的幾何數(shù)據(jù)點(diǎn)，既可以達(dá)到數(shù)據(jù)量精簡(jiǎn)的目的，有可以在很大程度上保留幾何形狀的骨架。

算法的基本思路

將待處理曲線的首末點(diǎn)虛連一條直線,求所有中間點(diǎn)與直線的距離,并找出最大距離值dmax ,用dmax與抽稀閾值threshold相比較：

若dmax < threshold，這條曲線上的中間點(diǎn)全部舍去;

若dmax ≥ threshold，則以該點(diǎn)為界，把曲線分為兩部分,對(duì)這兩部分曲線重復(fù)上述過(guò)程，直至所有的點(diǎn)都被處理完成。

算法的遞歸實(shí)現(xiàn)

偽代碼：

然而有時(shí)候遞歸的層次太深的話會(huì)出現(xiàn)棧溢出的情況。在此，再介紹一種非遞歸的算法。

算法的非遞歸實(shí)現(xiàn)

本文轉(zhuǎn)自 https://zhuanlan.zhihu.com/p/74906781，如有侵權(quán)，請(qǐng)聯(lián)系刪除。