Mike Bostock

File Not Found

Unfortunately, the page you were looking for does not appear to exist. Instead, here is a pleasing demonstration of Mitchell’s best-candidate algorithm.

The best-candidate algorithm generates a new random sample by creating k candidate samples and picking the one with the highest score: the one farthest from previous samples. The algorithm approximates Poisson-disc sampling, producing a more natural appearance (better blue noise spectral characteristics) than uniform random sampling. This has a variety of useful applications in computer graphics, such as reducing Moiré patterns in supersampling raytracers.

In pseudo-code:

function bestCandidate(k) {
  var bestScore = 0,
      bestCandidate;

  // Generate k random candidates.
  for (var i = 0; i < k; ++i) {
    var c = randomCandidate();

    // Determine if the current candidate is the new best.
    var s = score(c);
    if (s > bestScore) {
      bestScore = s;
      bestCandidate = c;
    }
  }

  return bestCandidate;
}

This implementation depends on an external function score which computes the minimum distance between the new candidate c and all previous samples. The naïve implementation is expensive, since it iterates over all previous samples for each new sample! Fortunately, data structures such as quadtrees can accelerate these tests by skipping samples that are far away.