poisson-disk-sampling

Poisson disk sampling in arbitrary dimensions.

Installing

With npm do:

npm install poisson-disk-sampling

With yarn do:

yarn add poisson-disk-sampling

A compiled version for web browsers is also available on a CDN:

<script src="https://cdn.jsdelivr.net/gh/kchapelier/poisson-disk-sampling@2.2.0/build/poisson-disk-sampling.min.js"></script>

Features

Can be used in any dimension (1D, 2D, 3D and more).
Can be used with a custom RNG function.
Allow the configuration of the max number of tries, the minimum distance and the maximum distance between each points.
Allow the use of custom function to drive the density of the distribution.

Basic example

var p = new PoissonDiskSampling({
    shape: [600, 300, 200],
    minDistance: 20,
    maxDistance: 30,
    tries: 10
});
var points = p.fill();

console.log(points); // array of sample points, themselves represented as simple arrays

Result as an image

Example with an image driving the distribution density

var p = new PoissonDiskSampling({
    shape: [500, 500],
    minDistance: 1,
    maxDistance: 30,
    tries: 20,
    distanceFunction: function (p) {
        return getImagePixelValueSomehow(p[0], p[1]); // value between 0 and 1
    }
});
var points = p.fill();

console.log(points); // array of sample points, themselves represented as simple arrays

Result as an image

Complete working example

Demo online | Source code

Public API

Constructor

new PoissonDiskSampling(options[, rng])

options :
- shape : Size/dimensions of the grid to generate points in, required.
- minDistance : Minimum distance between each points, required.
- maxDistance : Maximum distance between each points, defaults to minDistance times 2.
- tries : Maximum number of tries to generate a point, defaults to 30.
- distanceFunction : Function to control the distance between each point depending on their position, must return a value between 0 and 1.
- bias : When using a distanceFunction, will indicate which point constraint takes priority when evaluating two points (0 for the lowest distance, 1 for the highest distance), defaults to 0.
rng : A function to use as random number generator, defaults to Math.random.

// Poisson disk sampling in a 2D square
var pds = new PoissonDiskSampling({
    shape: [50, 50],
    minDistance: 4,
    maxDistance: 4,
    tries: 10
});

// Poisson disk sampling in a 3D volume
var pds = new PoissonDiskSampling({
    shape: [900, 400, 400],
    minDistance: 20,
    maxDistance: 25,
    tries: 10
});

// Poisson disk sampling in a 2D square using
// a custom function to drive the distance between each point
var pds = new PoissonDiskSampling({
    shape: [400, 400],
    minDistance: 4,
    maxDistance: 20,
    tries: 20,
    distanceFunction: function (point) {
        return point[0] / 400;
    },
    bias: 0
});

Method

pds.fill()

Fill the grid with random points following the distance constraint.

Returns the entirety of the points in the grid as an array of coordinate arrays. The points are sorted in their generation order.

var points = pds.fill();

console.log(points[0]);
// prints something like [30, 16]

pds.getAllPoints()

Get all the points present in the grid without trying to generate any new points.

Returns the entirety of the points in the grid as an array of coordinate arrays. The points are sorted in their generation order.

var points = pds.getAllPoints();

console.log(points[0]);
// prints something like [30, 16]

pds.getAllPointsWithDistance()

Get all the points present in the grid along with the result of the distance function.

Returns the entirety of the points in the grid as an array of coordinate + distance function result arrays. The points are sorted in their generation order.

Calling this method on an instance of PoissonDiskSampling without a distanceFunction will throw an error.

var points = pds.getAllPointsWithDistance();

console.log(points[0]);
// prints something like [30, 16, 0.4], 0.4 being the result of the distance function

pds.addRandomPoint()

Add a completely random point to the grid. There won't be any check on the distance constraint with the other points already present in the grid.

Returns the point as a coordinate array.

pds.addPoint(point)

point : Point represented as a coordinate array.

Add an arbitrary point to the grid. There won't be any check on the distance constraint with the other points already present in the grid.

Returns the point added to the grid.

If the point given is not of the correct dimension (i.e. inserting a 2D point in a 3D grid) or doesn't fit in the grid size, null will be returned.

pds.addPoint([20, 30, 40]);

pds.next()

Try to generate a new point in the grid following the distance constraint.

Returns a coordinate array when a point is generated, null otherwise.

var point;

while(point = pds.next()) {
    console.log(point); // [x, y, z]
}

pds.reset()

Reinitialize the grid as well as the internal state.

When doing multiple samplings in the same grid, it is preferable to reuse the same instance of PoissonDiskSampling instead of creating a new one for each sampling.

Usages in the wild

Creative Experiments by Lionel Radisson: #1 / #2
"Poisson disc squares", by Matt DesLauriers
Mapgen4, a procedural wilderness map generator by Amit Patel

Implementation notes

Internally, there are two different implementations of the algorithm. The implementation is chosen depending on whether a distanceFunction is passed to the constructor. The library is designed in such a way as to keep it transparent to the end user.

In order to reduce the impact of this dependency on the size of the javascript bundle(s) in web projects, it is possible to explicitly require a given implementation.

var PoissonDiskSampling = require('poisson-disk-sampling/src/implementations/fixed-density');

var PoissonDiskSampling = require('poisson-disk-sampling/src/implementations/variable-density');

History

2.2.0 (2020-02-17) :

Do not ignore distanceFunction anymore if minDistance and maxDistance are equal
Make it possible to explicitly require a specific implementation

2.1.0 (2020-02-10) :

Due to an issue on npmjs.com this version was not listed on the website even though it was available through the CLI.

Implement getAllPointsWithDistance()
Add a test suite for the variable density implementation
Fix an issue where the actual minDistance could be larger than the one set by the user in the variable density implementation

2.0.0 (2020-02-03) :

Support distance function / variable density
Change constructor signature, the rest of the public API is unchanged

1.0.6 (2019-09-28) :

Update dev dependencies

1.0.5 (2019-05-27) :

Fix package on npm (adding missing file)

1.0.4 (2019-05-27) :

Replace ndarray with a leaner custom implementation to drastically reduce the size of the package (~50%)
Update dev dependencies

1.0.3 (2019-01-12) :

Update dev dependencies
Change node versions tested with travis

1.0.2 (2017-09-30) :

Minor performance tweaks
Reduce npm package size
Update moore dep
Add benchmark script

1.0.1 (2017-01-06) :

Add some checks on the points added with addPoint()
Implements tests
Add travis support

1.0.0 (2016-09-16) :

Implement getAllPoints() and reset()
Fix incorrect handling of maxDistance when it is not set
Fix incorrect behavior when fill() is called several times
Declare the public API stable
API documentation
Remove mathp dependency

0.0.1 (2015-11-28) :

First release

Roadmap

Make it possible to import/require only one of the implementation.

How to contribute ?

For new features and other enhancements, please make sure to contact me beforehand, either on Twitter or through an issue on Github.

License

MIT

i5anoff/poisson-disk-sampling

poisson-disk-sampling

Installing

Features

Basic example

Result as an image

Example with an image driving the distribution density

Result as an image

Complete working example

Public API

Constructor

Method

Usages in the wild

Implementation notes

History

2.2.0 (2020-02-17) :

2.1.0 (2020-02-10) :

2.0.0 (2020-02-03) :

1.0.6 (2019-09-28) :

1.0.5 (2019-05-27) :

1.0.4 (2019-05-27) :

1.0.3 (2019-01-12) :

1.0.2 (2017-09-30) :

1.0.1 (2017-01-06) :

1.0.0 (2016-09-16) :

0.0.1 (2015-11-28) :

Roadmap

How to contribute ?

License