Delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D poin...

Geometry
mapbox/delaunatormapbox.github.io/delaunator/delaunator

README

Delaunator Build Status undefined undefined


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

- Interactive Demo
- Guide to data structures

Delaunay triangulation example

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


  1. ``` js
  2. const coords = [168,180, 168,178, 168,179, 168,181, 168,183, ...];

  4. const delaunay = new Delaunator(coords);
  5. console.log(delaunay.triangles);
  6. // [623, 636, 619,  636, 444, 619, ...]
  7. ```

Install


Install with NPM (npm install delaunator) or Yarn (yarn add delaunator), then import as an ES module:

  1. ``` js
  2. import Delaunator from 'delaunator';
  3. ```

To use as a module in a browser:

  1. ``` html
  2. <script type="module">
  3.     import Delaunator from 'https://cdn.skypack.dev/delaunator@5.0.0';
  4. </script>
  5. ```

Or use a browser UMD build that exposes a Delaunator global variable:

  1. ``` html
  2. <script src="https://unpkg.com/delaunator@5.0.0/delaunator.min.js"></script>
  3. ```

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:

  1. ``` js
  2. for (let i = 0; i < triangles.length; i += 3) {
  3.     coordinates.push([
  4.         points[triangles[i]],
  5.         points[triangles[i + 1]],
  6.         points[triangles[i + 2]]
  7.     ]);
  8. }
  9. ```

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)