【青鸟飞扬教育】曲线点抽稀算法 - Python 实现

何为抽稀

在处理矢量化数据时，记录中往往会有很多重复数据，对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间，另一方面造成所要表达的图形不光滑或不符合标准。因此要通过某种规则，在保证矢量曲线形状不变的情况下， 最大限度地减少数据点个数，这个过程称为抽稀。

通俗的讲就是对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且能够在一定程度保持原有形状。比较常用的两种抽稀算法是：道格拉斯 - 普克 (Douglas-Peuker) 算法和垂距限值法。

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

Douglas-Peuker 算法 (DP 算法) 过程如下:

• 1、连接曲线首尾两点 A、B；
• 2、依次计算曲线上所有点到 A、B 两点所在曲线的距离；
• 3、计算最大距离 D，如果 D 小于阈值 threshold, 则去掉曲线上出 A、B 外的所有点；如果 D 大于阈值 threshold, 则把曲线以最大距离分割成两段；
• 4、对所有曲线分段重复 1-3 步骤，知道所有 D 均小于阈值。即完成抽稀。

这种算法的抽稀精度与阈值有很大关系，阈值越大，简化程度越大，点减少的越多；反之简化程度越低，点保留的越多，形状也越趋于原曲线。

垂距限值法

垂距限值法其实和 DP 算法原理一样，但是垂距限值不是从整体角度考虑，而是依次扫描每一个点，检查是否符合要求。

算法过程如下:

• 1、以第二个点开始，计算第二个点到前一个点和后一个点所在直线的距离 d；
• 2、如果 d 大于阈值，则保留第二个点，计算第三个点到第二个点和第四个点所在直线的距离 d; 若 d 小于阈值则舍弃第二个点，计算第三个点到第一个点和第四个点所在直线的距离 d;
• 3、依次类推，直线曲线上倒数第二个点。
• 最后
• 其实 DP 算法和垂距限值法原理一样，DP 算法是从整体上考虑一条完整的曲线，实现时较垂距限值法复杂，但垂距限值法可能会在某些情况下导致局部最优。另外在实际使用中发现采用点到另外两点所在直线距离的方法来判断偏离，在曲线弧度比较大的情况下比较准确。如果在曲线弧度比较小，弯曲程度不明显时，这种方法抽稀效果不是很理想，建议使用三点所围成的三角形面积作为判断标准。