d3.js如何简化复杂路径 - 使用自定义算法 [英] d3.js How to simplify a complex path - using a custom algorithm
问题描述
这里有一个非常基本的例子。 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）
//简化路径
函数DouglasPeucker（）{
}
/ *
//http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
函数DouglasPeucker（PointList []，epsilon ）
//找到具有最大距离的点
dmax = 0
index = 0
end = length（PointList）
for i = 2 to（end- 1）{
d = recentDistanceToSegment（PointList [i]，Line（PointList [1]，PointList [end]））
if（d> dmax）{
index = i
dmax = d
}
}
//如果最大距离大于εilon，则递归简化
if（dmax>εilon）{
//递归调用
recResults1 [] = DouglasPeucker（PointList [1 ... index]，epsilon）
recResults2 [] = DouglasPeucker（PointList [index ... end]，epsilon）
//构建结果列表
ResultList [] = {recResults1 [1 ... end-1] recResults2 [1 ... end]}
} else {
ResultList [] = { PointList [1]，PointList [end]}
}
//返回结果
return ResultList []
end
* /
这不清楚你的问题是什么。将SVG数据字符串转换为点列表有问题吗？您可以使用：
函数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（，））;
}
返回路径;
}
这是一个非常简单的方法： code> M ）和行（ L ）命令，并将它们视为行。然后它拆分逗号上的所有子字符串。第一个substring被忽略，因为它是第一个 M 之前的空字符串。如果在 d3 中有更好的方法，我还没有找到它。
更容易：
function svg_to_path（path）{
returnM+ 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
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
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]]）;
}
到线的距离不是在单独的函数中计算，公式为从线上向量 {dx，dy} {nx，ny} c $ c>在第一点和最后一点之间。正常是标准化的， nx * nx + ny * ny == 1 。
第一个点被添加，最后一个点 path [last] 是隐含的，必须添加在 path_simplify 前端到递归函数 path_simplify_r 。选择此方法，以便连接左和右子路径不会在中间创建重复点。 （这可以通过加入 p1 和 p2.slice（1）来完成。 p>
这里是摆在一个小提琴的一切： http：// jsfiddle .net / Cbk9J / 3 /
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
*/
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/
这篇关于d3.js如何简化复杂路径 - 使用自定义算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
