Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Ramer-Douglas-Peucker line filtering algorithm in JavaScript
function findPerpendicularDistance(point, line) {
var pointX = point[0],
pointY = point[1],
lineStart = {
x: line[0][0],
y: line[0][1]
},
lineEnd = {
x: line[1][0],
y: line[1][1]
},
slope = (lineEnd.y - lineStart.y) / (lineEnd.x - lineStart.x),
intercept = lineStart.y - (slope * lineStart.x),
result;
result = Math.abs(slope * pointX - pointY + intercept) / Math.sqrt(Math.pow(slope, 2) + 1);
return result;
}
function douglasPeucker(points, epsilon) {
var i,
maxIndex = 0,
maxDistance = 0,
perpendicularDistance,
leftRecursiveResults, rightRecursiveResults,
filteredPoints;
// find the point with the maximum distance
for (i = 2; i < points.length - 1; i++) {
perpendicularDistance = findPerpendicularDistance(points[i], [points[1], points[points.length - 1]]);
if (perpendicularDistance > maxDistance) {
maxIndex = i;
maxDistance = perpendicularDistance;
}
}
// if max distance is greater than epsilon, recursively simplify
if (maxDistance >= epsilon) {
leftRecursiveResults = douglasPeucker(points.slice(1, maxIndex), epsilon);
rightRecursiveResults = douglasPeucker(points.slice(maxIndex), epsilon);
filteredPoints = leftRecursiveResults.concat(rightRecursiveResults);
} else {
filteredPoints = points;
}
return filteredPoints;
}
@rhyolight

This comment has been minimized.

Copy link
Owner Author

rhyolight commented May 31, 2012

@rjsteinert

This comment has been minimized.

Copy link

rjsteinert commented Jan 16, 2014

Nice! How's this working out for you?

@PaulGiletich

This comment has been minimized.

Copy link

PaulGiletich commented Feb 9, 2015

Aware! This is not correct version of algorithm, see http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm implementation in Matlab (keep in mind that arrays begin with 1 in matlab) for correct implementation. Lost entire working day fuguring out that this is not Ramer-Douglas-Peucker

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.