Created
February 14, 2011 16:54
-
-
Save adammiller/826148 to your computer and use it in GitHub Desktop.
Javascript implementation of the Douglas Peucker path simplification algorithm
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
var simplifyPath = function( points, tolerance ) { | |
// helper classes | |
var Vector = function( x, y ) { | |
this.x = x; | |
this.y = y; | |
}; | |
var Line = function( p1, p2 ) { | |
this.p1 = p1; | |
this.p2 = p2; | |
this.distanceToPoint = function( point ) { | |
// slope | |
var m = ( this.p2.y - this.p1.y ) / ( this.p2.x - this.p1.x ), | |
// y offset | |
b = this.p1.y - ( m * this.p1.x ), | |
d = []; | |
// distance to the linear equation | |
d.push( Math.abs( point.y - ( m * point.x ) - b ) / Math.sqrt( Math.pow( m, 2 ) + 1 ) ); | |
// distance to p1 | |
d.push( Math.sqrt( Math.pow( ( point.x - this.p1.x ), 2 ) + Math.pow( ( point.y - this.p1.y ), 2 ) ) ); | |
// distance to p2 | |
d.push( Math.sqrt( Math.pow( ( point.x - this.p2.x ), 2 ) + Math.pow( ( point.y - this.p2.y ), 2 ) ) ); | |
// return the smallest distance | |
return d.sort( function( a, b ) { | |
return ( a - b ); //causes an array to be sorted numerically and ascending | |
} )[0]; | |
}; | |
}; | |
var douglasPeucker = function( points, tolerance ) { | |
if ( points.length <= 2 ) { | |
return [points[0]]; | |
} | |
var returnPoints = [], | |
// make line from start to end | |
line = new Line( points[0], points[points.length - 1] ), | |
// find the largest distance from intermediate poitns to this line | |
maxDistance = 0, | |
maxDistanceIndex = 0, | |
p; | |
for( var i = 1; i <= points.length - 2; i++ ) { | |
var distance = line.distanceToPoint( points[ i ] ); | |
if( distance > maxDistance ) { | |
maxDistance = distance; | |
maxDistanceIndex = i; | |
} | |
} | |
// check if the max distance is greater than our tollerance allows | |
if ( maxDistance >= tolerance ) { | |
p = points[maxDistanceIndex]; | |
line.distanceToPoint( p, true ); | |
// include this point in the output | |
returnPoints = returnPoints.concat( douglasPeucker( points.slice( 0, maxDistanceIndex + 1 ), tolerance ) ); | |
// returnPoints.push( points[maxDistanceIndex] ); | |
returnPoints = returnPoints.concat( douglasPeucker( points.slice( maxDistanceIndex, points.length ), tolerance ) ); | |
} else { | |
// ditching this point | |
p = points[maxDistanceIndex]; | |
line.distanceToPoint( p, true ); | |
returnPoints = [points[0]]; | |
} | |
return returnPoints; | |
}; | |
var arr = douglasPeucker( points, tolerance ); | |
// always have to push the very last point on so it doesn't get left off | |
arr.push( points[points.length - 1 ] ); | |
return arr; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
same question as zhengyifan
it seems these lines do nothing?
line.distanceToPoint( p, true ); // line no 53
line.distanceToPoint( p, true ); // line no 61