2D Point Sets

In some of my projects I want an irregularly spaced set of 2D points. Click to generate a new set of points:

On this page I'm collecting some of the ways I've generated that set

1. Poisson Disk sampling
2. Lloyd Relaxation
3. Jittered Grid
4. Precomputed blue noise

There are many more that I haven't tried yet. I'm also trying to figure out what I want from these points:

1. Does not look like a grid.
2. Points are not clumped together.
3. No large gaps between points.
4. No obvious streaks.

Philippe Rivière^[1] has looked into this problem much more than I have, and has collected some algorithms^[2].

TODO: I'm still learning about this topic, and have a whole bunch more notes in another file that I need to merge onto this page

TODO: how to measure "streaks"? maybe difference betwen (angle of an edge) and (closest angle in neighboring cell)?

 1  Jittered Grid#

The easiest way to generate points is to make a grid:

But for many of my projects, a grid is too regular. The simplest fix is to add random "jitter" to the points:

let points = [];
for (let y = top; y < bottom; y += spacing) {
    for (let x = left; x < right; x += spacing) {
        points.push([
            x + jitter * spacing * (random() - 0.5),
            y + jitter * spacing * (random() - 0.5)
        ]);
    }
}

The jittered grids start with either a square or hexagon grid, and then add a random offset to each point. For the square grid I choose an offset that's square shaped. For the hex grid I tried a square shape and a circular shape. The jittered-hexagonal-grid-sampling^[3] library chooses from a hexagon shape.

But how much jitter should I add? First, let's look at the minimum amount of jitter to make it look irregular. I decided to measure the angle between points. Try increasing the jitter slider until the angle histogram shows all angles are evenly represented ("isotropic"):

To get angles evenly distributed, I need jitter ≥ 0.9, almost the full size of a grid square or hexagon. Now, let's look at the maximum amount of jitter to make it look even. I decided to measure the distance between points. Try decreasing the jitter slider until the distance histogram shows few outliers:

The short distance outliers are red; the long distance outliers are blue. To avoid points being too close together (red) or gaps (blue), I need jitter ≤ 0.6, a little over half the size of a grid square or hexagon.

That means I need jitter ≤ 0.6 and also jitter ≥ 0.9. There's no jitter value that gives me an even distribution of angles while avoiding distance outliers. Jittered grids are easy to implement but the output isn't great.

TODO: for hex/square/voronoi, what if we apply jitter to the vertices instead of the center points? related: my corner cutting post^[4] where I non-randomly moved vertices

 2  Poisson Disk#

Poisson Disk algorithms produce a much better set of points than jittered grids. I use these JavaScript libraries:

How do they compare to jittered grids? Let's compare the angle distribution. It looks pretty good:

Now let's look at distance outliers. It looks pretty good:

This is the main reason I like Poisson Disk more than Jittered Grid. It prevents points from being too close together (red), but sometimes allows points to be too far from each other (blue). We can also tune the output a little bit. The higher the tries parameter, the more evenly spaced the points, but the longer it takes. Reducing the value from the default of 30 down to 5 allows it to run 2–4X faster. Values above 30 do not seem to improve quality. Here's a comparison:

The poisson-disk-sampling library has three extra features over fast-2d-poisson-disk:

1. Works in >2 dimensions. Not shown here.
2. Works with variable density. Not shown here.
3. Allows controlling slack between min vs max distance. Let's look at this:

See how the distribution shows a much wider set of distances when the slack value is higher. The default slack is for max to be 2*min. For many of my procedural generation projects, I like the wider distribution of distances. Combining low slack and low tries can cause problems; try adjusting the sliders to slack=1 and then reduce tries to 3 or 2. I recommend keeping tries >5.

TODO A Comparison of Methods for Generating Poisson Disk Distributions^[7] (2008, Lagae and Dutre)

Casey Muratori's blog post The Nebraska Problem^[8] (2014) describes how packing poisson-disk-style points tightly led to "parallel branches" with visible gaps, and after trying many different fixes, ended up using a curved+jittered regular grid.

 3  Blue Noise#

Blue Noise gives us a texture (array of values at each x,y) instead of a point set. Subsets of the texture can be used to construct a point set. Here we pick every pixel with a brightness between start and start+width:

Things to try:

1. Change the start value while keeping width the same. Every value of start produces blue noise. That means there are 256 blue noise sets hidden in this one data file (25681 bytes). They overlap from one window to the next, which would be useful to allow some set of points to go out while new ones come into the set, all while maintaining the blue noise property.
2. Change the width value (defaults to 8) while keeping start the same. This changes the density of points. We can set this threshold separately per pixel to give a varying density image (dithering).

The precomputed blue noise I'm showing here from Christoph Peters's blog post "Free blue noise textures"^[9], CC0 license. I'm using 128_128/LDR_LLL1_0.png in a 256✕128 configuration (two tiles) to show that it's tileable.

There are some distances that never show up. TODO: understand why

90° angles don't show up in this set. You can see this in the color distribution charts — there are four places where the histogram stays near zero.

TODO Philippe Rivière's Blue noise^[10] notebook

TODO: show how the precomputed blue noise can be combined with a perlin noise threshold to make variable density points

TODO https://observablehq.com/@jobleonard/pseudo-blue-noise^[11]

TODO: read https://acko.net/blog/stable-fiddusion/^[12]

TODO: Recursive Wang Tiles^[13] (2006, Kopf, Cohen-Or, Deussen, Lischinski)

 4  TODO Lloyd Relaxation#

Lloyd Relaxation modifies a point set to make it more regular. We can run it multiple times.

 5  TODO Relaxed Grid#

Neil T's approach^[14] (2025) is use a relaxed grid so that you can still use grid coordinates, but otherwise get an irregular grid appearance.

TODO: for hex/square/voronoi, what if we apply jitter to the vertices instead of the center points? related: my corner cutting post^[15] (2010) where I non-randomly moved vertices

 6  TODO Quasirandom Sequences#

There are a whole bunch of other techniques, including latinized grids, wang tiles, penrose tiles, polyominoes, sobol/halton sequences

TODO The Unreasonable Effectiveness of Quasirandom Sequences^[16] (2018, Martin Roberts)

TODO https://extremelearning.com.au/a-simple-method-to-construct-isotropic-quasirandom-blue-noise-point-sequences/^[17] - there is a connection between blue noise and point sets, but I don't quite understand it. Martin Roberts in that article explores how much jitter to add to quasirandom sequences to build a blue noise point set

TODO Low Discrepancy Blue Noise Sampling^[18] (2016, Ahmed, Perrier, et al)

TODO Fast Progressive Multi-Jittered Sample Sequences^[19] (2022, Job van der Zwan)

 7  Evaluation#

Philippe Rivière^[20] wrote a history of Poisson Distribution generators^[21] (2023): Mitchell's Algorithm, Bridson's Algorithm, and improvements from Martin Roberts and Jacob Rus. He compares area and distance and shape for each of the generators. I also care about angle.

The reason I want these points instead of a grid is to avoid them looking too regular.

TODO: might be interesting to know the correlation between angle and the neighbor's angle, to see if we're getting "streaks". I see streaks sometimes, especially with poisson-disk-sampling set to tries=30 and slack=1.0. But I don't yet know how to measure them.

TODO: could add Fil's area and shape visualizations

TODO: a metric to summarize the distributions

TODO: "low discrepancy" metric

TODO: fourier transform might be interesting to look at

TODO: read about Voronoi Entropy, a measure of how ordered the points seem Characterization of Self-Assembled 2D Patterns with Voronoi Entropy^[22] (2018, Bormashenko et al)