Added hover highlighting to Voronoi Mitchell’s best-candidate by searching for the closest point with d3.geom.quadtree.
An improvement would be rendering highlighted cells in a separate canvas, so that they could be cleared without redrawing the entire Voronoi. This version leaves artifacts behind which get eaten away by new voronoi cells.
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <body> | |
| <script src="http://d3js.org/d3.v3.js"></script> | |
| <script> | |
| var width = 960, | |
| height = 500; | |
| var k = 20 // number of candidates to consider per point | |
| m = 10, // initial number of points to add per frame | |
| n = 2500, // remaining number of points to add | |
| newPoint = bestPointGenerator(32), | |
| points = [], | |
| voronoi = d3.geom.voronoi().clipExtent([[-1, -1], [width + 1, height + 1]]), | |
| cells = voronoi(points), | |
| quadtree = d3.geom.quadtree().extent([[0, 0], [width, height]])([]); | |
| var canvas = d3.select("body").append("canvas") | |
| .attr("width", width) | |
| .attr("height", height) | |
| .on("mousemove", function(x) { | |
| if (cells.length < 1) return; | |
| var pos = d3.mouse(this); | |
| var closestPoint = [Infinity, Infinity]; | |
| var minDistance = Infinity; | |
| // search for closest point | |
| quadtree.visit(function(quad, x1, y1, x2, y2) { | |
| var rx1 = pos[0] - minDistance, | |
| rx2 = pos[0] + minDistance, | |
| ry1 = pos[1] - minDistance, | |
| ry2 = pos[1] + minDistance; | |
| if (p = quad.point) { | |
| var p, | |
| dx = pos[0] - p[0], | |
| dy = pos[1] - p[1], | |
| d2 = dx * dx + dy * dy, | |
| d = Math.sqrt(d2); | |
| if (d < minDistance) { | |
| closestPoint = p; | |
| minDistance = d; | |
| } | |
| } | |
| return x1 > rx2 || x2 < rx1 || y1 > ry2 || y2 < ry1; // bounding box outside closest point | |
| }); | |
| // render highlighted point | |
| var closestPointIndex = points.indexOf(closestPoint); | |
| context.fillStyle = "#aaa"; | |
| drawCell(cells[closestPointIndex]); | |
| context.fillStyle = "#fff"; | |
| }); | |
| var context = canvas.node().getContext("2d"); | |
| context.strokeStyle = "#999"; | |
| context.fillStyle = "#fff"; | |
| d3.timer(function() { | |
| var n0 = points.length; | |
| for (var i = 0; i < m && --n >= 0; ++i) { | |
| points.push(newPoint(k)); | |
| // As we add more circles, gradually reduce circles per frame. | |
| if (m > 1) m *= .998; | |
| } | |
| cells = voronoi(points); | |
| for (var n1 = points.length, cell; n0 < n1; ++n0) { | |
| drawCell(cells[n0]); | |
| } | |
| return !n; | |
| }); | |
| function drawCell(cell) { | |
| context.beginPath(); | |
| context.moveTo(cell[0][0], cell[0][1]); | |
| for (var i = 1, l = cell.length; i < l; ++i) context.lineTo(cell[i][0], cell[i][1]); | |
| context.closePath(); | |
| context.fill(); | |
| context.stroke(); | |
| }; | |
| function bestPointGenerator(searchRadius) { | |
| return function(k) { | |
| var bestX, bestY, bestDistance = 0; | |
| for (var i = 0; i < k; ++i) { | |
| var x = Math.random() * width, | |
| y = Math.random() * height, | |
| rx1 = x - searchRadius, | |
| rx2 = x + searchRadius, | |
| ry1 = y - searchRadius, | |
| ry2 = y + searchRadius, | |
| minDistance = searchRadius; // minimum distance for this candidate | |
| quadtree.visit(function(quad, x1, y1, x2, y2) { | |
| if (p = quad.point) { | |
| var p, | |
| dx = x - p[0], | |
| dy = y - p[1], | |
| d2 = dx * dx + dy * dy, | |
| d = Math.sqrt(d2); | |
| if (d < minDistance) { | |
| minDistance = d; | |
| rx1 = x - d; | |
| rx2 = x + d; | |
| ry1 = y - d; | |
| ry2 = y + d; | |
| } | |
| } | |
| return x1 > rx2 || x2 < rx1 || y1 > ry2 || y2 < ry1; // or outside search radius | |
| }); | |
| if (minDistance > bestDistance) bestX = x, bestY = y, bestDistance = minDistance; | |
| } | |
| var best = [bestX, bestY]; | |
| quadtree.add(best); | |
| return best; | |
| }; | |
| } | |
| </script> |
