CoreSource checked

Poisson Disk Sampling

Places random points while keeping a minimum distance between them.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Intermediate
Family: Spatial Sampling
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready
Aliases: Blue Noise Sampling

Overview

Poisson Disk Sampling creates natural-looking point sets without clumps by rejecting points too close to existing samples.

Core Concepts

random drawminimum distance constraintsample selectionspatial samplingrandom sourcedistribution shape

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n k)

Space

O(n)

When to Use

Use Poisson Disk Sampling when you need to generate candidate points around active samples.
Use it for object placement with inputs like sampling region.
Use it when randomization, representative samples, or controlled variation are needed.
Use it when the Spatial Sampling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when reproducibility, distribution quality, or sample independence cannot be verified.
Do not treat the O(n) average case as a guarantee; check the O(n k) worst case.
Avoid it when the required output is not well-spaced random points.

What It Does

Generates candidate points around active samples
Keeps only points that satisfy a minimum distance

Use Cases

Object placement
Texture sampling
Blue-noise distributions

Inputs

Sampling region
Minimum distance
Random source

Outputs

Well-spaced random points

Key Formulas (1)

Minimum-distance test

accept candidate if distance(candidate, point) ≥ radius for every nearby point

accept candidate if distance(candidate, point) >= radius for every nearby point

Keeps generated points from getting closer than the requested spacing.

Pseudocode

1.Place an initial random point
2.Keep active points in a list
3.Generate candidates around an active point
4.Accept candidates far enough from neighbors
5.Remove active points that produce no candidates

Canonical Example

Input: items = [A, B, C, D], seed = 7
Output: sampled or randomized result
Explanation: Poisson Disk Sampling: The algorithm uses controlled randomness to choose or generate values.

Implementation Notes

Keep the input contract explicit: Sampling region; Minimum distance; Random source.
Use this step as the implementation spine: Place an initial random point.
Then preserve the next state change: Keep active points in a list.
Separate the random number source from the algorithm so tests can use fixed seeds.

Common Pitfalls

Grid acceleration makes neighbor distance checks efficient.
Sampling from the wrong distribution can make the estimate look precise but biased.
Using biased random choices or forgetting to store the seed for reproducible runs.
Returning well-spaced random points without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show points filling space while maintaining visible gaps.

Step 1 of 5: Place an initial random point

blue-noise-points

Notes

Poisson Disk Sampling operates in O(n) time and O(n) space within the Spatial Sampling family. Key governing relation: accept candidate if distance(candidate, point) >= radius for every nearby point. Often compared with Rejection Sampling and Poisson Disk Object Placement.