Skip to content

Instantly share code, notes, and snippets.

@adammiller
Created February 14, 2011 16:54
Show Gist options
  • Star 52 You must be signed in to star a gist
  • Fork 11 You must be signed in to fork a gist
  • Save adammiller/826148 to your computer and use it in GitHub Desktop.
Save adammiller/826148 to your computer and use it in GitHub Desktop.
Javascript implementation of the Douglas Peucker path simplification algorithm
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;
};
@abiv23
Copy link

abiv23 commented Nov 8, 2022

same question as zhengyifan

it seems these lines do nothing?

line.distanceToPoint( p, true ); // line no 53
line.distanceToPoint( p, true ); // line no 61

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment