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/