Delaunator

5.1.0 · active · verified Sun Apr 19

Delaunator is an incredibly fast and robust JavaScript library designed for generating Delaunay triangulations of 2D points. Currently stable at version 5.1.0, it maintains an active release cadence, consistently delivering performance enhancements and numerical robustness. A key differentiator is its exceptional speed, validated through extensive benchmarks, and its ability to handle degenerate floating-point inputs reliably by integrating `robust-predicates`. It serves as a foundational component for other critical computational geometry libraries like `d3-delaunay` and `d3-geo-voronoi`, extending its utility to Voronoi diagrams and geographic applications. As of v5.0.0, it transitioned to ES Modules by default, necessitating Node.js v12+ environments, and v5.1.0 introduced first-class TypeScript types, making the separate `@types/delaunator` package obsolete.

Common errors

```
ReferenceError: require is not defined
```
cause Attempting to use CommonJS `require()` syntax in an ES Module environment (e.g., Node.js with `"type": "module"` in `package.json`) after Delaunator v5.0.0.

fix Change your import statement to `import Delaunator from 'delaunator';`. Ensure your project is set up to handle ES Modules, or use a bundler if targeting older environments.
```
SyntaxError: Cannot use import statement outside a module
```
cause Attempting to use an ES Module `import` statement in a CommonJS context (e.g., Node.js without `"type": "module"` or an old browser script tag).

fix For Node.js, add `"type": "module"` to your `package.json`. For browsers, use a bundler (like Webpack or Rollup) to transpile to a compatible format, or load via `<script type="module">` for modern browsers, or use the UMD build (`<script src="https://unpkg.com/delaunator/delaunator.min.js"></script>`).
```
TypeError: delaunay.hull.next is not a function
```
cause Using code that expects the pre-v3.0.1 linked-list `hull` API with Delaunator v3.0.1 or later, where `hull` became a `Uint32Array`.

fix Update your code to iterate over `delaunay.hull` as a `Uint32Array` of point indices instead of traversing a linked list. E.g., `for (const i of delaunay.hull) { /* ... */ }`.
```
TS2307: Cannot find module 'delaunator' or its corresponding type declarations.
```
cause TypeScript compiler cannot find type definitions for `delaunator`. This could happen if `@types/delaunator` is missing in versions prior to 5.1.0, or if TypeScript configuration is incorrect.

fix If using Delaunator < 5.1.0, install `@types/delaunator` (`npm install -D @types/delaunator`). If using v5.1.0+, ensure `@types/delaunator` is uninstalled and your `tsconfig.json` `moduleResolution` is set appropriately (e.g., `"node16"` or `"bundler"`).

Warnings

breaking Delaunator now exposes itself as an ES Module by default (`"type": "module"`), which means CommonJS `require()` is no longer directly supported. This requires Node.js v12+ or a compatible build setup.
Fix: Use `import Delaunator from 'delaunator';` for ESM environments. For older Node.js or CommonJS projects, you might need to transpile your code or configure your bundler to handle ESM dependencies.
breaking Transpilation of the library itself has been removed. This means native support for older browsers like IE11 is no longer provided out-of-the-box. Consumers needing support for such environments must transpile `delaunator` in their build process.
Fix: Configure your build tools (e.g., Babel) to transpile `node_modules/delaunator` if you need to support environments without modern JavaScript features.
breaking The `delaunay.hull` API changed from a linked list structure to a `Uint32Array` of point indices. While previously undocumented, downstream libraries like `d3-delaunay` depended on the old structure, making this a breaking change for some users.
Fix: Access convex hull points as an ordered array of indices, `delaunay.hull`, instead of attempting to traverse a linked list structure. Update any code that iterated through `hull` via `.next` properties.
deprecated First-class TypeScript types are now shipped directly with the `delaunator` package, rendering the separate `@types/delaunator` package obsolete and unnecessary.
Fix: Uninstall `@types/delaunator` from your project (`npm uninstall @types/delaunator` or `yarn remove @types/delaunator`). The types are now automatically included when you install `delaunator` itself.
gotcha The input coordinate format differs between the constructor `new Delaunator(coords)` (which expects a flat array `[x0, y0, x1, y1, ...]`) and the static factory method `Delaunator.from(points)` (which expects an array of arrays `[[x0, y0], [x1, y1], ...]`). Using the wrong format will lead to incorrect triangulations or errors.
Fix: Ensure you are using the correct input format for the method you choose. For `new Delaunator()`, provide a flat array or `Float64Array`. For `Delaunator.from()`, provide an array of point arrays, or customize with `getX` and `getY` accessors.

Install

npm install delaunator npm
yarn add delaunator yarn
pnpm add delaunator pnpm

Imports

Delaunator
wrong:
```
const Delaunator = require('delaunator');
```
correct:
```
import Delaunator from 'delaunator';
```
Since v5.0.0, Delaunator is an ES Module by default, requiring Node.js v12+ or a module-aware bundler. CommonJS `require` will fail unless transpiled or configured.

Delaunator.from

wrong:

import { from } from 'delaunator';

correct:

import Delaunator from 'delaunator';
const points = [[0, 0], [1, 1]];
const delaunay = Delaunator.from(points);

`from` is a static method on the default export `Delaunator`, not a named export itself.

Delaunator (type)
wrong:
```
import { Delaunator } from 'delaunator';
```
correct:
```
import type Delaunator from 'delaunator';
```
For TypeScript, `Delaunator` is a default export for both value and type. Using `import type` is preferred for type-only imports. Since v5.1.0, `@types/delaunator` is no longer needed.

Quickstart

This example initializes Delaunator with a flat array of coordinates and logs the resulting triangle, half-edge, and convex hull indices, demonstrating basic usage.

import Delaunator from 'delaunator';

const coords = new Float64Array([
    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('Triangle vertex indices:', delaunay.triangles);
console.log('Half-edge indices for traversal:', delaunay.halfedges);
console.log('Convex hull point indices (counter-clockwise):', delaunay.hull);

// Example: Retrieve the coordinates of the first triangle
if (delaunay.triangles.length >= 3) {
    const i0 = delaunay.triangles[0];
    const i1 = delaunay.triangles[1];
    const i2 = delaunay.triangles[2];
    const triangleCoords = [
        [coords[2 * i0], coords[2 * i0 + 1]],
        [coords[2 * i1], coords[2 * i1 + 1]],
        [coords[2 * i2], coords[2 * i2 + 1]]
    ];
    console.log('Coordinates of the first triangle:', triangleCoords);
}

view raw JSON →