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/

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.

©2020 All rights reserved.