Instantly share code, notes, and snippets.

Created February 14, 2011 16:54
Show Gist options
• 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; };

### Humppakarajat commented May 13, 2013

Code to simplify a google maps api v3 Polyline based on the douglasPeucker.js snippet:

```google.maps.Polyline.prototype.simplifyLine = function(tolerance){
var res = null;

if(this.getPath() && this.getPath().getLength()){
var points = this.getPath().getArray();

var Line = function( p1, p2 ) {
this.p1 = p1;
this.p2 = p2;

this.distanceToPoint = function( point ) {
// slope
var m = ( this.p2.lat() - this.p1.lat() ) / ( this.p2.lng() - this.p1.lng() ),
// y offset
b = this.p1.lat() - ( m * this.p1.lng() ),
d = [];
// distance to the linear equation
d.push( Math.abs( point.lat() - ( m * point.lng() ) - b ) / Math.sqrt( Math.pow( m, 2 ) + 1 ) );
// distance to p1
d.push( Math.sqrt( Math.pow( ( point.lng() - this.p1.lng() ), 2 ) + Math.pow( ( point.lat() - this.p1.lat() ), 2 ) ) );
// distance to p2
d.push( Math.sqrt( Math.pow( ( point.lng() - this.p2.lng() ), 2 ) + Math.pow( ( point.lat() - this.p2.lat() ), 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;
};
res = douglasPeucker( points, tolerance );
// always have to push the very last point on so it doesn't get left off
res.push( points[points.length - 1 ] );
}
return res;
};```

Usage:

```var pl = new google.maps.Polyline({...});
var simplifiedLinePath = pl.simplifyLine(0.00045);
var simplifiedLine = new google.maps.Polyline({map: gmap, path: simplifiedLinePath});```

### payne92 commented Nov 29, 2013

I believe the distanceToPoint() function is flawed, which may be a source of problems. If you are testing a point that's near the supporting line, but far away from the segment, you'll return an incorrectly small distance. This may cause points to be omitted that shouldn't be.

### zhengyifan commented Aug 7, 2014

Hi, I do not understand the functionality in the below Code snippets, can you explain it? thanks a lot.

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

### maboiteaspam commented Aug 14, 2015

Using it to reduce path complexity after i created gestures with https://github.com/uwdata/gestrec

I hope it works, i m such in a hurry.. Thanks for sharing anyway !

The algorithm of Douglas Peucker must be analyzed / improved in Language R, Here I detail the tools that I use. I am using the following tools:

QGIS: Here I have uploaded an OSM map of California. And get the semantic information.
PostgreSQL: Here the stored paths (Latitude and Longitude)
Language R: Here we must do the manipulation of the RDP algorithm
Has anyone done any similar project?

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