Delaunator

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

• Interactive Demo
• Guide to data structures

Projects based on Delaunator

• d3-delaunayfor Voronoi diagrams, search, traversal and rendering (a part ofD3).
• d3-geo-voronoifor Delaunay triangulations and Voronoi diagrams on a sphere (e.g. for geographic locations).

Example

constcoords=[168,180,168,178,168,179,168,181,168,183,...];

constdelaunay=newDelaunator(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:

importDelaunatorfrom'delaunator';

To use as a module in a browser:

<scripttype= "module">
importDelaunatorfrom'https://cdn.skypack.dev/[email protected]';
</script>

Or use a browser UMD build that exposes aDelaunatorglobal variable:

<scriptsrc= "https://unpkg.com/[email protected]/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). getXandgetYare optional functions of the form(point) => valuefor custom point formats. Duplicate points are skipped.

delaunay.triangles

AUint32Arrayarray 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(leti=0;i<triangles.length;i+=3){
coordinates.push([
points[triangles[i]],
points[triangles[i+1]],
points[triangles[i+2]]
]);
}

delaunay.halfedges

AInt32Arrayarray of triangle half-edge indices that allows you to traverse the triangulation. i-th half-edge in the array corresponds to vertextriangles[i]the half-edge is coming from. halfedges[i]is the index of a twin half-edge in an adjacent triangle (or-1for 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

AUint32Arrayarray 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 (orFloat64Arrayif you usedDelaunator.from).

delaunay.update()

Updates the triangulation if you modifieddelaunay.coordsvalues in place, avoiding expensive memory allocations. Useful for iterative relaxation algorithms such asLloyd's.

Performance

Benchmark results against other Delaunay JS libraries (npm run benchon 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 onrobust-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)