Important
Please participate in the survey here!
(open until end of February)
To achieve a better sample size, I'd highly appreciate if you could circulate the link to this survey in your own networks.
Note
This is one of 189 standalone projects, maintained as part of the @thi.ng/umbrella monorepo and anti-framework.
🚀 Help me to work full-time on these projects by sponsoring me on GitHub. Thank you! ❤️
Fast, incremental 2D Delaunay & Voronoi mesh implementation, based on the @thi.ng/quad-edge data structure after Guibas & Stolfi and partially ported from C++ versions by Dani Lischinski, Paul Heckbert et al:
References:
- http://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/quadedge.html
- http://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/lischinski/114.ps
Construction speed: 20k random points (poisson disc samples, even distribution) in ~850ms (Chrome 72, MBP 2016)
STABLE - used in production
Search or submit any issues for this package
- @thi.ng/quad-edge - Quadedge data structure after Guibas & Stolfi
yarn add @thi.ng/geom-voronoiES module import:
<script type="module" src="https://cdn.skypack.dev/@thi.ng/geom-voronoi"></script>For Node.js REPL:
const geomVoronoi = await import("@thi.ng/geom-voronoi");Package sizes (brotli'd, pre-treeshake): ESM: 1.45 KB
- @thi.ng/api
- @thi.ng/bitfield
- @thi.ng/checks
- @thi.ng/geom-clip-line
- @thi.ng/geom-clip-poly
- @thi.ng/geom-isec
- @thi.ng/geom-poly-utils
- @thi.ng/math
- @thi.ng/quad-edge
- @thi.ng/vectors
Several projects in this repo's /examples directory are using this package:
| Screenshot | Description | Live demo | Source |
|---|---|---|---|
 |
Poisson-disk shape-aware sampling, Voronoi & Minimum Spanning Tree visualization | Demo | Source |
 |
Quasi-random lattice generator | Demo | Source |
 |
Animated Voronoi diagram, cubic splines & SVG download | Demo | Source |
import * as g from "@thi.ng/geom";
import { DVMesh } from "@thi.ng/geom-voronoi";
import { repeatedly } from "@thi.ng/transducers";
import { randNorm2 } from "@thi.ng/vectors";
const pts = [...repeatedly(() => randNorm2([], Math.random() * 250), 1000)];
const mesh = new DVMesh(pts);
// raw polygons of primary or dual mesh
mesh.delaunay()
mesh.voronoi()
// ...or clipped & filtered polygons within convex polygon boundary
const bounds = g.vertices(g.center(g.rect(500)));
// [ [ -250, -250 ], [ 250, -250 ], [ 250, 250 ], [ -250, 250 ] ]
const cells = mesh.voronoi(bounds);
document.body.innerHtml = g.asSvg(
g.svgDoc({ fill: "none", "stroke-width": 0.25 },
g.group({ stroke: "blue" }, mesh.delaunay(bounds).map((p) => g.polygon(p))),
g.group({ stroke: "red" }, mesh.voronoi(bounds).map((p) => g.polygon(p)))
)
);If this project contributes to an academic publication, please cite it as:
@misc{thing-geom-voronoi,
title = "@thi.ng/geom-voronoi",
author = "Karsten Schmidt",
note = "https://thi.ng/geom-voronoi",
year = 2016
}© 2016 - 2024 Karsten Schmidt // Apache License 2.0