Skip to content

Instantly share code, notes, and snippets.

@mbostock
Forked from mbostock/.block
Last active November 28, 2019 19:58
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mbostock/6224050 to your computer and use it in GitHub Desktop.
Mitchell’s Best-Candidate
license: gpl-3.0
redirect: https://observablehq.com/@mbostock/best-candidate-circles
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
background: #333;
}
circle {
fill: #fff;
stroke: #000;
stroke-width: 1.5px;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.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)
.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