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

    });

    return polygon.sort(function(a, b) {

      return a.angle - b.angle;

    }).filter(function(d, i) {

      return !i || (d.angle - polygon[i - 1].angle > 1e-10);

    });

  });

};

var d3_voronoi_opposite = {"l": "r", "r": "l"};

function d3_voronoi_tessellate(vertices, callback) {

  var Sites = {

    list: vertices

      .map(function(v, i) {

        return {

          index: i,

          x: v[0],

          y: v[1]

        };

      })

      .sort(function(a, b) {

        return a.y < b.y ? -1

          : a.y > b.y ? 1

          : a.x < b.x ? -1

          : a.x > b.x ? 1

          : 0;

      }),

    bottomSite: null

  };

  var EdgeList = {

    list: [],

    leftEnd: null,

    rightEnd: null,

    init: function() {

      EdgeList.leftEnd = EdgeList.createHalfEdge(null, "l");

      EdgeList.rightEnd = EdgeList.createHalfEdge(null, "l");

      EdgeList.leftEnd.r = EdgeList.rightEnd;

      EdgeList.rightEnd.l = EdgeList.leftEnd;

      EdgeList.list.unshift(EdgeList.leftEnd, EdgeList.rightEnd);

    },

    createHalfEdge: function(edge, side) {

      return {

        edge: edge,

        side: side,

        vertex: null,

        "l": null,

        "r": null

      };

    },

    insert: function(lb, he) {

      he.l = lb;

      he.r = lb.r;

      lb.r.l = he;

      lb.r = he;

    },

    leftBound: function(p) {

      var he = EdgeList.leftEnd;

      do {

        he = he.r;

      } while (he != EdgeList.rightEnd && Geom.rightOf(he, p));

      he = he.l;

      return he;

    },

    del: function(he) {

      he.l.r = he.r;

      he.r.l = he.l;

      he.edge = null;

    },

    right: function(he) {

      return he.r;

    },

    left: function(he) {

      return he.l;

    },

    leftRegion: function(he) {

      return he.edge == null

          ? Sites.bottomSite

          : he.edge.region[he.side];

    },

    rightRegion: function(he) {

      return he.edge == null

          ? Sites.bottomSite

          : he.edge.region[d3_voronoi_opposite[he.side]];

    }

  };

  var Geom = {

    bisect: function(s1, s2) {

      var newEdge = {

        region: {"l": s1, "r": s2},

        ep: {"l": null, "r": null}

      };

      var dx = s2.x - s1.x,

          dy = s2.y - s1.y,

          adx = dx > 0 ? dx : -dx,

          ady = dy > 0 ? dy : -dy;

      newEdge.c = s1.x * dx + s1.y * dy

          + (dx * dx + dy * dy) * .5;

      if (adx > ady) {

        newEdge.a = 1;

        newEdge.b = dy / dx;

        newEdge.c /= dx;

      } else {

        newEdge.b = 1;

        newEdge.a = dx / dy;

        newEdge.c /= dy;

      }

      return newEdge;

    },

    intersect: function(el1, el2) {

      var e1 = el1.edge,

          e2 = el2.edge;

      if (!e1 || !e2 || (e1.region.r == e2.region.r)) {

        return null;

      }

      var d = (e1.a * e2.b) - (e1.b * e2.a);

      if (Math.abs(d) < 1e-10) {

        return null;

      }

      var xint = (e1.c * e2.b - e2.c * e1.b) / d,

          yint = (e2.c * e1.a - e1.c * e2.a) / d,

          e1r = e1.region.r,

          e2r = e2.region.r,

          el,

          e;

      if ((e1r.y < e2r.y) ||

         (e1r.y == e2r.y && e1r.x < e2r.x)) {

        el = el1;

        e = e1;

      } else {

        el = el2;

        e = e2;

      }

      var rightOfSite = (xint >= e.region.r.x);

      if ((rightOfSite && (el.side === "l")) ||

        (!rightOfSite && (el.side === "r"))) {

        return null;

      }

      return {

        x: xint,

        y: yint

      };

    },

    rightOf: function(he, p) {

      var e = he.edge,

          topsite = e.region.r,

          rightOfSite = (p.x > topsite.x);

      if (rightOfSite && (he.side === "l")) {

        return 1;

      }

      if (!rightOfSite && (he.side === "r")) {

        return 0;

      }

      if (e.a === 1) {

        var dyp = p.y - topsite.y,

            dxp = p.x - topsite.x,

            fast = 0,

            above = 0;

        if ((!rightOfSite && (e.b < 0)) ||

          (rightOfSite && (e.b >= 0))) {

          above = fast = (dyp >= e.b * dxp);

        } else {

          above = ((p.x + p.y * e.b) > e.c);

          if (e.b < 0) {

            above = !above;

          }

          if (!above) {

            fast = 1;

          }

        }

        if (!fast) {

          var dxs = topsite.x - e.region.l.x;

          above = (e.b * (dxp * dxp - dyp * dyp)) <

            (dxs * dyp * (1 + 2 * dxp / dxs + e.b * e.b));

          if (e.b < 0) {

            above = !above;

          }

        }

      } else /* e.b == 1 */ {

        var yl = e.c - e.a * p.x,

            t1 = p.y - yl,

            t2 = p.x - topsite.x,

            t3 = yl - topsite.y;

        above = (t1 * t1) > (t2 * t2 + t3 * t3);

      }

      return he.side === "l" ? above : !above;

    },

    endPoint: function(edge, side, site) {

      edge.ep[side] = site;

      if (!edge.ep[d3_voronoi_opposite[side]]) return;

      callback(edge);

    },

    distance: function(s, t) {

      var dx = s.x - t.x,

          dy = s.y - t.y;

      return Math.sqrt(dx * dx + dy * dy);

    }

  };

  var EventQueue = {

    list: [],

    insert: function(he, site, offset) {

      he.vertex = site;

      he.ystar = site.y + offset;

      for (var i=0, list=EventQueue.list, l=list.length; i<l; i++) {

        var next = list[i];

        if (he.ystar > next.ystar ||

          (he.ystar == next.ystar &&

          site.x > next.vertex.x)) {

          continue;

        } else {

          break;

        }

      }

      list.splice(i, 0, he);

    },

    del: function(he) {

      for (var i=0, ls=EventQueue.list, l=ls.length; i<l && (ls[i] != he); ++i) {}

      ls.splice(i, 1);

    },

    empty: function() { return EventQueue.list.length === 0; },

    nextEvent: function(he) {

      for (var i=0, ls=EventQueue.list, l=ls.length; i<l; ++i) {

        if (ls[i] == he) return ls[i+1];

      }

      return null;

    },

    min: function() {

      var elem = EventQueue.list[0];

      return {

        x: elem.vertex.x,

        y: elem.ystar

      };

    },

    extractMin: function() {

      return EventQueue.list.shift();

    }

  };

  EdgeList.init();

  Sites.bottomSite = Sites.list.shift();