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

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

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

     4 // See lib/jit/LICENSE for details.

     5 

     6 // Notes:

     7 //

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

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

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

    11 //

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

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

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

    15 // computing the tessellation.

    16 

    17 /**

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

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

    20  */

    21 d3.geom.voronoi = function(vertices) {

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

    23 

    24   d3_voronoi_tessellate(vertices, function(e) {

    25     var s1,

    26         s2,

    27         x1,

    28         x2,

    29         y1,

    30         y2;

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

    32       s1 = e.ep.r;

    33       s2 = e.ep.l;

    34     } else {

    35       s1 = e.ep.l;

    36       s2 = e.ep.r;

    37     }

    38     if (e.a === 1) {

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

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

    41       y2 = s2 ? s2.y : 1e6;

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

    43     } else {

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

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

    46       x2 = s2 ? s2.x : 1e6;

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

    48     }

    49     var v1 = [x1, y1],

    50         v2 = [x2, y2];

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

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

    53   });

    54 

    55   // Reconnect the polygon segments into counterclockwise loops.

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

    57     var cx = vertices[i][0],

    58         cy = vertices[i][1];

    59     polygon.forEach(function(v) {

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

    61     });

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

    63       return a.angle - b.angle;

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

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

    66     });

    67   });

    68 };

    69 

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

    71 

    72 function d3_voronoi_tessellate(vertices, callback) {

    73 

    74   var Sites = {

    75     list: vertices

    76       .map(function(v, i) {

    77         return {

    78           index: i,

    79           x: v[0],

    80           y: v[1]

    81         };

    82       })

    83       .sort(function(a, b) {

    84         return a.y < b.y ? -1

    85           : a.y > b.y ? 1

    86           : a.x < b.x ? -1

    87           : a.x > b.x ? 1

    88           : 0;

    89       }),

    90     bottomSite: null

    91   };

    92 

    93   var EdgeList = {

    94     list: [],

    95     leftEnd: null,

    96     rightEnd: null,

    97 

    98     init: function() {

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

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

   101       EdgeList.leftEnd.r = EdgeList.rightEnd;

   102       EdgeList.rightEnd.l = EdgeList.leftEnd;

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

   104     },

   105 

   106     createHalfEdge: function(edge, side) {

   107       return {

   108         edge: edge,

   109         side: side,

   110         vertex: null,

   111         "l": null,

   112         "r": null

   113       };

   114     },

   115 

   116     insert: function(lb, he) {

   117       he.l = lb;

   118       he.r = lb.r;

   119       lb.r.l = he;

   120       lb.r = he;

   121     },

   122 

   123     leftBound: function(p) {

   124       var he = EdgeList.leftEnd;

   125       do {

   126         he = he.r;

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

   128       he = he.l;

   129       return he;

   130     },

   131 

   132     del: function(he) {

   133       he.l.r = he.r;

   134       he.r.l = he.l;

   135       he.edge = null;

   136     },

   137 

   138     right: function(he) {

   139       return he.r;

   140     },

   141 

   142     left: function(he) {

   143       return he.l;

   144     },

   145 

   146     leftRegion: function(he) {

   147       return he.edge == null

   148           ? Sites.bottomSite

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

   150     },

   151 

   152     rightRegion: function(he) {

   153       return he.edge == null

   154           ? Sites.bottomSite

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

   156     }

   157   };

   158 

   159   var Geom = {

   160 

   161     bisect: function(s1, s2) {

   162       var newEdge = {

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

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

   165       };

   166 

   167       var dx = s2.x - s1.x,

   168           dy = s2.y - s1.y,

   169           adx = dx > 0 ? dx : -dx,

   170           ady = dy > 0 ? dy : -dy;

   171 

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

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

   174 

   175       if (adx > ady) {

   176         newEdge.a = 1;

   177         newEdge.b = dy / dx;

   178         newEdge.c /= dx;

   179       } else {

   180         newEdge.b = 1;

   181         newEdge.a = dx / dy;

   182         newEdge.c /= dy;

   183       }

   184 

   185       return newEdge;

   186     },

   187 

   188     intersect: function(el1, el2) {

   189       var e1 = el1.edge,

   190           e2 = el2.edge;

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

   192         return null;

   193       }

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

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

   196         return null;

   197       }

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

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

   200           e1r = e1.region.r,

   201           e2r = e2.region.r,

   202           el,

   203           e;

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

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

   206         el = el1;

   207         e = e1;

   208       } else {

   209         el = el2;

   210         e = e2;

   211       }

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

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

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

   215         return null;

   216       }

   217       return {

   218         x: xint,

   219         y: yint

   220       };

   221     },

   222 

   223     rightOf: function(he, p) {

   224       var e = he.edge,

   225           topsite = e.region.r,

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

   227 

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

   229         return 1;

   230       }

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

   232         return 0;

   233       }

   234       if (e.a === 1) {

   235         var dyp = p.y - topsite.y,

   236             dxp = p.x - topsite.x,

   237             fast = 0,

   238             above = 0;

   239 

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

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

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

   243         } else {

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

   245           if (e.b < 0) {

   246             above = !above;

   247           }

   248           if (!above) {

   249             fast = 1;

   250           }

   251         }

   252         if (!fast) {

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

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

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

   256 

   257           if (e.b < 0) {

   258             above = !above;

   259           }

   260         }

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

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

   263             t1 = p.y - yl,

   264             t2 = p.x - topsite.x,

   265             t3 = yl - topsite.y;

   266 

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

   268       }

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

   270     },

   271 

   272     endPoint: function(edge, side, site) {

   273       edge.ep[side] = site;

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

   275       callback(edge);

   276     },

   277 

   278     distance: function(s, t) {

   279       var dx = s.x - t.x,

   280           dy = s.y - t.y;

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

   282     }

   283   };

   284 

   285   var EventQueue = {

   286     list: [],

   287 

   288     insert: function(he, site, offset) {

   289       he.vertex = site;

   290       he.ystar = site.y + offset;

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

   292         var next = list[i];

   293         if (he.ystar > next.ystar ||

   294           (he.ystar == next.ystar &&

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

   296           continue;

   297         } else {

   298           break;

   299         }

   300       }

   301       list.splice(i, 0, he);

   302     },

   303 

   304     del: function(he) {

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

   306       ls.splice(i, 1);

   307     },

   308 

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

   310 

   311     nextEvent: function(he) {

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

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

   314       }

   315       return null;

   316     },

   317 

   318     min: function() {

   319       var elem = EventQueue.list[0];

   320       return {

   321         x: elem.vertex.x,

   322         y: elem.ystar

   323       };

   324     },

   325 

   326     extractMin: function() {

   327       return EventQueue.list.shift();

   328     }

   329   };

   330 

   331   EdgeList.init();

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

   333 

   334   var newSite = Sites.list.shift(), newIntStar;

   335   var lbnd, rbnd, llbnd, rrbnd, bisector;

   336   var bot, top, temp, p, v;

   337   var e, pm;

   338 

   339   while (true) {

   340     if (!EventQueue.empty()) {

   341       newIntStar = EventQueue.min();

   342     }

   343     if (newSite && (EventQueue.empty()

   344       || newSite.y < newIntStar.y

   345       || (newSite.y == newIntStar.y

   346       && newSite.x < newIntStar.x))) { //new site is smallest

   347       lbnd = EdgeList.leftBound(newSite);

   348       rbnd = EdgeList.right(lbnd);

   349       bot = EdgeList.rightRegion(lbnd);

   350       e = Geom.bisect(bot, newSite);

   351       bisector = EdgeList.createHalfEdge(e, "l");

   352       EdgeList.insert(lbnd, bisector);

   353       p = Geom.intersect(lbnd, bisector);

   354       if (p) {

   355         EventQueue.del(lbnd);

   356         EventQueue.insert(lbnd, p, Geom.distance(p, newSite));

   357       }

   358       lbnd = bisector;

   359       bisector = EdgeList.createHalfEdge(e, "r");

   360       EdgeList.insert(lbnd, bisector);

   361       p = Geom.intersect(bisector, rbnd);

   362       if (p) {

   363         EventQueue.insert(bisector, p, Geom.distance(p, newSite));

   364       }

   365       newSite = Sites.list.shift();

   366     } else if (!EventQueue.empty()) { //intersection is smallest

   367       lbnd = EventQueue.extractMin();

   368       llbnd = EdgeList.left(lbnd);

   369       rbnd = EdgeList.right(lbnd);

   370       rrbnd = EdgeList.right(rbnd);

   371       bot = EdgeList.leftRegion(lbnd);

   372       top = EdgeList.rightRegion(rbnd);

   373       v = lbnd.vertex;

   374       Geom.endPoint(lbnd.edge, lbnd.side, v);

   375       Geom.endPoint(rbnd.edge, rbnd.side, v);

   376       EdgeList.del(lbnd);

   377       EventQueue.del(rbnd);

   378       EdgeList.del(rbnd);

   379       pm = "l";

   380       if (bot.y > top.y) {

   381         temp = bot;

   382         bot = top;

   383         top = temp;

   384         pm = "r";

   385       }

   386       e = Geom.bisect(bot, top);

   387       bisector = EdgeList.createHalfEdge(e, pm);

   388       EdgeList.insert(llbnd, bisector);

   389       Geom.endPoint(e, d3_voronoi_opposite[pm], v);

   390       p = Geom.intersect(llbnd, bisector);

   391       if (p) {

   392         EventQueue.del(llbnd);

   393         EventQueue.insert(llbnd, p, Geom.distance(p, bot));

   394       }

   395       p = Geom.intersect(bisector, rrbnd);

   396       if (p) {

   397         EventQueue.insert(bisector, p, Geom.distance(p, bot));

   398       }

   399     } else {

   400       break;

   401     }

   402   }//end while

   403 

   404   for (lbnd = EdgeList.right(EdgeList.leftEnd);

   405       lbnd != EdgeList.rightEnd;

   406       lbnd = EdgeList.right(lbnd)) {

   407     callback(lbnd.edge);

   408   }

   409 }