Instantly share code, notes, and snippets.

# rhyolight/rdp.js Created May 31, 2012

Ramer-Douglas-Peucker line filtering algorithm in JavaScript
 function findPerpendicularDistance(point, line) { var pointX = point, pointY = point, lineStart = { x: line, y: line }, lineEnd = { x: line, y: line }, 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, 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; }
Owner Author

### rjsteinert commented Jan 16, 2014

 Nice! How's this working out for you?

### 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