Ramer-Douglas-Peucker implementation

rdp.ts

interface Point {
    x: number;
    y: number;
}

/**
 * Compute the perpendicular distance between a point and a line
 * @param point
 * @param line
 */
const perpendicularDistance = (point: Point, line: [Point, Point]) => {
    const x0 = point.x;
    const y0 = point.y;
    const x1 = line[0].x;
    const y1 = line[0].y;
    const x2 = line[1].x;
    const y2 = line[1].y;

    const y2y1 = y2 - y1;
    const x2x1 = x2 - x1;

    if (x1 === x2 && y1 === y2) {
        return Math.sqrt((y1 - y0) ** 2 + (x1 - x0) ** 2);
    } else {
        return (
            Math.abs(y2y1 * x0 - x2x1 * y0 + x2 * y1 - y2 * x1) / Math.sqrt(y2y1 ** 2 + x2x1 ** 2)
        );
    }
};

//
/**
 * Ramer-Douglas-Peucker
 * Algorithm for reducing the number of points in a curve that is approximated by a series of points
 *
 * @param points
 * @param epsilon
 * @link https://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
 */
export const simplifyPolylines = (points: Point[], epsilon: number): Point[] => {
    let dmax = 0;
    let index = 0;
    let end = points.length - 1;

    for (let i = 1; i < end - 1; i++) {
        const d = perpendicularDistance(points[i], [points[0], points[end]]);

        if (d > dmax) {
            index = i;
            dmax = d;
        }
    }

    if (dmax > epsilon) {
        const resultLeft = simplifyPolylines(points.slice(0, index + 1), epsilon);
        const resultRight = simplifyPolylines(points.slice(index), epsilon);

        return ([] as Point[]).concat(resultLeft.slice(0, resultLeft.length - 1), resultRight);
    } else {
        return [points[0], points[end]];
    }
};