Mitchell’s Best-Candidate

A Delaunay variation of the Mitchell’s best-candidate explanation.

Note: this would be much more efficient if the Delaunay triangulation were computed incrementally for just the additional points added each frame.

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 500;

var k = 20 // number of candidates to consider per point
    m = 10, // initial number of points to add per frame
    n = 2500, // remaining number of points to add
    newPoint = bestPointGenerator(32),
    points = [];

var voronoi = d3.geom.voronoi()
    .clipExtent([[-1, -1], [width + 1, height + 1]]);

var canvas = d3.select("body").append("canvas")
    .attr("width", width)
    .attr("height", height);

var context = canvas.node().getContext("2d");

d3.timer(function() {
  var n0 = points.length;

for (var i = 0; i < m && --n >= 0; ++i) {
    points.push(newPoint(k));

// As we add more circles, gradually reduce circles per frame.
    if (m > 1) m *= .998;
  }

var links = voronoi.links(points);
  context.clearRect(0, 0, width, height);
  context.beginPath();
  for (var i = 0, link, l = links.length; i < l; ++i) {
    link = links[i];
    context.moveTo(link.source[0], link.source[1]);
    context.lineTo(link.target[0], link.target[1]);
  }
  context.closePath();
  context.stroke();

return !n;
});

function bestPointGenerator(searchRadius) {
  var quadtree = d3.geom.quadtree().extent([[0, 0], [width, height]])([]);

return function(k) {
    var bestX, bestY, bestDistance = 0;

for (var i = 0; i < k; ++i) {
      var x = Math.random() * width,
          y = Math.random() * height,
          rx1 = x - searchRadius,
          rx2 = x + searchRadius,
          ry1 = y - searchRadius,
          ry2 = y + searchRadius,
          minDistance = Infinity; // 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,
              d = Math.sqrt(d2);
          if (d < minDistance) {
            minDistance = d;
            rx1 = x - d;
            rx2 = x + d;
            ry1 = y - d;
            ry2 = y + d;
          }
        }
        return 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];
    quadtree.add(best);
    return best;
  };
}

</script>

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