Instantly share code, notes, and snippets.

# rhyolight/rdp.js

Created May 31, 2012 20:32
Show Gist options
• Save rhyolight/2846020 to your computer and use it in GitHub Desktop.
Ramer-Douglas-Peucker line filtering algorithm in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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; }

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