Skip to content

Instantly share code, notes, and snippets.

@mbostock
Forked from mbostock/.block
Last active February 9, 2016 02:02
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mbostock/6225662 to your computer and use it in GitHub Desktop.
Mitchell’s Best-Candidate
license: gpl-3.0

A Delaunay variation of the Mitchell’s best-candidate explanation.

Note: this would be much more efficient if the Delaunay triangulation were computed incrementally for just the additional points added each frame.

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="//d3js.org/d3.v3.min.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 = [];
var voronoi = d3.geom.voronoi()
.clipExtent([[-1, -1], [width + 1, height + 1]]);
var canvas = d3.select("body").append("canvas")
.attr("width", width)
.attr("height", height);
var context = canvas.node().getContext("2d");
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;
}
var links = voronoi.links(points);
context.clearRect(0, 0, width, height);
context.beginPath();
for (var i = 0, link, l = links.length; i < l; ++i) {
link = links[i];
context.moveTo(link.source[0], link.source[1]);
context.lineTo(link.target[0], link.target[1]);
}
context.closePath();
context.stroke();
return !n;
});
function bestPointGenerator(searchRadius) {
var quadtree = d3.geom.quadtree().extent([[0, 0], [width, height]])([]);
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 = Infinity; // 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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment