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

Douglas-Peukcer算法由D.Douglas和T.Peueker于1973年提出，是线状要素抽稀的经典算法。用它处理大量冗余的几何数据点，既可以达到数据量精简的目的，有可以在很大程度上保留几何形状的骨架。

算法的基本思路

将待处理曲线的首末点虚连一条直线,求所有中间点与直线的距离,并找出最大距离值dmax ,用dmax与抽稀阈值threshold相比较：

若dmax < threshold，这条曲线上的中间点全部舍去;

若dmax ≥ threshold，则以该点为界，把曲线分为两部分,对这两部分曲线重复上述过程，直至所有的点都被处理完成。

算法的递归实现

伪代码：

然而有时候递归的层次太深的话会出现栈溢出的情况。在此，再介绍一种非递归的算法。

算法的非递归实现

本文转自 https://zhuanlan.zhihu.com/p/74906781，如有侵权，请联系删除。