道格拉斯-普克算法
道格拉斯-普克算法(Douglas–Peucker algorithm,亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法)是将曲线近似表示为一系列点,并减少点的数量的一种算法。该算法的原始类型分别由乌尔斯·拉默(Urs Ramer)于1972年以及大卫·道格拉斯(David Douglas)和托马斯·普克(Thomas Peucker)于1973年提出,并在之后的数十年中由其他学者予以完善。
算法使用二分查找方式
具体判断一个点是否抽稀掉的方式是 连线两点,求中间点和这个直线的距离,小于阈值的抽吸掉。
具体如下
第一步,连线AH,得到距离最大的点是D,距离小于阈值的点事FG,需要抽稀掉
第二步,连线AD,得到距离最大的点是DH ,每段分别重复上述步骤,直到抽吸完两点间没有其他点。