Skip to content

Instantly share code, notes, and snippets.

@adammiller
Created February 14, 2011 16:54
  • Star 52 You must be signed in to star a gist
  • Fork 11 You must be signed in to fork a gist
Star You must be signed in to star a gist
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;
};
@aaronblohowiak
Copy link

what is the license on this???

@adammiller
Copy link
Author

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
Copy link

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

@BonsaiDen
Copy link

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
Copy link

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
Copy link
Author

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

@ttopholm
Copy link

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
Copy link
Author

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
Copy link

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
Copy link

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
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
Copy link

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
Copy link

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

@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