Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active February 9, 2016 01:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mbostock/981b42034400e48ac637 to your computer and use it in GitHub Desktop.
Save mbostock/981b42034400e48ac637 to your computer and use it in GitHub Desktop.
Mitchell’s Best-Candidate III
license: gpl-3.0
<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var width = 960,
height = 500;
var sample = bestCandidateSampler(width, height, 10, 3000);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
d3.timer(function() {
for (var i = 0; i < 10; ++i) {
var s = sample();
if (!s) return true;
svg.append("circle")
.attr("cx", s[0])
.attr("cy", s[1])
.attr("r", 0)
.transition()
.attr("r", 2);
}
});
function bestCandidateSampler(width, height, numCandidates, numSamplesMax) {
var numSamples = 0;
var quadtree = d3.geom.quadtree()
.extent([[0, 0], [width, height]])
([[Math.random() * width, Math.random() * height]]);
return function() {
if (++numSamples > numSamplesMax) return;
var bestCandidate, bestDistance = 0;
for (var i = 0; i < numCandidates; ++i) {
var c = [Math.random() * width, Math.random() * height],
d = distance(search(c[0], c[1]), c);
if (d > bestDistance) {
bestDistance = d;
bestCandidate = c;
}
}
quadtree.add(bestCandidate);
return bestCandidate;
};
function distance(a, b) {
var dx = a[0] - b[0],
dy = a[1] - b[1];
return dx * dx + dy * dy;
};
// Find the closest node to the specified point.
function search(x, y) {
var x0 = 0,
y0 = 0,
x3 = width,
y3 = width,
minDistance2 = Infinity,
closestPoint;
(function find(node, x1, y1, x2, y2) {
var point;
// stop searching if this cell can’t contain a closer node
if (x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) return;
// visit this point
if (point = node.point) {
var dx = x - point[0],
dy = y - point[1],
distance2 = dx * dx + dy * dy;
if (distance2 < minDistance2) {
var distance = Math.sqrt(minDistance2 = distance2);
x0 = x - distance, y0 = y - distance;
x3 = x + distance, y3 = y + distance;
closestPoint = point;
}
}
// bisect the current node
var children = node.nodes,
xm = (x1 + x2) * .5,
ym = (y1 + y2) * .5,
right = x > xm,
below = y > ym;
// visit closest cell first
if (node = children[below << 1 | right]) find(node, right ? xm : x1, below ? ym : y1, right ? x2 : xm, below ? y2 : ym);
if (node = children[below << 1 | !right]) find(node, right ? x1 : xm, below ? ym : y1, right ? xm : x2, below ? y2 : ym);
if (node = children[!below << 1 | right]) find(node, right ? xm : x1, below ? y1 : ym, right ? x2 : xm, below ? ym : y2);
if (node = children[!below << 1 | !right]) find(node, right ? x1 : xm, below ? y1 : ym, right ? xm : x2, below ? ym : y2);
})(quadtree, x0, y0, x3, y3);
return closestPoint;
}
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment