Ramer Douglas Peucker

ramer-douglas-peucker.js

//   ____ __  __ ___ ________  _   ___   __
//  / ___|  \/  |_ _|__  / _ \| \ | \ \ / /
// | |   | |\/| || |  / / | | |  \| |\ V / 
// | |___| |  | || | / /| |_| | |\  | | |  
//  \____|_|  |_|___/____\___/|_| \_| |_|  


/**
* @method ramerDouglasPeucker
*
* @description Algorithm for reducing the number of points in a curve that is
* approximated by a series of points
*
* @param {Array} points an array of JSON objects
* @param {Float} epsilon, determine recursively simplification
* @param {Array} comparison_fields an array of keys which represent x and y
*/

function ramerDouglasPeucker(points,epsilon,comparison_fields) {
  var x = comparison_fields[0];
  var y = comparison_fields[1];

  function findPerpendicularDistance(p, p1,p2) {
    // if start and end point are on the same x 
    // then the distance is the difference in X.
    var result;
    var slope;
    var intercept;
    if (p1[x] == p2[x]) {
      result=Math.abs(p[x]-p1[x]);
    } else {
      slope		 = (p2[y] - p1[y]) / (p2[x] - p1[x]);
      intercept	 = p1[y] - (slope * p1[x]);
      result		 = Math.abs(slope * p[x] - p[y] + intercept) / Math.sqrt(Math.pow(slope, 2) + 1);
    }

    return result;
  }
  var firstPoint	= points[0];
  var lastPoint	= points[points.length-1];

  if (points.length < 3) {
    return points;
  }

  var index	= -1;
  var dist	= 0;

  var str ="";
  for (var i=1 ; i<points.length-1 ; i++) {
    var cDist = findPerpendicularDistance(points[i],firstPoint,lastPoint);
    str += cDist+" ";
    if (cDist > dist) {
      dist	= cDist;
      index	= i;
    }
  }
  if (dist > epsilon) {
    // iterate
    var l1 = points.slice(0, index+1);
    var l2 = points.slice(index);
    var r1 = ramerDouglasPeucker(l1,epsilon,comparison_fields);
    var r2 = ramerDouglasPeucker(l2,epsilon,comparison_fields);
    // concat r2 to r1 minus the end/startpoint that will be the same
    var rs = r1.slice(0,r1.length-1).concat(r2);
    return rs;
  } else {
    return [firstPoint,lastPoint];
  }
}