Instantly share code, notes, and snippets.

Created February 14, 2011 16:54
Star You must be signed in to star a gist
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; };

### aaronblohowiak commented May 11, 2011

what is the license on this???

### adammiller commented May 11, 2011

http://unlicense.org/ -- do what you want with it. I'd be stoked to know if someone used it though, and what they used it for.

### aaronblohowiak commented May 11, 2011

nice. i want to reduce the size of the data transmitted for a collaborative canvas app, so this should help.

### BonsaiDen commented Aug 3, 2011

Hey there! That was a great help :) Working on image outlining and plugging this in greatly reduced the resulting paths.

There's one bug though: in this.distanceToPoint, m might end up being Infinity, so a check is needed to get it back down to normal values, else the path is reduced to 2 points.

### ttopholm commented Aug 23, 2011

does the points and tolerance need to be in a specific definition like longitude latitude or in utm coords... or doesn't it matter

### adammiller commented Aug 23, 2011

Unit-agnostic. Just make sure your tolerance is relative to the variance in your point values.

### ttopholm commented Aug 23, 2011

Okay just to clarify, so if I provide it in longitude / latitude the tolerance should be in degrees, right....

so if i want the tolerance in meters, and the points in lat/lon, I should do this in your code..

``````band_sqr = tolerance * 360.0 / (2.0 * Math.PI * 6378137.0); /* Now in degrees */
band_sqr *= band_sqr;
``````

and band_sqr would be the degrees....

### adammiller commented Aug 23, 2011

Converting meters to lat/long is an entirely different topic which I don't know a ton about. The code is provided as is and expects tolerance and the points to be unit-less numbers. The project I wrote this code for used a fixed tolerance, which I tweaked until the results were satisfactory.

### stefanix commented May 14, 2012

Tried the snippet but was failing under certain edge conditions. Ended up using this which I ported from C++. It also uses some nifty convex hull speed optimizations. See http://softsurfer.com/Archive/algorithm_0205/algorithm_0205.htm :

```  var poly_simplify = function(V, tol) {
// V ... [[x1,y1],[x2,y2],...] polyline
// tol  ... approximation tolerance
// ==============================================
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.
// http://softsurfer.com/Archive/algorithm_0205/algorithm_0205.htm
var sum = function(u,v) {return [u[0]+v[0], u[1]+v[1]];}
var diff = function(u,v) {return [u[0]-v[0], u[1]-v[1]];}
var prod = function(u,v) {return [u[0]*v[0], u[1]*v[1]];}
var dot = function(u,v) {return u[0]*v[0] + u[1]*v[1];}
var norm2 = function(v) {return v[0]*v[0] + v[1]*v[1];}
var norm = function(v) {return Math.sqrt(norm2(v));}
var d2 = function(u,v) {return norm2(diff(u,v));}
var d = function(u,v) {return norm(diff(u,v));}

var simplifyDP = function( tol, v, j, k, mk ) {
//  This is the Douglas-Peucker recursive simplification routine
//  It just marks vertices that are part of the simplified polyline
//  for approximating the polyline subchain v[j] to v[k].
//  mk[] ... array of markers matching vertex array v[]
if (k <= j+1) { // there is nothing to simplify
return;
}
// check for adequate approximation by segment S from v[j] to v[k]
var maxi = j;          // index of vertex farthest from S
var maxd2 = 0;         // distance squared of farthest vertex
var tol2 = tol * tol;  // tolerance squared
S = [v[j], v[k]];  // segment from v[j] to v[k]
u = diff(S[1], S[0]);   // segment direction vector
var cu = norm2(u,u);     // segment length squared
// test each vertex v[i] for max distance from S
// compute using the Feb 2001 Algorithm's dist_Point_to_Segment()
// Note: this works in any dimension (2D, 3D, ...)
var  w;           // vector
var Pb;                // point, base of perpendicular from v[i] to S
var b, cw, dv2;        // dv2 = distance v[i] to S squared
for (var i=j+1; i<k; i++) {
// compute distance squared
w = diff(v[i], S[0]);
cw = dot(w,u);
if ( cw <= 0 ) {
dv2 = d2(v[i], S[0]);
} else if ( cu <= cw ) {
dv2 = d2(v[i], S[1]);
} else {
b = cw / cu;
Pb = [S[0][0]+b*u[0], S[0][1]+b*u[1]];
dv2 = d2(v[i], Pb);
}
// test with current max distance squared
if (dv2 <= maxd2) {
continue;
}
// v[i] is a new max vertex
maxi = i;
maxd2 = dv2;
}
if (maxd2 > tol2) {      // error is worse than the tolerance
// split the polyline at the farthest vertex from S
mk[maxi] = 1;      // mark v[maxi] for the simplified polyline
// recursively simplify the two subpolylines at v[maxi]
simplifyDP( tol, v, j, maxi, mk );  // polyline v[j] to v[maxi]
simplifyDP( tol, v, maxi, k, mk );  // polyline v[maxi] to v[k]
}
// else the approximation is OK, so ignore intermediate vertices
return;
}

var n = V.length;
var sV = [];
var i, k, m, pv;               // misc counters
var tol2 = tol * tol;          // tolerance squared
vt = [];                       // vertex buffer, points
mk = [];                       // marker buffer, ints

// STAGE 1.  Vertex Reduction within tolerance of prior vertex cluster
vt[0] = V[0];              // start at the beginning
for (i=k=1, pv=0; i<n; i++) {
if (d2(V[i], V[pv]) < tol2) {
continue;
}
vt[k++] = V[i];
pv = i;
}
if (pv < n-1) {
vt[k++] = V[n-1];      // finish at the end
}

// STAGE 2.  Douglas-Peucker polyline simplification
mk[0] = mk[k-1] = 1;       // mark the first and last vertices
simplifyDP( tol, vt, 0, k-1, mk );

// copy marked vertices to the output simplified polyline
for (i=m=0; i<k; i++) {
if (mk[i]) {
sV[m++] = vt[i];
}
}
return sV;
}```

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

### lizandrolm commented Feb 24, 2017 • edited

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