pointille

Distribute n points approximately evenly inside a polygon — deterministically — via Lloyd's algorithm on a centroidal Voronoi tessellation (CVT). Named after the Pointillist painters, who were solving much the same problem by hand.

| | Triangle | Square | Pentagon | | --- | :---: | :---: | :---: | | n = 4 | | | | | n = 5 | | | | | n = 6 | | | | | n = 7 | | | |

Faint cells show each point's Voronoi region clipped to the polygon. Regenerate with npm run test:demo.

Install

npm install pointille

Usage

import { pointille } from 'pointille'

const unitSquare = [
  [0, 0], [1, 0], [1, 1], [0, 1],
] as const

const points = pointille(unitSquare, 25)
// => 25 [x, y] tuples, all inside the square, roughly evenly spaced.

A Point is a readonly [number, number] tuple. A Polygon is an ordered ring of points (no need to close it — the first vertex is implicitly connected to the last).

Options

pointille(polygon, n, {
  iterations: 30,    // Lloyd relaxation steps. Default: 30.
  seed: 1,           // Starting index into the Halton seed sequence. Default: 1.
})

Changing seed is the canonical way to get a different — but still deterministic — layout for the same (polygon, n) pair.

Algorithm

1. Seed. Generate n candidate points inside the polygon's bounding box using a 2D Halton sequence (pairing Van der Corput sequences in bases 2 and 3) and reject any falling outside the polygon. Halton is a low-discrepancy quasi-random sequence: no PRNG state, fully deterministic, well-spread.
2. Relax. Iterate Lloyd's algorithm:
   • Compute a Voronoi diagram of the current sites with d3-delaunay.
   • Clip each Voronoi cell to the polygon via polygon-clipping so that we handle concave polygons.
   • Move each site to the area-weighted centroid of its clipped cell.
3. Stop after iterations steps (default 30). The result is a centroidal Voronoi tessellation: each cell's site is at its own centroid, which gives the visual "even distribution" property.

The function is pure and deterministic: same inputs → byte-identical outputs.

Development

npm install
npm test         # node --test on src/__tests__/*.test.ts via tsx
npm run build    # tsup (ESM + CJS + .d.ts)
npm run test:demo

License

MIT