Introduction
This time, you get to know a useful algorithm for distributing points on an area resp. for analyzing images: the Poisson disc algorithm.
Background
The Poisson disc algorithm distributes points on an image in a relatively chaotic way like this:
That can be very useful in many areas of image processing and artwork creation (see below).
Basic Approach
For the creation of a Poisson disc distribution, you need the following steps:
- Define your desired minimal distance between the points,
- Define a grid of sections on your output canvas with a gridsize of your minimal distance divided by the square root of 2,
- Create an empty list of "active points" (for working) and "valid points" (for the result),
- Add a first random point from the canvas to your list of active points,
- [REPEAT] Select a random point from your list of active points (at the very beginning, it will be the start point),
- Find new random points around the selected point, which are away from it at least your minimal distance and not more than twice your minimal distance (i.e. within a specific range of a "disc"),
- Add each of the new valid points to your list of active points (and valid points), if it is not too close to other neighbour points,
- Remove the selected point from your list of active points,
- Repeat the procedure with the remaining points in your list of active points until this list of active points is empty,
- Finally return the result of valid points.
Algorithm in Detail
You start with the definition of your desired minimal distance between the points (parameter MinDistance) and the definition of a Grid of sections on your output canvas with a gridCellSize of your minimal distance divided by the square root of 2:
private static Point?[,] Grid;
public static PointCollection Points(double Width, double Height, int MinDistance,
int PointsPerAttempt, double Margin)
{
int gridCellSize = (int)(MinDistance / Math.Sqrt(2));
Grid = new Point?[(int)(Width / gridCellSize) + 1, (int)(Height / gridCellSize) + 1];
}
The Grid represents null or one Point in each of its cells. Finally, there will be a maximum of one point in each of these sections of the canvas:
Create an empty list of ActivePoints (for working) and ValidPoints (for the result). Add a first random point from the canvas to your list of ActivePoints (and ValidPoints) The random point shall be within the Width and Height of the canvas, and it shall take a Margin into account:
private static PointCollection ActivePoints, ValidPoints;
...
ActivePoints = new PointCollection();
ValidPoints = new PointCollection();
AddPoint(gridCellSize, new Point(rnd.Next((int)Margin,
(int)(Width - Margin)), rnd.Next((int)Margin, (int)(Height - Margin))));
Now select a random point (actPoint) from your list of ActivePoints (at the very beginning, it will be the start point) and repeat everything in the following loop until the list of ActivePoints is empty:
while (ActivePoints.Count > 0)
{
actPoint = ActivePoints[rnd.Next(0, ActivePoints.Count)];
for (var i = 0; i < PointsPerAttempt; i++)
{
newPoint = NewPointInDisc(actPoint, MinDistance);
if (FreeOfNeighbours(Width, Height, gridCellSize, newPoint, MinDistance, Margin))
AddPoint(gridCellSize, newPoint);
}
ActivePoints.Remove(actPoint);
}
For each selected point (actPoint) you focus on a disc with an inner radius of your minimal distance (MinDistance) and an outer radius of twice your minimal distance:<!--
The method NewPointInDisc detects a random point within this disc, and you repeat this filling of the disc, e.g., 30 times (which gives you a good distribution of points). You can play around with that number by changing the content of the parameter PointsPerAttempt.<!--
The method FreeOfNeighbours makes sure that each point you find within the disc is not too close to an existing point in its neighbourhood. All qualified points (shown in black) around your actual point actPoint are added to the list of ActivePoints, all disqualified points (shown in grey) are ignored.
Now the disc around your active point is saturated. Therefore, it is removed from the list of ActivePoints.
Then the procedure starts again with a new point selected randomly from the list of ActivePoints and so on ...
... until the whole canvas is saturated with points:
Whenever you add a point (AddPoint) to your list of active (and valid) points, you also add it to your Grid from the beginning. That makes it easier and faster to look for near neighbours.
private static void AddPoint(int GridCellSize, Point Point)
{
ActivePoints.Add(Point);
ValidPoints.Add(Point);
Grid[(int)(Point.X / GridCellSize), (int)(Point.Y / GridCellSize)] = Point;
}
This method (NewPointInDisc) detects a random new point within the bespoken disc around a point:
private static Point NewPointInDisc(Point Point, int MinDistance)
{
var mId = Matrix.Identity;
mId.Rotate(rnd.Next(0, 360));
Vector v = mId.Transform(new Vector(1, 0));
return Point + v * rnd.Next(MinDistance, (2 * MinDistance + 1));
}
And here the check is performed, whether a possible new point in the disc is either out of the canvas (taking the margin into account) or too close to other existing points. In NeighbourTooClose, the Grid is used to check only the sections around the point:
private static bool FreeOfNeighbours(double Width, double Height,
int GridCellSize, Point Point, int MinDistance, double Margin)
{
if (Point.X < Margin || Point.X >= Width - Margin
|| Point.Y < Margin || Point.Y >= Height - Margin
|| NeighbourTooClose(GridCellSize, Point, MinDistance))
return false;
return true;
}
private static bool NeighbourTooClose(int GridCellSize, Point Point, int MinDistance)
{
int a = (int)(Point.X / GridCellSize);
int b = (int)(Point.Y / GridCellSize);
for (int i = a - 1; i <= a + 1; i++)
for (int j = b - 1; j <= b + 1; j++)
{
if (i < 0 || i >= Grid.GetLength(0)
|| j < 0 || j >= Grid.GetLength(1))
continue;
if (Grid[i, j] != null && TooClose(Grid[i, j], Point, MinDistance))
return true;
}
return false;
}
private static bool TooClose(Point? P1, Point P2, int MinDistance)
{
double a = P2.X - ((Point)P1).X, b = P2.Y - ((Point)P1).Y;
return a * a + b * b < MinDistance * MinDistance;
}
So a lot of time is saved, because for each point the check for too close neighbours is not performed for all other points on the canvas but only for those in the eight nearest sections of the actual point in the Grid (there can only be none or one point in each section of the Grid).
Generate Artworks
This algorithm can be used in various situations. Here are some basic examples, but it is up to you and your creativity what you produce with the Poisson disc algorithm:
Basic photo: (c) 2014 qiurii
Points of Interest
Georges Seurat died at age 31, but before that he painted "A Sunday Afternoon on the Island of La Grande Jatte" (1884–1886), a perfect manual implementation of the Poisson disc algorithm.
History
- 10th January, 2015 - Published
- 11th January, 2015 - Links to other articles in the series added
