How to make randomly distributed points less random and more evenly spread out.
With only random distribution the results can include overlapping points, clusters of points and a somewhat uneven distribution throughout the grid. If you needed a more even distribution you could check each new point against every other point to prevent overlaps or clustering. This has an exponential problem O(n2) and makes the algorithm unscalable and inefficient. The solution is the Poisson Disc Sampling Algorithm.
Here we can see a considerably more even, yet still random distribution of points. By using a background grid method each new point can easily check its immediate neighbours without having to worry about all the points on the grid. This makes the algorithm much faster and scalable and is now an O(2n) operation.
Draw random points with a minimum separation of (r)
Watch the algorithm solve the puzzle one step at a time. Red points are Active and will be visited again to check if another point can be inserted nearby. Once the algorithm has decided a point cannot have any more neighbours it changes to black and becomes a fixed, closed point on the grid. Once there are no more Active points the solution has been reached.
r - The minimum distance between points.
k - The number of attempts to create a new point before deciding the current point should be closed.
n - The number of dimensions the grid has. This algorithm can distribute points in 3d, 4d, 5d etc. I'll do another example for 3d.
cell size - The size of the grid cells is calculated by r / sqrt(n)
The algorithm takes as input the extent of the sample domain in Rn, the minimum distance r between samples, and a constant k as the limit of samples to choose before rejection in the algorithm (typically k = 30).
Step 0. Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by r/√n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple n-dimensional array of integers: the default −1 indicates no sample, a non-negative integer gives the index of the sample located in a cell.
Step 1. Select the initial sample, x0, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list” (an array of sample indices) with this index (zero).
Step 2. While the active list is not empty, choose a random index from it (say i). Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around xi. For each point in turn, check if it is within distance r of existing samples (using the background grid to only test nearby samples). If a point is adequately far from existing samples, emit it as the next sample and add it to the active list. If after k attempts no such point is found, instead remove i from the active list
let width = 400;
let height = 400;
let r = 25;
let k = 30;
let n = 2;
let myPoisson = new PoissonDisc(width, height, r, k, n);
myPoisson.run();
Points are available in the myPoisson.points array. Point.px and Point.py are the x and y position.
Please visit GitHub to download the full source code. Released as public domain for anyone to use.
Fast Poisson Disc Sampling in Arbitrary Dimensions By Robert Bridson ~ University of British Columbia
Download the PDF
Thanks to all the internet people who posted the videos, articles and examples for me to learn from. Hopefully this example can add to that knowledge base for future coders. Inspired by The Coding Train poisson video.