“Random” points on a plane

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

  • place objects in a game world (trees in a forest, grass and rocks in a field, etc);
  • generate points for Voronoi diagram (to get 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.

NNNN points

Jittered grid

Grids give even distribution, but the picture will not look random. We can add a small displacement to every point and that will give a much better randomized picture.

NNNN points

The max displacement should be slightly less than half of distance between 2 diagonal neibouring points. This will ensure that each point will stay relatively close to the original position, but still shiftted enough to form random picture.

Pros:

  • points are distributed fairy evenly: no major gaps and no major clusters;
  • each point can be referenced by the original grid point (via an index or coordinates);

Cons:

  • some points can still be too close to each other (forming small clusters);
  • some points may fall of the canvas due to shift (the shift can be re-generated increasing the risk of clusters)

Poisson disk distribution

Another solution is Poisson disk sampling (or Poisson disk distribution): points are placed randomly, maintaining the minimum distance and not too far away from each other.

NNNN points

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”);

Other options

There are other ways to generate evenly distributed random points (see this blog post):

  • use noise;
  • Lloyd’s relaxation: apply a few iterations of Lloyd algorithm to move points away from each other;