import "../svg/line";
import "geom";

/**
 * Computes the 2D convex hull of a set of points using Graham's scanning
 * algorithm. The algorithm has been implemented as described in Cormen,
 * Leiserson, and Rivest's Introduction to Algorithms. The running time of
 * this algorithm is O(n log n), where n is the number of input points.
 *
 * @param vertices [[x1, y1], [x2, y2], …]
 * @returns polygon [[x1, y1], [x2, y2], …]
 */
d3.geom.hull = function(vertices) {
  var x = d3_svg_lineX,
      y = d3_svg_lineY;

  if (arguments.length) return hull(vertices);

  function hull(data) {
    if (data.length < 3) return [];

    var fx = d3_functor(x),
        fy = d3_functor(y),
        n = data.length,
        vertices, // TODO use parallel arrays
        plen = n - 1,
        points = [],
        stack = [],
        d,
        i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;

    if (fx === d3_svg_lineX && y === d3_svg_lineY) vertices = data;
    else for (i = 0, vertices = []; i < n; ++i) {
      vertices.push([+fx.call(this, d = data[i], i), +fy.call(this, d, i)]);
    }

    // find the starting ref point: leftmost point with the minimum y coord
    for (i = 1; i < n; ++i) {
      if (vertices[i][1] < vertices[h][1]
          || vertices[i][1] == vertices[h][1]
          && vertices[i][0] < vertices[h][0]) h = i;
    }

    // calculate polar angles from ref point and sort
    for (i = 0; i < n; ++i) {
      if (i === h) continue;
      y1 = vertices[i][1] - vertices[h][1];
      x1 = vertices[i][0] - vertices[h][0];
      points.push({angle: Math.atan2(y1, x1), index: i});
    }
    points.sort(function(a, b) { return a.angle - b.angle; });

    // toss out duplicate angles
    a = points[0].angle;
    v = points[0].index;
    u = 0;
    for (i = 1; i < plen; ++i) {
      j = points[i].index;
      if (a == points[i].angle) {
        // keep angle for point most distant from the reference
        x1 = vertices[v][0] - vertices[h][0];
        y1 = vertices[v][1] - vertices[h][1];
        x2 = vertices[j][0] - vertices[h][0];
        y2 = vertices[j][1] - vertices[h][1];
        if (x1 * x1 + y1 * y1 >= x2 * x2 + y2 * y2) {
          points[i].index = -1;
          continue;
        } else {
          points[u].index = -1;
        }
      }
      a = points[i].angle;
      u = i;
      v = j;
    }

    // initialize the stack
    stack.push(h);
    for (i = 0, j = 0; i < 2; ++j) {
      if (points[j].index > -1) {
        stack.push(points[j].index);
        i++;
      }
    }
    sp = stack.length;

    // do graham's scan
    for (; j < plen; ++j) {
      if (points[j].index < 0) continue; // skip tossed out points
      while (!d3_geom_hullCCW(stack[sp - 2], stack[sp - 1], points[j].index, vertices)) {
        --sp;
      }
      stack[sp++] = points[j].index;
    }

    // construct the hull
    var poly = [];
    for (i = sp - 1; i >= 0; --i) poly.push(data[stack[i]]);
    return poly;
  }

  hull.x = function(_) {
    return arguments.length ? (x = _, hull) : x;
  };

  hull.y = function(_) {
    return arguments.length ? (y = _, hull) : y;
  };

  return hull;
};

// are three points in counter-clockwise order?
function d3_geom_hullCCW(i1, i2, i3, v) {
  var t, a, b, c, d, e, f;
  t = v[i1]; a = t[0]; b = t[1];
  t = v[i2]; c = t[0]; d = t[1];
  t = v[i3]; e = t[0]; f = t[1];
  return (f - b) * (c - a) - (d - b) * (e - a) > 0;
}
