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; };

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