A really fast JavaScript library for Delaunay triangulation of 2D points. Implements a variation of the Sweep-hull algorithm.
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 indices (each group of three numbers forms a triangle).
Benchmark results against three 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 | 26ms | 40ms | 174ms | 327ms | 658ms | 2.07s | 4.95s |
| faster-delaunay | 78ms | 140ms | 328ms | 776ms | 1.74s | 3.87s | 6.99s |
| incremental-delaunay | 81ms | 154ms | 428ms | 874ms | 1.74s | 4.3s | 9.03s |
| 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 | 22ms | 39ms | 162ms | 270ms | 586ms | 1.86s | 4.53s |
| faster-delaunay | 76ms | 172ms | 291ms | 692ms | 1.19s | 3.46s | 6.36s |
| incremental-delaunay | 74ms | 154ms | 410ms | 806ms | 1.67s | 4.27s | 8.3s |
| delaunay-fast | 152ms | 340ms | 1.19s | 3.2s | 8.37s | 30.03s | 82.05s |
The algorithm is based on ideas from the following papers:
- A simple sweep-line Delaunay triangulation algorithm, 2013, Liu Yonghe, Feng Jinming, Shao Yuehong
- S-hull: a fast radial sweep-hull routine for Delaunay triangulation, 2010, David Sinclair