{{ message }}

Instantly share code, notes, and snippets.

Created Feb 14, 2011
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 } ); }; }; var douglasPeucker = function( points, tolerance ) { if ( points.length <= 2 ) { return [points]; } var returnPoints = [], // make line from start to end line = new Line( points, 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]; } 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 // ============================================== // Copyright 2002, softSurfer (www.softsurfer.com) // 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+v, u+v];} var diff = function(u,v) {return [u-v, u-v];} var prod = function(u,v) {return [u*v, u*v];} var dot = function(u,v) {return u*v + u*v;} var norm2 = function(v) {return v*v + v*v;} 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, S); // 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 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 = V; // start at the beginning for (i=k=1, pv=0; i

### 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 } ); }; }; var douglasPeucker = function( points, tolerance ) { if ( points.length <= 2 ) { return [points]; } var returnPoints = [], // make line from start to end line = new Line( points, 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]; } 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

 @adammiller 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?