Security News

### JSR Working Group Kicks Off with Ambitious Roadmap and Plans for Open Governance

At its inaugural meeting, the JSR Working Group outlined plans for an open governance model and a roadmap to enhance JavaScript package management.

Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →

delaunator

Advanced tools

An incredibly fast JavaScript library for Delaunay triangulation of 2D points

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.

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/delaunator@5.0.0';
</script>
```

Or use a browser UMD build that exposes a `Delaunator`

global variable:

```
<script src="https://unpkg.com/delaunator@5.0.0/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)
- ricardomatias/delaunator (Kotlin)
- delaunator-java (Java)
- delaunay-Stata (Stata/Mata)
- Delaunator.jl (Julia)

FAQs

An incredibly fast JavaScript library for Delaunay triangulation of 2D points

The npm package delaunator receives a total of **1,836,744** 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

At its inaugural meeting, the JSR Working Group outlined plans for an open governance model and a roadmap to enhance JavaScript package management.

By Sarah Gooding - Nov 05, 2024

Security News

Research

An advanced npm supply chain attack is leveraging Ethereum smart contracts for decentralized, persistent malware control, evading traditional defenses.

By Kush Pandya, Philipp Burckhardt, Kirill Boychenko, Orlando Barrera - Oct 31, 2024

Security News

Research

Attackers are impersonating Sindre Sorhus on npm with a fake 'chalk-node' package containing a malicious backdoor to compromise developers' projects.

By Kirill Boychenko - Oct 31, 2024