Created
May 31, 2012 20:32
-
-
Save rhyolight/2846020 to your computer and use it in GitHub Desktop.
Ramer-Douglas-Peucker line filtering algorithm in JavaScript
This file contains hidden or 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; | |
} |
Nice! How's this working out for you?
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
Ramer-Douglas-Peucker