(function(){d3.geom = {};

/**

 * Computes a contour for a given input grid function using the <a

 * href="http://en.wikipedia.org/wiki/Marching_squares">marching

 * squares</a> algorithm. Returns the contour polygon as an array of points.

 *

 * @param grid a two-input function(x, y) that returns true for values

 * inside the contour and false for values outside the contour.

 * @param start an optional starting point [x, y] on the grid.

 * @returns polygon [[x1, y1], [x2, y2], …]

 */

d3.geom.contour = function(grid, start) {

  var s = start || d3_geom_contourStart(grid), // starting point

      c = [],    // contour polygon

      x = s[0],  // current x position

      y = s[1],  // current y position

      dx = 0,    // next x direction

      dy = 0,    // next y direction

      pdx = NaN, // previous x direction

      pdy = NaN, // previous y direction

      i = 0;

  do {

    // determine marching squares index

    i = 0;

    if (grid(x-1, y-1)) i += 1;

    if (grid(x,   y-1)) i += 2;

    if (grid(x-1, y  )) i += 4;

    if (grid(x,   y  )) i += 8;

    // determine next direction

    if (i === 6) {

      dx = pdy === -1 ? -1 : 1;

      dy = 0;

    } else if (i === 9) {

      dx = 0;

      dy = pdx === 1 ? -1 : 1;

    } else {

      dx = d3_geom_contourDx[i];

      dy = d3_geom_contourDy[i];

    }

    // update contour polygon

    if (dx != pdx && dy != pdy) {

      c.push([x, y]);

      pdx = dx;

      pdy = dy;

    }

    x += dx;

    y += dy;

  } while (s[0] != x || s[1] != y);

  return c;

};

// lookup tables for marching directions

var d3_geom_contourDx = [1, 0, 1, 1,-1, 0,-1, 1,0, 0,0,0,-1, 0,-1,NaN],

    d3_geom_contourDy = [0,-1, 0, 0, 0,-1, 0, 0,1,-1,1,1, 0,-1, 0,NaN];

function d3_geom_contourStart(grid) {

  var x = 0,

      y = 0;

  // search for a starting point; begin at origin

  // and proceed along outward-expanding diagonals

  while (true) {

    if (grid(x,y)) {

      return [x,y];

    }

    if (x === 0) {

      x = y + 1;

      y = 0;

    } else {

      x = x - 1;

      y = y + 1;

    }

  }

}

/**

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

  if (vertices.length < 3) return [];

  var len = vertices.length,

      plen = len - 1,

      points = [],

      stack = [],

      i, j, h = 0, x1, y1, x2, y2, u, v, a, sp;

  // find the starting ref point: leftmost point with the minimum y coord

  for (i=1; i<len; ++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<len; ++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(vertices[stack[i]]);

  }

  return poly;

}

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

}

// Note: requires coordinates to be counterclockwise and convex!

d3.geom.polygon = function(coordinates) {

  coordinates.area = function() {

    var i = 0,

        n = coordinates.length,

        a = coordinates[n - 1][0] * coordinates[0][1],

        b = coordinates[n - 1][1] * coordinates[0][0];

    while (++i < n) {

      a += coordinates[i - 1][0] * coordinates[i][1];

      b += coordinates[i - 1][1] * coordinates[i][0];

    }

    return (b - a) * .5;

  };

  coordinates.centroid = function(k) {

    var i = -1,

        n = coordinates.length - 1,

        x = 0,

        y = 0,

        a,

        b,

        c;

    if (!arguments.length) k = -1 / (6 * coordinates.area());

    while (++i < n) {

      a = coordinates[i];

      b = coordinates[i + 1];

      c = a[0] * b[1] - b[0] * a[1];

      x += (a[0] + b[0]) * c;

      y += (a[1] + b[1]) * c;

    }

    return [x * k, y * k];

  };

  // The Sutherland-Hodgman clipping algorithm.

  coordinates.clip = function(subject) {

    var input,

        i = -1,

        n = coordinates.length,

        j,

        m,

        a = coordinates[n - 1],

        b,

        c,

        d;

    while (++i < n) {

      input = subject.slice();

      subject.length = 0;

      b = coordinates[i];

      c = input[(m = input.length) - 1];

      j = -1;

      while (++j < m) {

        d = input[j];

        if (d3_geom_polygonInside(d, a, b)) {

          if (!d3_geom_polygonInside(c, a, b)) {

            subject.push(d3_geom_polygonIntersect(c, d, a, b));

          }

          subject.push(d);

        } else if (d3_geom_polygonInside(c, a, b)) {

          subject.push(d3_geom_polygonIntersect(c, d, a, b));

        }

        c = d;

      }

      a = b;

    }

    return subject;

  };

  return coordinates;

};

function d3_geom_polygonInside(p, a, b) {

  return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);

}

// Intersect two infinite lines cd and ab.

function d3_geom_polygonIntersect(c, d, a, b) {

  var x1 = c[0], x2 = d[0], x3 = a[0], x4 = b[0],

      y1 = c[1], y2 = d[1], y3 = a[1], y4 = b[1],

      x13 = x1 - x3,

      x21 = x2 - x1,

      x43 = x4 - x3,

      y13 = y1 - y3,

      y21 = y2 - y1,

      y43 = y4 - y3,

      ua = (x43 * y13 - y43 * x13) / (y43 * x21 - x43 * y21);

  return [x1 + ua * x21, y1 + ua * y21];

}

// Adapted from Nicolas Garcia Belmonte's JIT implementation:

// http://blog.thejit.org/2010/02/12/voronoi-tessellation/

// http://blog.thejit.org/assets/voronoijs/voronoi.js

// See lib/jit/LICENSE for details.

// Notes:

//

// This implementation does not clip the returned polygons, so if you want to

// clip them to a particular shape you will need to do that either in SVG or by

// post-processing with d3.geom.polygon's clip method.

//

// If any vertices are coincident or have NaN positions, the behavior of this

// method is undefined. Most likely invalid polygons will be returned. You

// should filter invalid points, and consolidate coincident points, before

// computing the tessellation.

/**

 * @param vertices [[x1, y1], [x2, y2], …]

 * @returns polygons [[[x1, y1], [x2, y2], …], …]

 */

d3.geom.voronoi = function(vertices) {

  var polygons = vertices.map(function() { return []; });

  d3_voronoi_tessellate(vertices, function(e) {

    var s1,

        s2,

        x1,

        x2,

        y1,

        y2;

    if (e.a === 1 && e.b >= 0) {

      s1 = e.ep.r;

      s2 = e.ep.l;

    } else {

      s1 = e.ep.l;

      s2 = e.ep.r;

    }

    if (e.a === 1) {

      y1 = s1 ? s1.y : -1e6;

      x1 = e.c - e.b * y1;

      y2 = s2 ? s2.y : 1e6;

      x2 = e.c - e.b * y2;

    } else {

      x1 = s1 ? s1.x : -1e6;

      y1 = e.c - e.a * x1;

      x2 = s2 ? s2.x : 1e6;

      y2 = e.c - e.a * x2;

    }

    var v1 = [x1, y1],

        v2 = [x2, y2];

    polygons[e.region.l.index].push(v1, v2);

    polygons[e.region.r.index].push(v1, v2);

  });

  // Reconnect the polygon segments into counterclockwise loops.

  return polygons.map(function(polygon, i) {

    var cx = vertices[i][0],

        cy = vertices[i][1];

    polygon.forEach(function(v) {

      v.angle = Math.atan2(v[0] - cx, v[1] - cy);