JavaScript: Simplification libraries

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

mourner_simplify.js

/*
 Copyright (c) 2013, Vladimir Agafonkin
 Simplify.js is a high-performance JS polyline simplification library
 mourner.github.io/simplify-js
*/

(function (global, undefined) {

	"use strict";


	// to suit your point format, run search/replace for '.x' and '.y';
	// to switch to 3D, uncomment the lines in the next 2 functions
	// (configurability would draw significant performance overhead)


	function getSquareDistance(p1, p2) { // square distance between 2 points

		var dx = p1.x - p2.x,
	//	    dz = p1.z - p2.z,
		    dy = p1.y - p2.y;

		return dx * dx +
	//	       dz * dz +
		       dy * dy;
	}

	function getSquareSegmentDistance(p, p1, p2) { // square distance from a point to a segment

		var x = p1.x,
		    y = p1.y,
	//	    z = p1.z,

		    dx = p2.x - x,
		    dy = p2.y - y,
	//	    dz = p2.z - z,

		    t;

		if (dx !== 0 || dy !== 0) {

			t = ((p.x - x) * dx +
	//		     (p.z - z) * dz +
			     (p.y - y) * dy) /
			        (dx * dx +
	//		         dz * dz +
			         dy * dy);

			if (t > 1) {
				x = p2.x;
				y = p2.y;
	//			z = p2.z;

			} else if (t > 0) {
				x += dx * t;
				y += dy * t;
	//			z += dz * t;
			}
		}

		dx = p.x - x;
		dy = p.y - y;
	//	dz = p.z - z;

		return dx * dx +
	//	       dz * dz +
		       dy * dy;
	}

	// the rest of the code doesn't care for the point format


	// basic distance-based simplification

	function simplifyRadialDistance(points, sqTolerance) {

		var i,
		    len = points.length,
		    point,
		    prevPoint = points[0],
		    newPoints = [prevPoint];

		for (i = 1; i < len; i++) {
			point = points[i];

			if (getSquareDistance(point, prevPoint) > sqTolerance) {
				newPoints.push(point);
				prevPoint = point;
			}
		}

		if (prevPoint !== point) {
			newPoints.push(point);
		}

		return newPoints;
	}


	// simplification using optimized Douglas-Peucker algorithm with recursion elimination

	function simplifyDouglasPeucker(points, sqTolerance) {

		var len = points.length,

		    MarkerArray = (typeof Uint8Array !== undefined + '')
		                ? Uint8Array
		                : Array,

		    markers = new MarkerArray(len),

		    first = 0,
		    last  = len - 1,

		    i,
		    maxSqDist,
		    sqDist,
		    index,

		    firstStack = [],
		    lastStack  = [],

		    newPoints  = [];

		markers[first] = markers[last] = 1;

		while (last) {

			maxSqDist = 0;

			for (i = first + 1; i < last; i++) {
				sqDist = getSquareSegmentDistance(points[i], points[first], points[last]);

				if (sqDist > maxSqDist) {
					index = i;
					maxSqDist = sqDist;
				}
			}

			if (maxSqDist > sqTolerance) {
				markers[index] = 1;

				firstStack.push(first);
				lastStack.push(index);

				firstStack.push(index);
				lastStack.push(last);
			}

			first = firstStack.pop();
			last = lastStack.pop();
		}

		for (i = 0; i < len; i++) {
			if (markers[i]) {
				newPoints.push(points[i]);
			}
		}

		return newPoints;
	}


	// both algorithms combined for awesome performance

	function simplify(points, tolerance, highestQuality) {

		var sqTolerance = tolerance !== undefined ? tolerance * tolerance : 1;

		points = highestQuality ? points : simplifyRadialDistance(points, sqTolerance);
		points = simplifyDouglasPeucker(points, sqTolerance);

		return points;
	};


	// export either as a Node.js module, AMD module or a global browser variable

	if (typeof exports === 'object') {
		module.exports = simplify;

	} else if (typeof define === 'function' && define.amd) {
		define(function () {
			return simplify;
		});

	} else {
		global.simplify = simplify;
	}

}(this));

simplify.js

(function() {

d3.simplify = function() {
  var projection = d3.geo.mercator();

  function simplify(feature) {
    if (feature.type !== "MultiPolygon") throw new Error("not yet supported");

    var heap = minHeap(),
        maxArea = 0,
        triangle;

    feature.coordinates = feature.coordinates.map(function(polygon) {
      return polygon.map(function(lineString) {
        var points = lineString.map(projection),
            triangles = [];

        for (var i = 1, n = lineString.length - 1; i < n; ++i) {
          triangle = points.slice(i - 1, i + 2);
          if (triangle[1][2] = area(triangle)) {
            triangles.push(triangle);
            heap.push(triangle);
          }
        }

        for (var i = 0, n = triangles.length; i < n; ++i) {
          triangle = triangles[i];
          triangle.previous = triangles[i - 1];
          triangle.next = triangles[i + 1];
        }

        return points;
      });
    });

    while (triangle = heap.pop()) {

      // If the area of the current point is less than that of the previous point
      // to be eliminated, use the latter’s area instead. This ensures that the
      // current point cannot be eliminated without eliminating previously-
      // eliminated points.
      if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
      else maxArea = triangle[1][2];

      if (triangle.previous) {
        triangle.previous.next = triangle.next;
        triangle.previous[2] = triangle[2];
        update(triangle.previous);
      } else {
        triangle[0][2] = triangle[1][2];
      }

      if (triangle.next) {
        triangle.next.previous = triangle.previous;
        triangle.next[0] = triangle[0];
        update(triangle.next);
      } else {
        triangle[2][2] = triangle[1][2];
      }
    }

    function update(triangle) {
      heap.remove(triangle);
      triangle[1][2] = area(triangle);
      heap.push(triangle);
    }

    return feature;
  }

  simplify.projection = function(_) {
    if (!arguments.length) return projection;
    projection = _;
    return simplify;
  };

  return simplify;
};

function compare(a, b) {
  return a[1][2] - b[1][2];
}

function area(t) {
  return Math.abs((t[0][0] - t[2][0]) * (t[1][1] - t[0][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[0][1]));
}

function minHeap() {
  var heap = {},
      array = [];

  heap.push = function() {
    for (var i = 0, n = arguments.length; i < n; ++i) {
      var object = arguments[i];
      up(object.index = array.push(object) - 1);
    }
    return array.length;
  };

  heap.pop = function() {
    var removed = array[0],
        object = array.pop();
    if (array.length) {
      array[object.index = 0] = object;
      down(0);
    }
    return removed;
  };

  heap.remove = function(removed) {
    var i = removed.index,
        object = array.pop();
    if (i !== array.length) {
      array[object.index = i] = object;
      (compare(object, removed) < 0 ? up : down)(i);
    }
    return i;
  };

  function up(i) {
    var object = array[i];
    while (i > 0) {
      var up = ((i + 1) >> 1) - 1,
          parent = array[up];
      if (compare(object, parent) >= 0) break;
      array[parent.index = i] = parent;
      array[object.index = i = up] = object;
    }
  }

  function down(i) {
    var object = array[i];
    while (true) {
      var right = (i + 1) << 1,
          left = right - 1,
          down = i,
          child = array[down];
      if (left < array.length && compare(array[left], child) < 0) child = array[down = left];
      if (right < array.length && compare(array[right], child) < 0) child = array[down = right];
      if (down === i) break;
      array[child.index = i] = child;
      array[object.index = i = down] = object;
    }
  }

  return heap;
}

})();

simplify_RK_1.0.js

(function() {

d3.simplify = function() {
  var projection = d3.geo.mercator();

  function simplify(feature) {
    if (feature.type !== "MultiPolygon" && feature.type !== "LineString" && feature.type !== "Polygon" && feature.type !== "MultiLineString") throw new Error("not yet supported");

    var heap = minHeap(),
        maxArea = 0,
        triangle;
    if (feature.type == "LineString"){
	    triangles = [];
	    var points = feature.coordinates
	    for (var i=1;i<points.length-1;i++){
		var point = feature.coordinates[i];
		triangle = points.slice(i - 1, i + 2);
		if (triangle[1][2] = area(triangle)) {
		    triangles.push(triangle);
		    heap.push(triangle);
		}
	    }
	    feature.coordinates = feature.coordinates.map(function(lineString) {
		var points = lineString.map(projection);
		for (var i = 1, n = lineString.length - 1; i < n; ++i) {
		  triangle = points.slice(i - 1, i + 2);
		  if (triangle[1][2] = area(triangle)) {
		    triangles.push(triangle);
		    heap.push(triangle);
		  }
		}

		for (var i = 0, n = triangles.length; i < n; ++i) {
		  triangle = triangles[i];
		  triangle.previous = triangles[i - 1];
		  triangle.next = triangles[i + 1];
		}
		return points;

	    });
    }
    else if (feature.type == "Polygon"){
	    feature.coordinates = feature.coordinates.map(function(lineString) {
		var points = lineString.map(projection),
		    triangles = [];

		for (var i = 1, n = lineString.length - 1; i < n; ++i) {
		  triangle = points.slice(i - 1, i + 2);
		  if (triangle[1][2] = area(triangle)) {
		    triangles.push(triangle);
		    heap.push(triangle);
		  }
		}

		for (var i = 0, n = triangles.length; i < n; ++i) {
		  triangle = triangles[i];
		  triangle.previous = triangles[i - 1];
		  triangle.next = triangles[i + 1];
		}

		return points;
	      });
    }
    else if (feature.type == "MultiLineString"){
	feature.coordinates = feature.coordinates.map(function(lineString){
//		console.log(lineString.length);
		var points = lineString.map(projection),
		    triangles = [];
//		console.log(points);
		for (var i = 1, n = lineString.length - 1; i < n; ++i) {
		  triangle = points.slice(i - 1, i + 2);
		  if (triangle[1][2] = area(triangle)) {
		    triangles.push(triangle);
		    heap.push(triangle);
		  }
		}
		for (var i = 0, n = triangles.length; i < n; ++i) {
		  triangle = triangles[i];
		  triangle.previous = triangles[i - 1];
		  triangle.next = triangles[i + 1];
		}
//		console.log(points);
	
		return points;		
   	});
    }
    else if (feature.type == "MultiPolygon"){
	    feature.coordinates = feature.coordinates.map(function(polygon) {
	      return polygon.map(function(lineString) {
		var points = lineString.map(projection),
		    triangles = [];

		for (var i = 1, n = lineString.length - 1; i < n; ++i) {
		  triangle = points.slice(i - 1, i + 2);
		  if (triangle[1][2] = area(triangle)) {
		    triangles.push(triangle);
		    heap.push(triangle);
		  }
		}

		for (var i = 0, n = triangles.length; i < n; ++i) {
		  triangle = triangles[i];
		  triangle.previous = triangles[i - 1];
		  triangle.next = triangles[i + 1];
		}
	
		return points;
	      });
	    });
    }

    while (triangle = heap.pop()) {

      // If the area of the current point is less than that of the previous point
      // to be eliminated, use the latter’s area instead. This ensures that the
      // current point cannot be eliminated without eliminating previously-
      // eliminated points.
      if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
      else maxArea = triangle[1][2];

      if (triangle.previous) {
        triangle.previous.next = triangle.next;
        triangle.previous[2] = triangle[2];
        update(triangle.previous);
      } else {
        triangle[0][2] = triangle[1][2];
      }

      if (triangle.next) {
        triangle.next.previous = triangle.previous;
        triangle.next[0] = triangle[0];
        update(triangle.next);
      } else {
        triangle[2][2] = triangle[1][2];
      }
    }

    function update(triangle) {
      heap.remove(triangle);
      triangle[1][2] = area(triangle);
      heap.push(triangle);
    }

    return feature;
  }

  simplify.projection = function(_) {
    if (!arguments.length) return projection;
    projection = _;
    return simplify;
  };

  return simplify;
};

function compare(a, b) {
  return a[1][2] - b[1][2];
}

function area(t) {
  return Math.abs((t[0][0] - t[2][0]) * (t[1][1] - t[0][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[0][1]));
}

function minHeap() {
  var heap = {},
      array = [];

  heap.push = function() {
    for (var i = 0, n = arguments.length; i < n; ++i) {
      var object = arguments[i];
      up(object.index = array.push(object) - 1);
    }
    return array.length;
  };

  heap.pop = function() {
    var removed = array[0],
        object = array.pop();
    if (array.length) {
      array[object.index = 0] = object;
      down(0);
    }
    return removed;
  };

  heap.remove = function(removed) {
    var i = removed.index,
        object = array.pop();
    if (i !== array.length) {
      array[object.index = i] = object;
      (compare(object, removed) < 0 ? up : down)(i);
    }
    return i;
  };

  function up(i) {
    var object = array[i];
    while (i > 0) {
      var up = ((i + 1) >> 1) - 1,
          parent = array[up];
      if (compare(object, parent) >= 0) break;
      array[parent.index = i] = parent;
      array[object.index = i = up] = object;
    }
  }

  function down(i) {
    var object = array[i];
    while (true) {
      var right = (i + 1) << 1,
          left = right - 1,
          down = i,
          child = array[down];
      if (left < array.length && compare(array[left], child) < 0) child = array[down = left];
      if (right < array.length && compare(array[right], child) < 0) child = array[down = right];
      if (down === i) break;
      array[child.index = i] = child;
      array[object.index = i = down] = object;
    }
  }

  return heap;
}

})();

simplify_RK_1.1.js

(function() {

d3.simplify = function() {
  var projection = d3.geo.mercator();

  function simplify(feature) {
    if (feature.type !== "MultiPolygon" && feature.type !== "LineString") throw new Error("not yet supported");

    var heap = minHeap(),
        maxArea = 0,
        triangle;
        
    //Reform the coordinates to have them in the formatting of a 'MultiPolygon'
    if (feature.type == "LineString")feature.coordinates=[[feature.coordinates]]
    
    feature.coordinates = feature.coordinates.map(function(polygon) {
      return polygon.map(function(lineString) {
        var points = lineString.map(projection),
            triangles = [];

        for (var i = 1, n = lineString.length - 1; i < n; ++i) {
          triangle = points.slice(i - 1, i + 2);
          if (triangle[1][2] = area(triangle)) {
            triangles.push(triangle);
            heap.push(triangle);
          }
        }

        for (var i = 0, n = triangles.length; i < n; ++i) {
          triangle = triangles[i];
          triangle.previous = triangles[i - 1];
          triangle.next = triangles[i + 1];
        }

        return points;
      });
    });

    while (triangle = heap.pop()) {

      // If the area of the current point is less than that of the previous point
      // to be eliminated, use the latter’s area instead. This ensures that the
      // current point cannot be eliminated without eliminating previously-
      // eliminated points.
      if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
      else maxArea = triangle[1][2];

      if (triangle.previous) {
        triangle.previous.next = triangle.next;
        triangle.previous[2] = triangle[2];
        update(triangle.previous);
      } else {
        triangle[0][2] = triangle[1][2];
      }

      if (triangle.next) {
        triangle.next.previous = triangle.previous;
        triangle.next[0] = triangle[0];
        update(triangle.next);
      } else {
        triangle[2][2] = triangle[1][2];
      }
    }

    function update(triangle) {
      heap.remove(triangle);
      triangle[1][2] = area(triangle);
      heap.push(triangle);
    }

    return feature;
  }

  simplify.projection = function(_) {
    if (!arguments.length) return projection;
    projection = _;
    return simplify;
  };

  return simplify;
};

function compare(a, b) {
  return a[1][2] - b[1][2];
}

function area(t) {
  return Math.abs((t[0][0] - t[2][0]) * (t[1][1] - t[0][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[0][1]));
}

function minHeap() {
  var heap = {},
      array = [];

  heap.push = function() {
    for (var i = 0, n = arguments.length; i < n; ++i) {
      var object = arguments[i];
      up(object.index = array.push(object) - 1);
    }
    return array.length;
  };

  heap.pop = function() {
    var removed = array[0],
        object = array.pop();
    if (array.length) {
      array[object.index = 0] = object;
      down(0);
    }
    return removed;
  };

  heap.remove = function(removed) {
    var i = removed.index,
        object = array.pop();
    if (i !== array.length) {
      array[object.index = i] = object;
      (compare(object, removed) < 0 ? up : down)(i);
    }
    return i;
  };

  function up(i) {
    var object = array[i];
    while (i > 0) {
      var up = ((i + 1) >> 1) - 1,
          parent = array[up];
      if (compare(object, parent) >= 0) break;
      array[parent.index = i] = parent;
      array[object.index = i = up] = object;
    }
  }

  function down(i) {
    var object = array[i];
    while (true) {
      var right = (i + 1) << 1,
          left = right - 1,
          down = i,
          child = array[down];
      if (left < array.length && compare(array[left], child) < 0) child = array[down = left];
      if (right < array.length && compare(array[right], child) < 0) child = array[down = right];
      if (down === i) break;
      array[child.index = i] = child;
      array[object.index = i = down] = object;
    }
  }

  return heap;
}

})();