道格拉斯-普克算法 Douglas-Peucker Algorithm 简称 D-P 算法，亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法，是将曲线近似表示为一系列点，并减少点的数量的一种算法。该算法的原始类型分别由乌尔斯·拉默于1972年以及大卫·道格拉斯和托马斯·普克于1973年提出，并在之后的数十年中由其他学者予以完善。

D-P 算法是公认的线状要素化简经典算法。现有的线化简算法中，有相当一部分都是在该算法基础上进行改进产生的。用来对大量冗余的图形数据点进行压缩以提取必要的数据点，它是一个整体算法，具有平移和旋转不变性，可保留较大弯曲形态上的特征点。且在给定曲线与阈值后，抽样结果一定。

保留了较大弯曲形态上的特征点：

经典的 D-P 算法描述如下【红色部分用于辅助理解 可忽略】：

1. 连接当前矢量曲线首尾点a、b，该直线AB为当前矢量曲线的弦；
2. 计算首尾点a、b间所有坐标点到该弦AB的距离，并获取最大距离d及其的坐标点c；
3. 比较最大距离d与给定的阈值thresholdVal，小于阈值，当前弦AB可作为曲线的近似【首尾间的坐标点将被抽稀】，该段矢量曲线处理完毕。
4. 大于阈值，使用最大距离坐标点c分割当前矢量曲线，分割后的两段矢量曲线分别使用1~3的流程进行处理。
5. 全部处理完毕后，依次连接各个分割点形成的折线，即可以作为整个曲线的近似。

示意图如下：

2.源码分享

2.1 公式

点

M

(

x

0

,

y

0

)

M(x_{0},y_{0})

M(x0​,y0​) 是平面上的一个点，它到直线

A

x

B

y

C

=

0

Ax+By+C=0

Ax+By+C=0 的距离 d 为：

d

=

∣

A

x

0

B

y

0

C

∣

A

2

B

2

d= \frac{|Ax_{0}+By_{0}+C|}{ \sqrt{A^{2}+B{2}}}

d=A2+B2

​∣Ax0​+By0​+C∣​

2.2 源码

一下是优化前的代码，优化后的代码请查看《道格拉斯-普克 Douglas-Peucker 抽稀算法近1000倍的速度提升》两个对象封装类【为了简洁注解未使用DOC规范】：

// 类1 坐标数据封装
@Data
@NoArgsConstructor
@AllArgsConstructor
public class PointData {
    // 标记是否删除（0保留 1删除）
    private int isDelete;
	// 数据点的经度
    private double longitudeEx;
    // 数据点的纬度
    private double latitudeEx;
}

// 类2 点INDEX及到线距离封装
@Data
@NoArgsConstructor
@AllArgsConstructor
@Builder
public class DistanceData {
    // 当前点的 INDEX 值
    private int index;
    // 当前点到直线的距离值
    private double distance;
}



### 给大家的福利


**零基础入门**


对于从来没有接触过网络安全的同学，我们帮你准备了详细的学习成长路线图。可以说是最科学最系统的学习路线，大家跟着这个大的方向学习准没问题。


![](https://img-blog.csdnimg.cn/img_convert/95608e9062782d28f4f04f821405d99a.png)


同时每个成长路线对应的板块都有配套的视频提供：


![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/a91b9e8100834e9291cfcf1695d8cd42.png#pic_center)


因篇幅有限，仅展示部分资料


网络安全面试题


![](https://img-blog.csdnimg.cn/img_convert/80674985176a4889f7bb130756893764.png)


绿盟护网行动


![](https://img-blog.csdnimg.cn/img_convert/9f3395407120bb0e1b5bf17bb6b6c743.png)


还有大家最喜欢的黑客技术


![](https://img-blog.csdnimg.cn/img_convert/5912337446dee53639406fead3d3f03c.jpeg)


**网络安全源码合集+工具包**


![](https://img-blog.csdnimg.cn/img_convert/5072ce807750c7ec721c2501c29cb7d5.png)


![](https://img-blog.csdnimg.cn/img_convert/4a5f4281817dc4613353c120c9543810.png)

**所有资料共282G**，朋友们如果有需要全套《网络安全入门+黑客进阶学习资源包》，可以扫描下方二维码领取（如遇扫码问题，可以在评论区留言领取哦）~




**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**

**[需要这份系统化资料的朋友，可以点击这里获取](https://bbs.csdn.net/topics/618540462)**


**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**