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(n ^{2})* 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 *R ^{n}*,
the minimum distance

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, *x _{0}*, 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 *x _{i}*. For each
point in turn, check if it is within distance

```
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.