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

To use as a module in a browser:

Or use a browser UMD build that exposes a

To get the coordinates of all triangles, use:

The flat array-based data structures might be counterintuitive, but they're one of the key reasons this library is fast.

| uniform 100k | gauss 100k | grid 100k | degen 100k | uniform 1 million | gauss 1 million | grid 1 million | degen 1 million :-- | --: | --: | --: | --: | --: | --: | --: | --:

### Projects based on Delaunator

- 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).

## Example

```
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

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>`

## API Reference

#### new Delaunator(coords)

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).#### Delaunator.from(points, getX, getY)

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.#### delaunay.triangles

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]]
]);
}
```

#### delaunay.halfedges

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.

#### delaunay.hull

A`Uint32Array`

array of indices that reference points on the convex hull of the input data, counter-clockwise.#### delaunay.coords

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`

).#### delaunay.update()

Updates the triangulation if you modified`delaunay.coords`

values in place, avoiding expensive memory allocations.
Useful for iterative relaxation algorithms such as Lloyd's.## Performance

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## Papers

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

## Robustness

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.## Ports to other languages

- 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)