Mitchell’s Best-Candidate II

An animation of Mitchell’s best-candidate algorithm, which produces samples with blue-noise spectral characteristics that are useful for minimizing aliasing. Unlike uniform random sampling, best-candidate samples are more evenly distributed, with fewer samples close together. (A similar, but more efficient, algorithm is poisson-disc sampling.)

For each new sample, the best-candidate algorithm generates a fixed number of candidate samples, shown in gray. Here, 10 candidates are generated. The best candidate, shown in red, is the one that is farthest away from all previous (non-candidate) samples.

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.point {
  fill: #000;
}

.candidate .point {
  fill: #aaa;
  transition: fill 250ms linear;
}

.candidate .search {
  fill: none;
  stroke: #aaa;
  transition: stroke 250ms linear, stroke-width 250ms linear;
}

.candidate--best .point {
  fill: #f00;
}

.candidate--best .search {
  stroke: #f00;
  stroke-width: 1.5px;
}

</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 500;

var k = 10; // number of candidates to consider per circle

var quadtree = d3.geom.quadtree()
    .extent([[0, 0], [width, height]])
    ([[Math.random() * width, Math.random() * height]]);

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

var gCandidate = svg.append("g")
    .attr("class", "candidate");

var gPoint = svg.append("g")
    .attr("class", "point");

gPoint.append("circle")
    .attr("r", 3.5)
    .attr("cx", quadtree.point[0])
    .attr("cy", quadtree.point[1]);

(function nextPoint() {
  var i = 0,
      maxDistance = -Infinity,
      bestCandidate = null;

(function nextCandidate() {
    if (++i > k) {
      gCandidate.selectAll("*").transition()
          .style("opacity", 0)
          .remove();

gPoint.append("circle")
          .attr("r", 3.5)
          .attr("cx", bestCandidate.__data__[0])
          .attr("cy", bestCandidate.__data__[1]);

quadtree.add(bestCandidate.__data__);

return nextPoint();
    }

var x = Math.random() * width,
        y = Math.random() * height,
        closest = search(x, y),
        dx = closest[0] - x,
        dy = closest[1] - y,
        distance = Math.sqrt(dx * dx + dy * dy);

var g = gCandidate.insert("g", "*")
        .datum([x, y])
        .attr("class", "candidate--current");

g.append("circle")
        .attr("class", "point")
        .attr("r", 3.5)
        .attr("cx", x)
        .attr("cy", y);

g.append("circle")
        .attr("class", "search")
        .attr("r", 2.5)
        .attr("cx", x)
        .attr("cy", y);

g.append("line")
        .attr("class", "search")
        .attr("x1", x)
        .attr("y1", y)
        .attr("x2", x)
        .attr("y2", y);

t.select("circle.search")
        .attr("r", distance);

t.select("line.search")
        .attr("x2", closest[0])
        .attr("y2", closest[1]);
  })();

})();

// Find the closest node to the specified point.
function search(x, y) {
  var x0 = 0,
      y0 = 0,
      x3 = width,
      y3 = width,
      minDistance2 = Infinity,
      closestPoint;

(function find(node, x1, y1, x2, y2) {
    var point;

// stop searching if this cell can’t contain a closer node
    if (x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) return;

// visit this point
    if (point = node.point) {
      var dx = x - point[0],
          dy = y - point[1],
          distance2 = dx * dx + dy * dy;
      if (distance2 < minDistance2) {
        var distance = Math.sqrt(minDistance2 = distance2);
        x0 = x - distance, y0 = y - distance;
        x3 = x + distance, y3 = y + distance;
        closestPoint = point;
      }
    }

// bisect the current node
    var children = node.nodes,
        xm = (x1 + x2) * .5,
        ym = (y1 + y2) * .5,
        right = x > xm,
        below = y > ym;

// visit closest cell first
    if (node = children[below << 1 | right]) find(node, right ? xm : x1, below ? ym : y1, right ? x2 : xm, below ? y2 : ym);
    if (node = children[below << 1 | !right]) find(node, right ? x1 : xm, below ? ym : y1, right ? xm : x2, below ? y2 : ym);
    if (node = children[!below << 1 | right]) find(node, right ? xm : x1, below ? y1 : ym, right ? x2 : xm, below ? ym : y2);
    if (node = children[!below << 1 | !right]) find(node, right ? x1 : xm, below ? y1 : ym, right ? xm : x2, below ? ym : y2);
  })(quadtree, x0, y0, x3, y3);

return closestPoint;
}

</script>

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