delaunator

What is delaunator?

The delaunator npm package is a fast library for Delaunay triangulation of 2D points. It is used to triangulate a set of points into a mesh of triangles, which is a fundamental operation in many geometric algorithms. The package is particularly useful in graphics, geographical information systems (GIS), and for performing various computational geometry tasks.

What are delaunator's main functionalities?

Triangulation

This feature allows you to perform Delaunay triangulation on an array of points. The 'triangles' property of the resulting object contains the indices of the points that form the triangles.

const Delaunator = require('delaunator');
const points = [[0, 0], [1, 0], [1, 1], [0, 1]];
const delaunay = Delaunator.from(points);
console.log(delaunay.triangles);

Hull

This feature provides the convex hull of the input points as an array of point indices that are in the hull. The hull is the outermost 'shell' of the triangulation.

const Delaunator = require('delaunator');
const points = [[0, 0], [1, 0], [1, 1], [0, 1]];
const delaunay = Delaunator.from(points);
console.log(delaunay.hull);

Coordinates Conversion

Delaunator can also take a flat array of coordinates and perform triangulation. This is useful when working with data that is not already structured as an array of points.

const Delaunator = require('delaunator');
const coords = [0, 0, 1, 0, 1, 1, 0, 1];
const delaunay = Delaunator.from(coords);
console.log(delaunay.triangles);

Other packages similar to delaunator

earcut

Earcut is a fast, header-only polygon triangulation library. It's similar to delaunator but focuses on converting polygons to triangles, which is useful for rendering complex shapes in computer graphics.

trianglify

Trianglify is a library for generating colorful triangle meshes that can be used as SVG images and CSS backgrounds. While delaunator focuses on the triangulation algorithm, Trianglify builds on top of it to create visually appealing patterns.

p2t

Poly2Tri is a 2D constrained Delaunay triangulation library. Unlike delaunator, which only works with point sets, Poly2Tri can handle complex polygons with holes and Steiner points, making it more suitable for certain GIS applications.

README

delaunator

A really fast JavaScript library for Delaunay triangulation of 2D points.

• Interactive Demo
• Guide to data structures

For Voronoi diagram computation, search, traversal and rendering, check out d3-delaunay which is based on Delaunator.

Example

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

const delaunay = Delaunator.from(points);
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
import Delaunator from 'delaunator';

// or require in Node / Browserify
const Delaunator = require('delaunator');

Or use a browser build directly:

<script src="https://unpkg.com/delaunator@2.0.2/delaunator.min.js"></script> <!-- minified build -->
<script src="https://unpkg.com/delaunator@2.0.2/delaunator.js"></script> <!-- dev build -->

API Reference

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.

new Delaunator(coords)

Constructs a delaunay triangulation object given a typed array of point coordinates of the form: [x0, y0, x1, y1, ...].

delaunay.triangles

A flat Int32Array 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:

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

delaunay.halfedges

A flat 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.

Performance

Benchmark results against four fastest other libraries (npm run bench on Macbook Pro Retina 15" 2017, Node v8.10.0):

library	10,000	20,000	50,000	100,000	200,000	500,000	1,000,000
delaunator	31ms	17ms	59ms	125ms	232ms	613ms	1.35s
faster-delaunay	48ms	88ms	243ms	447ms	1.02s	2.72s	4.95s
incremental-delaunay	56ms	131ms	309ms	577ms	1.12s	3.01s	6.37s
d3-voronoi	132ms	220ms	483ms	1s	2.27s	6.3s	12.67s
delaunay-fast	150ms	343ms	1.19s	3.35s	10.09s	41.09s	117.53s

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