point-elimination

Eliminate 1D, 2D or 3D points: weighted sample elimination to an exact count with progressive ordering, and greedy elimination by minimum distance, both with adaptive spacing.

eliminateToCount implements weighted sample elimination, progressive sampling and adaptive sampling from:

Cem Yuksel. Sample Elimination for Generating Poisson Disk Sample Sets. Computer Graphics Forum (Proceedings of EUROGRAPHICS 2015), 34(2), 25–32, 2015. doi:10.1111/cgf.12538

Reference implementation: cyCodeBase

Installation

npm install point-elimination

Usage

See the example and its source.

import {
  eliminateToCount,
  eliminateByDistance,
  packingRadius,
} from "point-elimination";

// 5000 random 2D points
const points = Float32Array.from({ length: 5000 * 2 }, Math.random);

// Poisson disk subset of exactly 1000 points
const indices = eliminateToCount(points, 1000, { dimension: 2 });
// => Uint32Array of kept point indices

// Progressive ordering: the first k indices are also well distributed, for any
// k. Slice the output to change the density without eliminating again.
const ordered = eliminateToCount(points, 1000, {
  dimension: 2,
  progressive: true,
});
const first100 = ordered.subarray(0, 100);

// The domain defaults to the bounding box (its volume for 3D points). Set it
// when points don't fill their bounding box, eg. the area of a mesh surface.
const surfaceIndices = eliminateToCount(meshPoints, 1000, {
  domainSize: meshArea,
  domainDimension: 2,
});

// Points at least 0.02 apart, earlier points first
const spaced = eliminateByDistance(points, 0.02, { dimension: 2 });

// Adaptive spacing: twice the distance where scale is 2
const scales = Float32Array.from({ length: 5000 }, (_, i) =>
  points[i * 2] < 0.5 ? 1 : 2,
);
const adaptive = eliminateByDistance(points, 0.02, { dimension: 2, scales });

// Poisson disk radius of 1000 points densely packed in a unit square: their
// minimum distance is twice that
const radius = packingRadius(1, 1000, 2);

API

pointElimination

• pointElimination
  • static
    • .eliminateByDistance(points, distance, [options]) ⇒ Uint32Array
    • .eliminateToCount(points, count, [options]) ⇒ Uint32Array
    • .packingRadius(domainSize, count, [domainDimension]) ⇒ number
  • inner
    • ~EliminateByDistanceOptions : object
    • ~EliminateToCountOptions : object

pointElimination.eliminateByDistance(points, distance, [options]) ⇒ Uint32Array

Greedy elimination: keeps each point, in order, not closer than distance to an already kept one. Every removed point of order conflicts with a kept point.

Kind: static method of pointElimination Returns: Uint32Array - Unique indices of the kept points, in visiting order.

Param	Type	Default	Description
points	ArrayLike.<number>		Flat array of point components.
distance	number		Minimum distance between kept points.
[options]	EliminateByDistanceOptions	{}

pointElimination.eliminateToCount(points, count, [options]) ⇒ Uint32Array

Weighted sample elimination (Yuksel 2015) to a Poisson disk distributed subset of count points.

Use 3 to 5 times more input points than count: more barely improves quality while cost grows quadratically.

Kind: static method of pointElimination Returns: Uint32Array - Indices of the kept points, ascending unless progressive.

Param	Type	Default	Description
points	ArrayLike.<number>		Flat array of point components.
count	number
[options]	EliminateToCountOptions	{}

pointElimination.packingRadius(domainSize, count, [domainDimension]) ⇒ number

Poisson disk radius of count points densely packed in a domain of domainSize: segments in 1D, hexagonal in 2D and face-centered cubic in 3D. Points are twice that apart.

Kind: static method of pointElimination

Param	Type	Default	Description
domainSize	number		Length, area or volume of the domain.
count	number
[domainDimension]	number	3	From 1 to 3.

pointElimination~EliminateByDistanceOptions : object

Kind: inner typedef of pointElimination Properties

Name	Type	Default	Description
[dimension]	number	3	Number of components per point, from 1 to 3.
[scales]	ArrayLike.<number>		Per point distance multiplier, positive and finite: two points conflict below distance times the mean of their scales.
[order]	ArrayLike.<number>		Indices in visiting order: earlier points have priority. Points not listed are discarded. Defaults to the index order.

pointElimination~EliminateToCountOptions : object

Kind: inner typedef of pointElimination Properties

Name	Type	Default	Description
[dimension]	number	3	Number of components per point, from 1 to 3.
[domainSize]	number		Length, area or volume of the sampled domain. Defaults to the points bounding box, ignoring flat axes. Set it for points on a curve or surface, eg. the area of a mesh.
[domainDimension]	number		Dimension of the sampled domain, from 1 to 3, eg. 2 for a surface in 3D. Defaults to the bounding box dimension, or dimension when domainSize is set. Set with domainSize.
[scales]	ArrayLike.<number>		Per point spacing multiplier for adaptive sampling, positive and finite. Normalize them so that the domain mean of 1 / scale^domainDimension is 1.
[weightLimiting]	boolean	true	Cap the weight of very close neighbors.
[progressive]	boolean	false	Order the output so that each prefix is itself well distributed.

License

MIT. See license file.