d3.js How to simplify a complex path - using a custom algorithm

Question

I've got a very basic example here. http://jsfiddle.net/jEfsh/57/ that creates a complex path - with lots of points. I've read up on an algorithm that may look over the points and create a simpler set of coordinates. Does anyone have any experience with this - examples on how to loop through the path data and pass it through the algorithm - find the shortest set of points to create a more rudimentary version of the shape?

http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

var points = "M241,59L237,60L233,60L228,61L224,61L218,63L213,63L209,65L204,66L199,67L196,68L193,69L189,70L187,72L184,72L182,74L179,75L177,76L175,78L173,79L170,81L168,83L165,85L163,87L161,89L159,92L157,95L157,97L155,102L153,105L152,110L151,113L151,117L151,123L150,137L148,180L148,185L148,189L148,193L148,197L148,202L148,206L149,212L151,218L152,222L154,229L154,232L155,235L157,239L158,241L160,245L162,247L163,249L165,251L167,254L169,256L172,258L175,260L178,261L183,265L188,268L193,270L206,273L213,275L220,275L225,275L232,276L238,277L243,277L249,277L253,277L259,277L266,277L271,277L277,277L281,277L284,277L288,277L293,277L297,276L302,274L305,272L308,271L311,268L313,267L315,264L318,261L322,257L324,254L326,249L329,244L331,241L332,239L334,234L338,230L339,226L341,222L343,218L345,213L347,211L348,207L349,201L351,196L352,192L353,187L353,183L353,180L353,178L354,176L354,173L354,170L354,168L354,167L354,166L354,164L354,162L354,161L354,159L354,158L354,155L354,152L354,149L352,143L349,137L347,133L343,125L340,119 M241,59L340,119";

d3.select("#g-1").append("path").attr("d", points);


//simplify the path

function DouglasPeucker(){

}



/*
//http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm


function DouglasPeucker(PointList[], epsilon)
    // Find the point with the maximum distance
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to ( end - 1) {
        d = shortestDistanceToSegment(PointList[i], Line(PointList[1], PointList[end])) 
        if ( d > dmax ) {
            index = i
            dmax = d
        }
    }
    // If max distance is greater than epsilon, recursively simplify
    if ( dmax > epsilon ) {
        // Recursive call
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

        // Build the result list
        ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    // Return the result
    return ResultList[]
end
*/

Answer 1

It's not clear what your problem is exactly. Do you have problems to turn the SVG data string into a list of points? You can use this:

function path_from_svg(svg) {
    var pts = svg.split(/[ML]/);
    var path = [];

    console.log(pts.length);
    for (var i = 1; i < pts.length; i++) {
        path.push(pts[i].split(","));
    }

    return path;
}

It is a very simple approach: It splits the string on all move (M) and line (L) commands and treats them as lines. It then splits all substrings on the comma. The first "substring" is ignored, because it is the empty string before the first M. If there is a way to do this better in d3 I haven't found it.

The reverse operation is easier:

function svg_to_path(path) {
    return "M" + path.join("L");
}

This is equivalent to svg.line.interpolate("linear").

You can then implement the Douglas-Peucker algorithm on this path data recursively:

function path_simplify_r(path, first, last, eps) {
    if (first >= last - 1) return [path[first]];

    var px = path[first][0];
    var py = path[first][1];

    var dx = path[last][0] - px;
    var dy = path[last][1] - py;

    var nn = Math.sqrt(dx*dx + dy*dy);
    var nx = -dy / nn;
    var ny = dx / nn;

    var ii = first;
    var max = -1;

    for (var i = first + 1; i < last; i++) {
        var p = path[i];

        var qx = p[0] - px;
        var qy = p[1] - py;

        var d = Math.abs(qx * nx + qy * ny);
        if (d > max) {
            max = d;
            ii = i;
        }
    }

    if (max < eps) return [path[first]];

    var p1 = path_simplify_r(path, first, ii, eps);
    var p2 = path_simplify_r(path, ii, last, eps);

    return p1.concat(p2);        
}

function path_simplify(path, eps) {
    var p = path_simplify_r(path, 0, path.length - 1, eps);
    return p.concat([path[path.length - 1]]);
}

The distance to the line is not calculated in a separate function but directly with the formula for the distance of a point to a 2d line from the normal {nx, ny} on the line vector {dx, dy} between the first and last point. The normal is normalised, nx*nx + ny*ny == 1.

When creating the paths, only the first point is added, the last point path[last] is implied and must be added in path_simplify, which is a front end to the recursive function path_simplify_r. This approach was chosen so that concatenating the left and right subpaths does not create a duplicate point in the middle. (This could equally well and maybe cleaner be done by joining p1 and p2.slice(1).)

Here's everything put together in a fiddle: http://jsfiddle.net/Cbk9J/3/

Answer 2

Lots of good references in the comments to this question -- alas they are comments and not suggested answers which can be truly voted on.

http://bost.ocks.org/mike/simplify/

shows interactive use of this kind of thing which references Douglas-Peucker but also Visvalingam.