Mitchell’s Best-Candidate

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

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

<!DOCTYPE html>
<meta charset="utf-8">
<canvas width="960" height="500"></canvas>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>

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 canvas = d3.select("canvas").node(),
    context = canvas.getContext("2d"),
    width = canvas.width,
    height = canvas.height;

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

context.strokeStyle = "#000";
context.fillStyle = "#fff";

var timer = 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 *= 0.998;
  }

var cells = voronoi.polygons(points);

for (var n1 = points.length, cell; n0 < n1; ++n0) {
    cell = cells[n0];
    context.beginPath();
    context.moveTo(cell[0][0], cell[0][1]);
    for (var i = 1, l = cell.length; i < l; ++i) context.lineTo(cell[i][0], cell[i][1]);
    context.closePath();
    context.fill();
    context.stroke();
  }

if (!n) timer.stop();
});

</script>

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