Javascript implementation of the Douglas Peucker path simplification algorithm

douglasPeucker.js

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

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

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

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

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?

same question as zhengyifan

it seems these lines do nothing?

line.distanceToPoint( p, true ); // line no 53
line.distanceToPoint( p, true ); // line no 61