Delaunator: a Delaunay triangulation built on flat typed arrays

Ten lines to a triangulation

The library does one thing, and the shortest possible demonstration is ten coordinates on one line. Coordinates are passed as a flat array of x and y pairs:

const coords = [377,479,  453,434,  326,387,  444,359,  511,389,
                586,429,  470,315,  622,493,  627,367,  570,314];
const delaunay = new Delaunator(coords);
console.log(delaunay.triangles);

The output is an array of triangle vertex indices, each group of three numbers forming a triangle, and all triangles are directed counterclockwise.

Installation is a normal npm install followed by an ES module import:

import Delaunator from 'delaunator';

For a browser there are two documented routes: an ES module import from a CDN, or a UMD build that exposes a `Delaunator` global. The package metadata lists `delaunator.min.js` for both jsdelivr and unpkg, and the `files` array ships `index.js`, `index.d.ts`, `delaunator.js` and `delaunator.min.js`.

One detail in the API description is easy to miss and worth repeating: use a typed array for best performance. The constructor takes whatever you give it and returns `coords` as an array of the type you passed, or `Float64Array` if you used `Delaunator.from`.

Flat arrays and the half-edge trick

The three accessors on the result object are what you actually work with. `triangles` is a `Uint32Array` of vertex indices. `halfedges` is an `Int32Array` where the i-th half-edge corresponds to vertex `triangles[i]` coming from it, and `halfedges[i]` is the index of the twin half-edge in the adjacent triangle, or `-1` for outer half-edges on the convex hull.

That second array is the whole reason the library performs well. A conventional half-edge structure allocates objects per edge; this one stores indices into the same triangle array, so traversal is arithmetic rather than pointer chasing.

The readme does not pretend this is comfortable. It states directly that the flat array-based data structures might be counterintuitive, then names them as one of the key reasons the library is fast. That is an honest framing: you are trading code clarity for throughput, and the decision is visible.

`hull` is a `Uint32Array` of indices referencing the points on the convex hull, counterclockwise. If you only need the hull and nothing else, you still pay for the full triangulation, since the hull is a by-product of the sweep rather than a cheaper query.

There is also `delaunay.update()`, which re-triangulates after you have modified `coords` values in place, avoiding expensive memory allocations. The readme points at iterative relaxation algorithms such as Lloyd's as the intended use, where you move points and recompute repeatedly.

Array input, duplicate skipping, and reading triangles back

`Delaunator.from(points[, getX, getY])` takes an array of points instead of a flat array, assuming `[x, y]` by default. The optional `getX` and `getY` functions accept any point shape, which is how you feed it objects. Duplicate points are skipped.

Because indices in `triangles` refer to positions in whatever you passed, turning indices back into coordinates differs between the two entry points. With `from`, each index maps to one element of `points`:

for (let i = 0; i < triangles.length; i += 3) {
    coordinates.push([
        points[triangles[i]],
        points[triangles[i + 1]],
        points[triangles[i + 2]]
    ]);
}

With the flat constructor, each index has to be doubled to reach its coordinate:

for (let i = 0; i < triangles.length; i += 3) {
    coordinates.push([
        [coords[2 * triangles[i]],     coords[2 * triangles[i] + 1]],
        [coords[2 * triangles[i + 1]], coords[2 * triangles[i + 1] + 1]],
        [coords[2 * triangles[i + 2]], coords[2 * triangles[i + 2] + 1]]
    ]);
}

Getting this wrong is easy because both loops look nearly identical and the failure is silent, producing coordinates read from the wrong offsets. If you find yourself debugging garbage triangles, check which constructor you used before you check the library.

The repository also points out that this is a building block rather than a finished product. `d3-delaunay` uses it for Voronoi diagrams, search, traversal and rendering as part of D3, and `d3-geo-voronoi` for triangulations on a sphere for geographic locations. If you need either of those, use those rather than assembling them here.

What the benchmark table does and does not tell you

The README carries a full comparison against seven other JavaScript Delaunay libraries across four point distributions and two sizes, and it is worth reading closely because it dates itself. The stated conditions are `npm run bench` on a Macbook Pro Retina 15 inch 2017 with Node v10.10.0.

At 100k points, Delaunator reports 82ms uniform, 61ms gaussian, 66ms grid and 25ms degenerate, against 473ms for the nearest alternative on the uniform case. At one million points the picture is starker: 1.07s uniform and 950ms gaussian, where `delaunay-fast` needs 132s and 138s and `delaunay-triangulate` runs out of memory.

Two honest caveats. Node v10 is old enough that the absolute numbers say little about current hardware, so the ratios are the usable information. And several competitors report timeouts or OOM at one million points, which tells you about their scaling more than about Delaunator's absolute speed.

The degenerate column is the one to watch, since that is where numerical stability shows up. Delaunator's 25ms and 278ms figures against 68ms and 810ms for the nearest rival are consistent with the exact predicate work described further down.

The algorithm itself is credited to three papers: a sweep-line Delaunay triangulation algorithm by Liu Yonghe, Feng Jinming and Shao Yuehong from 2013, S-hull, a fast radial sweep-hull routine by David Sinclair from 2010, and a faster circle-sweep algorithm by Ahmad Biniaz and Gholamhossein Dastghaibyfard from 2011.

The ES module break and what version 5 changed

Version 5.0.0 in March 2021 was a two-part breaking release and both parts still shape who can use the library today.

The first was switching to ES modules by default with `"type": "module"`, requiring Node 12 or newer. The second was removing transpilation, which dropped IE11 support out of the box. The release notes phrase the second as a consequence: consumers needing to support older browsers must transpile the code themselves. The `package.json` now requires a newer floor than that, with `engines` no longer specified in the metadata but the ESM assumption baked into `main`, `module` and `type` all pointing at `index.js`.

That same release made what the notes describe as full numerical reliability by switching orientation checks to `robust-predicates`, a modern port of Jonathan Shewchuk.s exact geometric predicates. The consequence is stated in the README: Delaunator should produce valid output even on highly degenerate input. Shewchuk's predicates are an industry standard in computational geometry for exactly this problem, and they are the library's only runtime dependency at `^3.0.2`.

Two smaller changes since then. v5.0.1 in January 2024 was a slightly smaller bundle. v5.1.0 in March 2026 added first-class TypeScript types maintained inside the library, so `@types/delaunator` is no longer necessary, which matters for a package whose `types` field already pointed at `index.d.ts`.

The port list is long enough to be a signal about how settled the algorithm is: Rust, Go, C++, C#, Ruby, Python, PyTorch and others, each linked from the README as an independent port.

Repository shape and where the docs live

The tree is compact for a library with this many users. `index.js` is the implementation, `bench.js` the benchmark harness referenced by the table, `test/` holds the test suite, and `rollup.config.js` produces the bundles. `tsconfig.json` and `eslint.config.js` sit alongside, with the linter running against `index.js`, the test file, `bench.js`, the rollup config and `docs/diagrams.js`.

Two entries earn their keep. `CODEOWNERS` means specific people are on the hook for specific paths, and `delaunator.png` plus `docs/example.png` are the images the README embeds.

The test script is `tsc && node test/test.js`, with lint running first via `pretest`, so type checking is part of the suite rather than a separate concern. There is also a coverage script using `node --experimental-test-coverage`, which puts the project on Node's built-in test runner rather than a third-party framework, and `prepublishOnly` runs both test and build.

Documentation is split between the README and a hosted site at mapbox.github.io/delaunator, which holds an interactive demo and what the README calls a guide to data structures. That guide is the more useful of the two for anyone working with `halfedges`, since the README's own admission that the flat structures are counterintuitive is not resolved in the README itself.

The last push to `main` was 2026-06-24, and the repository is not archived, with 5 open issues against 2,624 stars. The license field reports ISC and `LICENSE` is in the tree, so there is no ambiguity to resolve here about terms.

Editorial conclusion

Delaunator is small, dependency-light and fast because it commits to a data structure choice rather than hiding it: a flat `Uint32Array` of triangle indices and a parallel `Int32Array` of half-edges, which is awkward to consume and cheap to traverse. The 2021 switch to exact orientation predicates is the other thing worth knowing, since it turned a class of degenerate-input failures into valid output at the cost of one dependency. The benchmark table dates from a 2017 MacBook Pro and Node v10, so read the ratios rather than the milliseconds. If you want Voronoi diagrams, reach for d3-delaunay, which wraps this library; if you want to modify coordinates in place, `update()` exists for iterative relaxation. Start with `new Delaunator(coords)` on a flat coordinate array, and use `convert` style input only if you actually have objects.

Frequently asked questions

Official sources

1. License: ISC
2. mapbox/delaunator on GitHub
3. Project website
4. README
5. Releases