delaunator
Advanced tools
Package description
The delaunator npm package is a fast library for Delaunay triangulation of 2D points. It is used to triangulate a set of points into a mesh of triangles, which is a fundamental operation in many geometric algorithms. The package is particularly useful in graphics, geographical information systems (GIS), and for performing various computational geometry tasks.
Triangulation
This feature allows you to perform Delaunay triangulation on an array of points. The 'triangles' property of the resulting object contains the indices of the points that form the triangles.
const Delaunator = require('delaunator');
const points = [[0, 0], [1, 0], [1, 1], [0, 1]];
const delaunay = Delaunator.from(points);
console.log(delaunay.triangles);Hull
This feature provides the convex hull of the input points as an array of point indices that are in the hull. The hull is the outermost 'shell' of the triangulation.
const Delaunator = require('delaunator');
const points = [[0, 0], [1, 0], [1, 1], [0, 1]];
const delaunay = Delaunator.from(points);
console.log(delaunay.hull);Coordinates Conversion
Delaunator can also take a flat array of coordinates and perform triangulation. This is useful when working with data that is not already structured as an array of points.
const Delaunator = require('delaunator');
const coords = [0, 0, 1, 0, 1, 1, 0, 1];
const delaunay = Delaunator.from(coords);
console.log(delaunay.triangles);Earcut is a fast, header-only polygon triangulation library. It's similar to delaunator but focuses on converting polygons to triangles, which is useful for rendering complex shapes in computer graphics.
Trianglify is a library for generating colorful triangle meshes that can be used as SVG images and CSS backgrounds. While delaunator focuses on the triangulation algorithm, Trianglify builds on top of it to create visually appealing patterns.
Poly2Tri is a 2D constrained Delaunay triangulation library. Unlike delaunator, which only works with point sets, Poly2Tri can handle complex polygons with holes and Steiner points, making it more suitable for certain GIS applications.
Readme
A really fast JavaScript library for Delaunay triangulation of 2D points.
var points = [[168, 180], [168, 178], [168, 179], [168, 181], [168, 183], ...];
var delaunay = new Delaunator(points);
console.log(delaunay.triangles);
// [623, 636, 619, 636, 444, 619, ...]
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 flat Int32Array 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 (var i = 0; i < triangles.length; i += 3) {
coordinates.push([
points[triangles[i]],
points[triangles[i + 1]],
points[triangles[i + 2]]
]);
}
A flat 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.
Benchmark results against four fastest other libraries
(bench.js on Macbook Pro Retina mid-2012, Node v7.9.0):
| library | 10,000 | 20,000 | 50,000 | 100,000 | 200,000 | 500,000 | 1,000,000 |
|---|---|---|---|---|---|---|---|
| delaunator | 25ms | 32ms | 105ms | 168ms | 350ms | 974ms | 2.46s |
| faster-delaunay | 78ms | 140ms | 328ms | 776ms | 1.74s | 3.87s | 6.99s |
| incremental-delaunay | 81ms | 154ms | 428ms | 874ms | 1.74s | 4.3s | 9.03s |
| d3-voronoi | 154ms | 250ms | 534ms | 1.19s | 2.7s | 7.37s | 18.36s |
| delaunay-fast | 136ms | 386ms | 1.18s | 3.03s | 7.95s | 28.2s | 76.96s |
| library | 10,000 | 20,000 | 50,000 | 100,000 | 200,000 | 500,000 | 1,000,000 |
|---|---|---|---|---|---|---|---|
| delaunator | 24ms | 27ms | 109ms | 170ms | 327ms | 941ms | 2.03s |
| faster-delaunay | 76ms | 172ms | 291ms | 692ms | 1.19s | 3.46s | 6.36s |
| incremental-delaunay | 74ms | 154ms | 410ms | 806ms | 1.67s | 4.27s | 8.3s |
| d3-voronoi | 164ms | 264ms | 522ms | 1.16s | 2.67s | 7.64s | 18.62s |
| delaunay-fast | 152ms | 340ms | 1.19s | 3.2s | 8.37s | 30.03s | 82.05s |
The algorithm is based on ideas from the following papers:
FAQs
An incredibly fast JavaScript library for Delaunay triangulation of 2D points
The npm package delaunator receives a total of 2,835,561 weekly downloads. As such, delaunator popularity was classified as popular.
We found that delaunator demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 29 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Researchers recently demonstrated that the npm Registry is vulnerable to cache poisoning combined with DoS, posing significant risks for package availability.
Security News
The June TC39 meeting wrapped up this week with eight proposals moving on to the next stage. Here's a quick roundup of the features that the committee approved to advance.
Security News
Cyber extortion in the US and Canada hit record levels in 2023, with ransomware attacks surging and median ransom demands skyrocketing, though fewer companies are choosing to pay ransoms.