Skip to content

Instantly share code, notes, and snippets.

@renecnielsen
Last active January 31, 2017 20:18
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 renecnielsen/d6999bd59c003fdd930a1e11e12f024a to your computer and use it in GitHub Desktop.
Save renecnielsen/d6999bd59c003fdd930a1e11e12f024a to your computer and use it in GitHub Desktop.
Go Logo - Mitchell's Best Candidate Bounded
license: mit

Visualising the IFRC Go Logo using the Mitchell’s best-candidate algorithm to place the circles.

Forked from philipcdavis's block: Mitchell's Best Candidate Bounded, which in turn is based on Mike Bostock's example.

Mike Bostock's description: "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."

forked from renecnielsen's block: Go Logo - Mitchell's Best Candidate Bounded

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>GO! Logo</title>
</head>
<style>
canvas {
margin: 0 auto;
display: block;
}
</style>
<body>
<div id="chart"></div>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
<script type="text/javascript">
var chart = d3.select("#chart");
var canvas = chart.append("canvas");
canvas.node().width = 1000;
canvas.node().height = 1000;
canvas.node().style.width = "960px";
canvas.node().style.height = "960px";
canvas.node().getContext('2d').scale(2,2);
var context = canvas.node().getContext("2d");
var go = new Path2D("M151.28,149a17.1,17.1,0,0,0-6.32,1.22l-16.54-27.63a23.23,23.23,0,0,0-12.24-40.8V71a17.21,17.21,0,1,0-5.58,0V81.82a23.23,23.23,0,0,0-12.24,40.8L81.81,150.26a17.24,17.24,0,1,0,4.79,2.87L103,125.69a23.07,23.07,0,0,0,20.73,0l16.43,27.43A17.19,17.19,0,1,0,151.28,149Zm-75.8,28.84a11.63,11.63,0,1,1,11.63-11.63A11.64,11.64,0,0,1,75.49,177.88ZM101.75,54.07A11.63,11.63,0,1,1,113.39,65.7,11.65,11.65,0,0,1,101.75,54.07Zm-4.27,50.83a15.9,15.9,0,1,1,15.9,15.9A15.9,15.9,0,0,1,97.48,104.89Zm53.8,73a11.63,11.63,0,1,1,11.63-11.63A11.64,11.64,0,0,1,151.28,177.88Z");
// forked from @mbostock's example
// https://bl.ocks.org/mbostock/6224050
var maxRadius = 3, // maximum radius of circle
padding = 1, // padding between circles; also minimum radius
margin = {top: -maxRadius, right: -maxRadius, bottom: -maxRadius, left: -maxRadius},
width = 500 - margin.left - margin.right,
height = 500 - margin.top - margin.bottom;
var k = 1, // initial number of candidates to consider per circle
m = 20, // initial number of circles to add per frame
n = 15000, // remaining number of circles to add
newCircle = bestCircleGenerator(maxRadius, padding);
var timer = d3.timer(function(elapsed) {
if (elapsed > 20000) timer.stop();
for (var i = 0; i < m && --n >= 0; ++i) {
var circle = newCircle(k);
context.beginPath();
context.arc(circle[0], circle[1], circle[2], 0, 2 * Math.PI, false);
context.fillStyle = d3.interpolateReds(Math.random());
context.fill();
}
return !n;
});
function bestCircleGenerator(maxRadius, padding) {
var quadtree = d3.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;
var y = Math.random() * height;
// Check if point is in the SVG path
if (!context.isPointInPath(go, x, y)) {
do {
x = Math.random() * width;
y = Math.random() * height;
} while (!context.isPointInPath(go, x, y))
}
var rx1 = x - searchRadius,
rx2 = x + searchRadius,
ry1 = y - searchRadius,
ry2 = y + searchRadius,
minDistance = maxRadius; // minimum distance for this candidate
quadtree.visit(function(node, x1, y1, x2, y2) {
if (p = node.data) {
var p,
dx = x - p[0],
dy = y - p[1],
d2 = dx * dx + dy * dy;
r2 = 10;
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>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment