block by renecnielsen d6999bd59c003fdd930a1e11e12f024a

Go Logo - Mitchell's Best Candidate Bounded

Full Screen

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

index.html

<!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>