Natural object placement with Poisson Disk Sampling

I recently came across a tweet from Pico Tanks on where they create regions, defined by a shape, where players can hide. What stands out to me the most, is how the trees in those regions never seem to overlap. After looking more into this, I found an algorithm called Poisson disk sampling.

Trees placed using Poisson Disk Sampling.

Poisson Disk sampling

The reason why Poisson disk sampling produces a natural pattern is the way the points are generated. Instead of generating a random X and Y coordinate, each point is generated between a minimum and maximum distance between each other.

Points generated with random X and Y coordinates.
Points generated with Poisson Disk Sampling. All of the points are distributed evenly with at least 2 units apart from each other.

How it works

Before we start generating the points we have to set up all the needed inputs. The algorithm itself only takes in r and k as input. r is the minimum distance between the samples and k is a constant which is the maximum samples before rejection. First, we initialize a 2D grid for storing the samples.
The cell size of this grid is bounded by r/√n where n is the number of dimensions (2 in this case) so that each cell will contain at most 1 sample.

In step 1 we generate the initial sample that is randomly chosen from the domain. This sample is inserted into the grid and added to the active list, this active list holds the current samples which we generate new samples from.

After we have our initial sample, while the active list is not empty, we choose a random index from that list and generate up to k points around it. These points lay between r and 2*r distance from the current index. For each point, we check if it is between r distance from any of the samples saved in the grid and since the points are generated between r and 2*r, we can skip unnecessary checks by only checking the neighboring cells of the current index. If we found a point that is adequately far from existing samples, we save it to the grid and the active list. If after k samples, no such points are found, we remove the current index from the active list.

Checking which points are inside the shape

To know which points are inside the shape, I found a very fast and short algorithm on the Unity3D wiki.
The basic idea is to run a semi-infinite ray horizontally out from the test point and count how many edges it crosses.
At each crossing, a boolean is switched between true and false. At the end of the ray, this boolean is returned.

References

Poisson Disk Sampling in Arbitrary Dimensions
Poly contains point from Wiki.Unity3d