import “../arrays/range”; import “../core/functor”; import “../math/trigonometry”; import “../svg/line”; import “delaunay”; import “geom”; import “polygon”;
// Adapted from Nicolas Garcia Belmonte's JIT implementation: // blog.thejit.org/2010/02/12/voronoi-tessellation/ // 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 points 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 points [[x1, y1], [x2, y2], …] * @returns polygons [[[x1, y1], [x2, y2], …], …] */
d3.geom.voronoi = function(points) {
var x = d3_svg_lineX, y = d3_svg_lineY, clipPolygon = null; // For backwards-compatibility. if (arguments.length) return voronoi(points); function voronoi(data) { var points, polygons = data.map(function() { return []; }), fx = d3_functor(x), fy = d3_functor(y), d, i, n = data.length, Z = 1e6; if (fx === d3_svg_lineX && fy === d3_svg_lineY) points = data; else for (points = new Array(n), i = 0; i < n; ++i) { points[i] = [+fx.call(this, d = data[i], i), +fy.call(this, d, i)]; } d3_geom_voronoiTessellate(points, 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 : -Z; x1 = e.c - e.b * y1; y2 = s2 ? s2.y : Z; x2 = e.c - e.b * y2; } else { x1 = s1 ? s1.x : -Z; y1 = e.c - e.a * x1; x2 = s2 ? s2.x : Z; 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); }); // Connect edges into counterclockwise polygons without coincident points. polygons = polygons.map(function(polygon, i) { var cx = points[i][0], cy = points[i][1], angle = polygon.map(function(v) { return Math.atan2(v[0] - cx, v[1] - cy); }), order = d3.range(polygon.length).sort(function(a, b) { return angle[a] - angle[b]; }); return order .filter(function(d, i) { return !i || (angle[d] - angle[order[i - 1]] > ε); }) .map(function(d) { return polygon[d]; }); }); // Fix degenerate polygons. polygons.forEach(function(polygon, i) { var n = polygon.length; if (!n) return polygon.push([-Z, -Z], [-Z, Z], [Z, Z], [Z, -Z]); if (n > 2) return; var p0 = points[i], p1 = polygon[0], p2 = polygon[1], x0 = p0[0], y0 = p0[1], x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1], dx = Math.abs(x2 - x1), dy = y2 - y1; if (Math.abs(dy) < ε) { // 0° var y = y0 < y1 ? -Z : Z; polygon.push([-Z, y], [Z, y]); } else if (dx < ε) { // ±90° var x = x0 < x1 ? -Z : Z; polygon.push([x, -Z], [x, Z]); } else { var y = (x2 - x1) * (y1 - y0) < (x1 - x0) * (y2 - y1) ? Z : -Z, z = Math.abs(dy) - dx; if (Math.abs(z) < ε) { // ±45° polygon.push([dy < 0 ? y : -y, y]); } else { if (z > 0) y *= -1; polygon.push([-Z, y], [Z, y]); } } }); if (clipPolygon) for (i = 0; i < n; ++i) clipPolygon.clip(polygons[i]); for (i = 0; i < n; ++i) polygons[i].point = data[i]; return polygons; } voronoi.x = function(_) { return arguments.length ? (x = _, voronoi) : x; }; voronoi.y = function(_) { return arguments.length ? (y = _, voronoi) : y; }; voronoi.clipExtent = function(_) { if (!arguments.length) return clipPolygon && [clipPolygon[0], clipPolygon[2]]; if (_ == null) clipPolygon = null; else { var x1 = +_[0][0], y1 = +_[0][1], x2 = +_[1][0], y2 = +_[1][1]; clipPolygon = d3.geom.polygon([[x1, y1], [x1, y2], [x2, y2], [x2, y1]]); } return voronoi; }; // @deprecated; use clipExtent instead voronoi.size = function(_) { if (!arguments.length) return clipPolygon && clipPolygon[2]; return voronoi.clipExtent(_ && [[0, 0], _]); }; voronoi.links = function(data) { var points, graph = data.map(function() { return []; }), links = [], fx = d3_functor(x), fy = d3_functor(y), d, i, n = data.length; if (fx === d3_svg_lineX && fy === d3_svg_lineY) points = data; else for (points = new Array(n), i = 0; i < n; ++i) { points[i] = [+fx.call(this, d = data[i], i), +fy.call(this, d, i)]; } d3_geom_voronoiTessellate(points, function(e) { var l = e.region.l.index, r = e.region.r.index; if (graph[l][r]) return; graph[l][r] = graph[r][l] = true; links.push({source: data[l], target: data[r]}); }); return links; }; voronoi.triangles = function(data) { if (x === d3_svg_lineX && y === d3_svg_lineY) return d3.geom.delaunay(data); var points = new Array(n), fx = d3_functor(x), fy = d3_functor(y), d, i = -1, n = data.length; while (++i < n) { (points[i] = [+fx.call(this, d = data[i], i), +fy.call(this, d, i)]).data = d; } return d3.geom.delaunay(points).map(function(triangle) { return triangle.map(function(point) { return point.data; }); }); }; return voronoi;
};
var d3_geom_voronoiOpposite = {l: “r”, r: “l”};
function d3_geom_voronoiTessellate(points, callback) {
var Sites = { list: points .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_geom_voronoiOpposite[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_geom_voronoiOpposite[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(); var newSite = Sites.list.shift(), newIntStar; var lbnd, rbnd, llbnd, rrbnd, bisector; var bot, top, temp, p, v; var e, pm; while (true) { if (!EventQueue.empty()) { newIntStar = EventQueue.min(); } if (newSite && (EventQueue.empty() || newSite.y < newIntStar.y || (newSite.y == newIntStar.y && newSite.x < newIntStar.x))) { //new site is smallest lbnd = EdgeList.leftBound(newSite); rbnd = EdgeList.right(lbnd); bot = EdgeList.rightRegion(lbnd); e = Geom.bisect(bot, newSite); bisector = EdgeList.createHalfEdge(e, "l"); EdgeList.insert(lbnd, bisector); p = Geom.intersect(lbnd, bisector); if (p) { EventQueue.del(lbnd); EventQueue.insert(lbnd, p, Geom.distance(p, newSite)); } lbnd = bisector; bisector = EdgeList.createHalfEdge(e, "r"); EdgeList.insert(lbnd, bisector); p = Geom.intersect(bisector, rbnd); if (p) { EventQueue.insert(bisector, p, Geom.distance(p, newSite)); } newSite = Sites.list.shift(); } else if (!EventQueue.empty()) { //intersection is smallest lbnd = EventQueue.extractMin(); llbnd = EdgeList.left(lbnd); rbnd = EdgeList.right(lbnd); rrbnd = EdgeList.right(rbnd); bot = EdgeList.leftRegion(lbnd); top = EdgeList.rightRegion(rbnd); v = lbnd.vertex; Geom.endPoint(lbnd.edge, lbnd.side, v); Geom.endPoint(rbnd.edge, rbnd.side, v); EdgeList.del(lbnd); EventQueue.del(rbnd); EdgeList.del(rbnd); pm = "l"; if (bot.y > top.y) { temp = bot; bot = top; top = temp; pm = "r"; } e = Geom.bisect(bot, top); bisector = EdgeList.createHalfEdge(e, pm); EdgeList.insert(llbnd, bisector); Geom.endPoint(e, d3_geom_voronoiOpposite[pm], v); p = Geom.intersect(llbnd, bisector); if (p) { EventQueue.del(llbnd); EventQueue.insert(llbnd, p, Geom.distance(p, bot)); } p = Geom.intersect(bisector, rrbnd); if (p) { EventQueue.insert(bisector, p, Geom.distance(p, bot)); } } else { break; } }//end while for (lbnd = EdgeList.right(EdgeList.leftEnd); lbnd != EdgeList.rightEnd; lbnd = EdgeList.right(lbnd)) { callback(lbnd.edge); }
}