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]) {

h = i;

} else if (vertices[i][1] == vertices[h][1]) {

h = (vertices[i][0] < vertices[h][0] ? i : h);

}

}

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

} else {

points[u].index = -1;

a = points[i].angle;

u = i;

v = j;

}

} else {

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 === -1) 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=0; i<sp; ++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;

}