# Fastfish, Elixir + Rust 2D poisson disc sampling

Source at https://github.com/Lucassifoni/fastfish

### Random but natural disk placement

I recently had the occasion to implement two algorithms aiming to place disks on a surface. My constraints were perceptual, as the placement should look homogeneous to the eye while not too deterministic. An hexagonal grid is the opposite feel of what I was looking for.

I stumbled on this elegant visualisation by Jason Davies (https://www.jasondavies.com/poisson-disc/), based on the paper â€śFast Poisson Disk Sampling in Arbitrary Dimensionsâ€ť by Robert Bridson, University of British Columbia.

A first implementation in Elixir & Rust, based on the paper, quickly gave me a similar result to Jasonâ€™s visualisation.

### The algorithm

Letting aside the performance optimizations in Roberd Bridsonâ€™s paper, here are the general steps :

- Given a minimum distance between samples
`D`

, a domain width, a domain height, a number of attempts`K`

, - Place a disk of radius
`r < D`

at the center of the domain - This disk is put in the
`active disks list`

- While the
`active disks list`

is not empty- The current disk is chosen randomly in the active disks list
- While the current attempts to place a disk is lower than
`K`

and a disk wasnâ€™t placed- Generate a disk at a radius > 2D around the current disk
- If thereâ€™s a collision with either another disk or the domain bounds,
`increment K`

- Else save this disk as the next and
`break`

- If you have a next disk (so attempts are < K), add it to the active disks list
- Else, remove the current disk from the active list

This works but lifts the need to check for collisions at every step. Bridsonâ€™s paper solves this with a data structure that represents a background grid, sampling the domain to ensure thereâ€™s at most one disk in every cell. As every disk has the same radius, you just have to check nearby cells for collisions.

### Multi-radius sampling

My task needed to have a compact cluster of disks, unbounded, with a defined number of disks having defined radii. The picture below is a visualisation of the expected resultâ€‰:

I replaced the background grid by a subsetting of the total disk list, based on existing radii and next-disk radius. We check the circles in a circular shell for collisions. It is less efficient than the background grid but works well with a diverse disk list.

What is interesting is the variety of clusters you get by varying the value of K, the number of allowed attempts :

#### K = 2

#### K = 5

#### K = 10

#### K = 30

### Performance

My use-case has those parameters :

- Runs one-time per person who visits the website (as long as their session holds)
- Runs server-side
- Number of disks : 100 < N < 1000 (more 100 than 1000 though)
- Different radii : 2, (90% of disks have a radius of R, 10% of disks have a radius of 3R)

```
Benchmarking Elixir, 100 samples, k=30 ...
Benchmarking Rust , 100 samples, k=30 ...
Name ips average deviation median 99th %
Rust , 100 samples, k=30 6.90 K 0.145 ms Â±67.27% 0.186 ms 0.31 ms
Elixir, 100 samples, k=30 0.71 K 1.42 ms Â±8.98% 1.40 ms 1.69 ms
Benchmarking Elixir, 500 samples, k=30 ...
Benchmarking Rust , 500 samples, k=30 ...
Name ips average deviation median 99th %
Rust , 500 samples, k=30 1.16 K 0.86 ms Â±93.65% 1.01 ms 1.96 ms
Elixir, 500 samples, k=30 0.0477 K 20.96 ms Â±2.88% 20.92 ms 22.45 ms
```

So, for my use-case, fair enough. Iâ€™ll have to start investigating how did I get this variability on the Rust side though. My Rust isnâ€™t yet *that* idiomatic, and rewriting it in a few months should shed light on that matter.