javascript - d3.js 如何简化复杂路径 - 使用自定义算法

Question

我这里有一个非常基本的例子。 http://jsfiddle.net/jEfsh/57/这会创建一条复杂的路径 - 有很多点。我已经阅读了一种算法，该算法可以查看这些点并创建一组更简单的坐标。有没有人对此有任何经验 - 关于如何遍历路径数据并将其传递给算法的示例 - 找到最短的点集以创建更基本的形状版本？

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

不清楚您的问题到底是什么。您在将 SVG 数据字符串转换为点列表时遇到问题吗？你可以使用这个:

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;
}

这是一种非常简单的方法:它在所有移动 (M) 和行 (L) 命令上拆分字符串并将它们视为行。然后它拆分逗号上的所有子字符串。第一个“子字符串”被忽略，因为它是第一个 M 之前的空字符串。如果有办法在 d3 中做得更好，我还没有找到。

逆向操作更简单:

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

这等同于 svg.line.interpolate("linear")。

然后您可以递归地在此路径数据上实现 Douglas-Peucker 算法:

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]]);
}

到直线的距离不是在单独的函数中计算的，而是直接用直线向量上的点到二维直线距离的公式 {nx, ny} {dx, dy} 第一个点和最后一个点之间。法线已归一化，nx*nx + ny*ny == 1。

创建路径时，只添加第一个点，最后一个点path[last]是隐含的，必须在path_simplify中添加，这是一个前端到递归函数 path_simplify_r。选择这种方法是为了连接左右子路径不会在中间创建重复点。 (这同样可以通过加入 p1 和 p2.slice(1) 来完成，也许更干净。)

这里是所有东西放在一起的 fiddle :http://jsfiddle.net/Cbk9J/3/