Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
};
@aaronblohowiak

This comment has been minimized.

Copy link

aaronblohowiak commented May 11, 2011

what is the license on this???

@adammiller

This comment has been minimized.

Copy link
Owner Author

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link
Owner Author

adammiller commented Aug 23, 2011

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

@ttopholm

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link
Owner Author

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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.

See: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment

@zhengyifan

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

lizandrolm commented Feb 24, 2017

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.