Skip to content

Latest commit

 

History

History
90 lines (62 loc) · 3.77 KB

README.md

File metadata and controls

90 lines (62 loc) · 3.77 KB
Raw

delaunator

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

Build Status

Interactive Demo

Example

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, ...]

API Reference

new Delaunator(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.

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 (var 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 (bench.js on Macbook Pro Retina mid-2012, Node v7.9.0):

Uniform distribution

library 10,000 20,000 50,000 100,000 200,000 500,000 1,000,000
delaunator 25ms 32ms 105ms 168ms 350ms 974ms 2.46s
faster-delaunay 78ms 140ms 328ms 776ms 1.74s 3.87s 6.99s
incremental-delaunay 81ms 154ms 428ms 874ms 1.74s 4.3s 9.03s
d3-voronoi 154ms 250ms 534ms 1.19s 2.7s 7.37s 18.36s
delaunay-fast 136ms 386ms 1.18s 3.03s 7.95s 28.2s 76.96s

Gaussian distribution

library 10,000 20,000 50,000 100,000 200,000 500,000 1,000,000
delaunator 24ms 27ms 109ms 170ms 327ms 941ms 2.03s
faster-delaunay 76ms 172ms 291ms 692ms 1.19s 3.46s 6.36s
incremental-delaunay 74ms 154ms 410ms 806ms 1.67s 4.27s 8.3s
d3-voronoi 164ms 264ms 522ms 1.16s 2.67s 7.64s 18.62s
delaunay-fast 152ms 340ms 1.19s 3.2s 8.37s 30.03s 82.05s

Papers

The algorithm is based on ideas from the following papers: