背景
在最近开发的某系统中，有一需求是在map上显示路径，并在路径上分段打箭头、点和文字信息（时间）。
测试环境（mock数据）理想效果
看起来还不错是吧
然鹅，但由于真实环境点位数据过于密集，导致显示效果十分魔幻，看起来是这样婶的。（害）
然后呢，突然想起来之前大学时侯做acm的一个路径拟合题和这个需求很类似，就在此分享一下吧（虽然好像这个算法是由后端实现）。
Ramer–Douglas–Peucker算法
1. 简介
Ramer–Douglas–Peucker算法，又称道格拉斯-普克算法算法或迭代端点拟合算法，是一种将由多点组成的曲线（折线）降采样为点数较小的类似曲线（折线）的算法。
2. 算法思想
起始曲线是一组有序的点或线，距离维度 ε（可以理解为拟合度） > 0。
该算法采用递归思想。最初，运算点集合为所有点。首先，拟合出第一个点和最后一个点的直线，计算当前运算集中所有点到这条直线的距离（循环），如果这个距离(d)<ε,那么可以将除了首尾的两个点以外的所有点去除,形成一个简单线段。否则，如果距离(d)>ε，这个点将被保留，并由此点将原有运算集划分为两个子集，并递归运算这个流程。
当递归完成后，可以生成一条新的输出曲线，该曲线由所有且仅由那些被标记为保留的点组成。
说了这些，有轻微阅读障碍的XDM估计已经躺下了（比如我），所以这里放上一张图来帮助理解。
3. 参数控制
ε(阈值)，越小，直线越平滑，越大，直线越锐利。
4. 伪代码
function 道格拉斯(运算点集, 阈值) {
// 找出两点间点的最大距离
最大距离 = 0;
距离最大点位置 = 0;
length = 运算集.length;
for (let i = 0; i < length - 1; i++) {
d = 计算点到直线距离(
运算点集[i],
拟合直线方程(运算点集[0], 运算点集[length - 1])
);
if (d > 最大距离) {
距离最大点位置 = i;
最大距离 = d;
}
}
结果输出 = [];
// 如果最大距离小于阈值,就拟合
if (最大距离 > 阈值) {
// 继续计算
左子集 = 道格拉斯(运算点集合.slice(0, 距离最大点位置), 阈值);
右子集 = 道格拉斯(运算点集.slice(距离最大点位置, length), 阈值);
结果输出 = 左子集.concat(右子集);
} else {
// 拟合
结果输出 = [运算点集[0], 运算点集[length - 1]];
}
return 结果输出;
}5.后记
- 算法复杂度O(n log n)
End
