背景

老婆最近在准备面试，整理项目难点时对这个抽稀算法不理解。那我就得站出来了😀😀

抽稀算法

抽稀算法是指在保持数据尽可能不失真的前提下，减少数据的数量。路径规划中，抽稀算法减少路径点的数量，同时保留路径的形状特征。常见的抽稀算法有 Douglas-Peucker 算法。

Douglas-Peucker 算法原理如下；

1. 在曲线首尾两点虚连一条直线，计算其余各点到该直线的距离；
2. 选其最大者与阈值相比较，若小于阈值则将首尾之间的点全部舍去；
3. 否则以改点将已知曲线分为两部分，每部分从第 1 步开始重新处理；

求点到线的距离

结论：d=|Ax0+By0+C|/√(A²+B²)

我花了一上午才弄懂这个公式。请问 d=|Ax0+By0+C|/√(A²+B²) 是什么公式？从哪里推出的？

getD(point, point1, point2) {
    // 先两点式求得直线方程 (x-x1)/(x2-x1) = (y-y1)(y2-y1)，利用了等比定理
    // 然后展开 (y2-y1)x + (x1-x2)y + (x2y1-x1y2)  = 0
    // 最终要得到 Ax + By + c = 0 这种形式
    let m = (point2.y - point1.y) * point.x + (point1.x - point2.x) * point.y + (point2.x * point1.y - point1.x * point2.y);
    let n = Math.pow(point2.y - point1.y, 2) + Math.pow(point1.x - point2.x, 2);
    // 根据点到直线距离公式 d=|Ax0+By0+C|/√(A²+B²)
    return Math.abs(m) / Math.sqrt(n);
},

Douglas-Peucker（JS 版）

douglas(points, threshold) {
    // 距离首尾连线最远的点
    let index = 0, dmax = 0;
    for (let i = 1; i < points.length - 1; i++) {
        let point = points[i];
        let d = this.getD(point, points[0], points[points.length - 1]);
        if (d > dmax) {
            dmax = d;
            index = i;
        }
    }
    if (dmax < threshold) {
        // 舍弃首尾之间的所有点
        return [points[0], points[points.length - 1]];
    } else {
        // 以该点将该段曲线一分为二，每一部分重复上述过程(递归)
        let left = this.douglas(points.slice(0, index + 1), threshold);
        let right = this.douglas(points.slice(index, points.length), threshold);
        return left.slice(0, -1).concat(right);
    }
}

在线体验

点我点我>>