Go Logo - Mitchell's Best Candidate Bounded

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."

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>GO! Logo</title>
  </head>

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("M113.39,11.34a102,102,0,1,0,102,102A102,102,0,0,0,113.39,11.34Zm38.09,172.49a17.29,17.29,0,0,1-11.17-30.49L123.8,125.75a23.19,23.19,0,0,1-20.83,0L86.46,153.33a17.37,17.37,0,1,1-4.81-2.88l16.63-27.78a23.35,23.35,0,0,1,12.3-41V70.81a17.3,17.3,0,1,1,5.61,0V81.66a23.35,23.35,0,0,1,12.3,41l16.63,27.78a17.29,17.29,0,1,1,6.36,33.38Z");
    // 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>

https://d3js.org/d3.v4.min.js

https://d3js.org/d3-scale-chromatic.v1.min.js