|
<!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> |