An incredibly fast and robust JavaScript library for Delaunay triangulation of 2D points.
- d3-delaunay for Voronoi diagrams, search, traversal and rendering (a part of D3).
- d3-geo-voronoi for Delaunay triangulations and Voronoi diagrams on a sphere (e.g. for geographic locations).
const coords = [168,180, 168,178, 168,179, 168,181, 168,183, ...];
const delaunay = new Delaunator(coords);
console.log(delaunay.triangles);
// [623, 636, 619, 636, 444, 619, ...]
Install with NPM (npm install delaunator
) or Yarn (yarn add delaunator
), then import as an ES module:
import Delaunator from 'delaunator';
To use as a module in a browser:
<script type="module">
import Delaunator from 'https://cdn.skypack.dev/[email protected]';
</script>
Or use a browser UMD build that exposes a Delaunator
global variable:
<script src="https://unpkg.com/[email protected]/delaunator.min.js"></script>
Constructs a delaunay triangulation object given an array of point coordinates of the form:
[x0, y0, x1, y1, ...]
(use a typed array for best performance).
Constructs a delaunay triangulation object given an array of points ([x, y]
by default).
getX
and getY
are optional functions of the form (point) => value
for custom point formats.
Duplicate points are skipped.
A Uint32Array
array of triangle vertex indices (each group of three numbers forms a triangle).
All triangles are directed counterclockwise.
To get the coordinates of all triangles, use:
for (let i = 0; i < triangles.length; i += 3) {
coordinates.push([
points[triangles[i]],
points[triangles[i + 1]],
points[triangles[i + 2]]
]);
}
A Int32Array
array of triangle half-edge indices that allows you to traverse the triangulation.
i
-th half-edge in the array corresponds to vertex triangles[i]
the half-edge is coming from.
halfedges[i]
is the index of a twin half-edge in an adjacent triangle
(or -1
for outer half-edges on the convex hull).
The flat array-based data structures might be counterintuitive, but they're one of the key reasons this library is fast.
A Uint32Array
array of indices that reference points on the convex hull of the input data, counter-clockwise.
An array of input coordinates in the form [x0, y0, x1, y1, ....]
,
of the type provided in the constructor (or Float64Array
if you used Delaunator.from
).
Updates the triangulation if you modified delaunay.coords
values in place, avoiding expensive memory allocations.
Useful for iterative relaxation algorithms such as Lloyd's.
Benchmark results against other Delaunay JS libraries
(npm run bench
on Macbook Pro Retina 15" 2017, Node v10.10.0):
uniform 100k | gauss 100k | grid 100k | degen 100k | uniform 1 million | gauss 1 million | grid 1 million | degen 1 million | |
---|---|---|---|---|---|---|---|---|
delaunator | 82ms | 61ms | 66ms | 25ms | 1.07s | 950ms | 830ms | 278ms |
faster‑delaunay | 473ms | 411ms | 272ms | 68ms | 4.27s | 4.62s | 4.3s | 810ms |
incremental‑delaunay | 547ms | 505ms | 172ms | 528ms | 5.9s | 6.08s | 2.11s | 6.09s |
d3‑voronoi | 972ms | 909ms | 358ms | 720ms | 15.04s | 13.86s | 5.55s | 11.13s |
delaunay‑fast | 3.8s | 4s | 12.57s | timeout | 132s | 138s | 399s | timeout |
delaunay | 4.85s | 5.73s | 15.05s | timeout | 156s | 178s | 326s | timeout |
delaunay‑triangulate | 2.24s | 2.04s | OOM | 1.51s | OOM | OOM | OOM | OOM |
cdt2d | 45s | 51s | 118s | 17s | timeout | timeout | timeout | timeout |
The algorithm is based on ideas from the following papers:
- A simple sweep-line Delaunay triangulation algorithm, 2013, Liu Yonghe, Feng Jinming and Shao Yuehong
- S-hull: a fast radial sweep-hull routine for Delaunay triangulation, 2010, David Sinclair
- A faster circle-sweep Delaunay triangulation algorithm, 2011, Ahmad Biniaz and Gholamhossein Dastghaibyfard
Delaunator should produce valid output even on highly degenerate input. It does so by depending on robust-predicates, a modern port of Jonathan Shewchuk's robust geometric predicates, an industry standard in computational geometry.
- delaunator-rs (Rust)
- fogleman/delaunay (Go)
- delaunator-cpp (C++)
- delaunator-sharp (C#)
- delaunator-ruby (Ruby)
- Delaunator-Python (Python)
- hx-delaunator (Haxe)
- ricardomatias/delaunator (Kotlin)
delaunator's People
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.