Skip to content

Instantly share code, notes, and snippets.

@roxlu roxlu/README.md forked from mbostock/.block
Created Feb 23, 2014

Embed
What would you like to do?

Mitchell’s best-candidate algorithm generates a new random sample by creating k candidate samples and picking the best of k. Here the “best” sample is defined as the sample that is farthest away from previous samples. The algorithm approximates Poisson-disc sampling, producing a much more natural appearance (better blue noise spectral characteristics) than uniform random sampling.

See also the white-on-black and Voronoi variations of this example.

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="http://d3js.org/d3.v3.js"></script>
<script>
var maxRadius = 32, // maximum radius of circle
padding = 1, // padding between circles; also minimum radius
margin = {top: -maxRadius, right: -maxRadius, bottom: -maxRadius, left: -maxRadius},
width = 960 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
var k = 1, // initial number of candidates to consider per circle
m = 10, // initial number of circles to add per frame
n = 2500, // remaining number of circles to add
newCircle = bestCircleGenerator(maxRadius, padding);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
d3.timer(function() {
for (var i = 0; i < m && --n >= 0; ++i) {
var circle = newCircle(k);
svg.append("circle")
.attr("cx", circle[0])
.attr("cy", circle[1])
.attr("r", 0)
.style("fill-opacity", (Math.random() + .5) / 2)
.transition()
.attr("r", circle[2]);
// As we add more circles, generate more candidates per circle.
// Since this takes more effort, gradually reduce circles per frame.
if (k < 500) k *= 1.01, m *= .998;
}
return !n;
});
function bestCircleGenerator(maxRadius, padding) {
var quadtree = d3.geom.quadtree().extent([[0, 0], [width, height]])([]),
searchRadius = maxRadius * 2,
maxRadius2 = maxRadius * maxRadius;
return function(k) {
var bestX, bestY, bestDistance = 0;
for (var i = 0; i < k || bestDistance < padding; ++i) {
var x = Math.random() * width,
y = Math.random() * height,
rx1 = x - searchRadius,
rx2 = x + searchRadius,
ry1 = y - searchRadius,
ry2 = y + searchRadius,
minDistance = maxRadius; // 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,
r2 = p[2] * p[2];
if (d2 < r2) return minDistance = 0, true; // within a circle
var d = Math.sqrt(d2) - p[2];
if (d < minDistance) minDistance = d;
}
return !minDistance || 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, bestDistance - padding];
quadtree.add(best);
return best;
};
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.