“Random” points on a plane

We need to generate random, evenly distributed points on a plane. Possible use-cases:

  • generate trees in a forest in a game world;
  • generate points for Voronoi diagram (with areas of similar size);

The simplest approach - to use uniformly distributed points with (random(), random()) - doesn’t work, because there will be areas with high density of points and areas with no points at all. Such distribution doesn’t look natural.

Caption

Various types of grids with gaps can give even distribution, but the picture will not look random. There will always be a pattern, sometimes more visible, sometimes less, but still visible. This doesn’t look natural either.

A solution to this problem is Poisson disk sampling (or Poisson disk distribution): points are placed randomly, but not too close and not too far away from each other.

Caption

This article compares randomly placed points with Poisson disk distribution, and shows “best candidate” and Bridson’s algorithms to build such distribution (with great examples and visualizations).

Bridson’s algorithm for Poisson disk sampling

Summary of this page. Bridson’s algorithm allows us to generate random points with Poisson disk distribution.

Formal problem description: generate tightly packed random points maintaining minimal distance between them.

Algorithm parameters:

  1. area where points should be generated;
  2. r - minimum distance between any 2 points;
  3. k - amount of attempts to generate a new point;

The algorithm uses a grid with r/sqrt(2) cell size. There could be at most 1 point in any grid cell. The value of a cell is either an index of a generated point or -1.

The algorithm:

  1. initialize the grid that covers the requested area with -1 in each cell;
  2. generate an initial point p0 and set the corresponding grid cell to 0 (the first point); initialize a list of active points with index 0;
  3. pick a random index from active points (let’s say p-i). Generate up to k random points in annulus between r and 2r form the selected point p-i; test every generated point if it’s far enough (dist >=r) from already existing points (use the grid to test only nearby cells);
    • if a generated point is far enough from all existing points, add it to the list of generated points, update the grid cell with its index and add this new point to active points;
    • if all k points are too close to already existing points, then remove p-i from active points;
  4. repeat until list of active points is empty;

Side notes:

  • complexity is O(N);
  • easy to implement;
  • the cluster of points grows naturally from the starting point to all directions;
  • easily extensible to 3D (and more dimensional) space;
  • the number of points is not known until the generation process is complete (it’s “generate some points with specific condition” rather than “generate N points”);