Graham scan

graham_scan.es6

function graham_scan(points) {
  const pivot = points.reduce((c, p) =>
                                  p.y < c.y || p.y===c.y && p.x<c.x ? p : c);
  const sorted = points
                  .map(p=>({x:p.x,y:p.y,angle:Math.atan2(p.y-pivot.y,p.x-pivot.x)}))
                  .sort((a,b) => a.angle === b.angle ? a.x - b.x : a.angle - b.angle);
  function cross_p (a,b,c) {return (b.x-a.x)*(c.y-a.y) <= (b.y-a.y)*(c.x-a.x);}
  var result = [sorted[0], sorted[1]], top = 1;
  for(var i=2; i<sorted.length; i++){
    while (top >= 1 && cross_p(result[top-1], result[top], sorted[i])) top--;
    result[++top] = sorted[i];
  }
  return result.slice(0,top+1);
}

graham_scan.js

function graham_scan(points) {
  var pivot = points.reduce(function (c, p) {
    return p.y < c.y || p.y === c.y && p.x < c.x ? p : c;
  });
  var sorted = points.map(function (p) {
    return { x: p.x, y: p.y, angle: Math.atan2(p.y - pivot.y, p.x - pivot.x) };
  }).sort(function (a, b) {
    return a.angle === b.angle ? a.x - b.x : a.angle - b.angle;
  });
  function cross_p(a, b, c) {
    return (b.x - a.x) * (c.y - a.y) <= (b.y - a.y) * (c.x - a.x);
  }
  var result = [sorted[0], sorted[1]],
      top = 1;
  for (var i = 2; i < sorted.length; i++) {
    while (top >= 1 && cross_p(result[top - 1], result[top], sorted[i])) top--;
    result[++top] = sorted[i];
  }
  return result.slice(0, top + 1);
}

graham_scan_fast.js

/* Fast optimized version of the graham scan in javascript
  computes the hull of 1 million points in 600ms in firefox
  Note: the orginal points array will be reordered in place, and a "_graham_angle" property will be added to all the points.
  @param points : an array of points. Each point is represented as an array [x,y]
  @return : an array of points. The points form the convex hull of the original set of points
*/
function graham_scan(points) {
  // The enveloppe is the points themselves
  if (points.length <= 3) return points;
  
  // Find the pivot
  var pivot = points[0];
  for (var i=0; i<points.length; i++) {
    if (points[i][1] < pivot[1] || (points[i][1] === pivot[1] && points[i][0] < pivot[0]))
      pivot = points[i];
  }

  // Attribute an angle to the points
  for (var i=0; i<points.length; i++) {
    points[i]._graham_angle = Math.atan2(points[i][1] - pivot[1], points[i][0] - pivot[0]);
  }
  points.sort(function(a, b){return a._graham_angle === b._graham_angle
                                        ? a[0] - b[0]
                                        : a._graham_angle - b._graham_angle});

  // Adding points to the result if they "turn left"
  var result = [points[0]], len=1;
  for(var i=1; i<points.length; i++){
    var a = result[len-2],
        b = result[len-1],
        c = points[i];
    while (
        (len === 1 && b[0] === c[0] && b[1] === c[1]) ||
        (len > 1 && (b[0]-a[0]) * (c[1]-a[1]) <= (b[1]-a[1]) * (c[0]-a[0]))) {
        len--;
        b = a;
        a = result[len-2];
    }
    result[len++] = c;
  }
  result.length = len;
  return result;
}