Nascent Political Miscreant

    delaunator
    DefinitelyTyped icon, indicating that this package has TypeScript declarations provided by the separate @types/delaunator package

    5.0.0 • Public • Published

    Delaunator Build Status

    An incredibly fast JavaScript library for Delaunay triangulation of 2D points.

    Delaunay triangulation example

    Projects based on Delaunator

    • d3-delaunay for Voronoi diagrams, search, traversal and rendering (a part of D3).
    • d3-geo-voronoi for Delaunay triangulations and Voronoi diagrams on a sphere (e.g. for geographic locations).

    Ports to other languages

    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@4.0.1/delaunator.min.js"></script> <!-- minified build -->
    <script src="https://unpkg.com/delaunator@4.0.1/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 an array of point coordinates of the form: [x0, y0, x1, y1, ...] (use a typed array for best performance).

    delaunay.triangles

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

    delaunay.hull

    A Uint32Array array of indices that reference points on the convex hull of the input data, counter-clockwise.

    delaunay.coords

    An array of input coordinates in the form [x0, y0, x1, y1, ....], of the type provided in the constructor (or Float64Array if you used Delaunator.from).

    delaunay.update()

    Updates the triangulation if you modified delaunay.coords values in place, avoiding expensive memory allocations. Useful for iterative relaxation algorithms such as Lloyd's.

    Performance

    Benchmark results against other Delaunay JS libraries (npm run bench on Macbook Pro Retina 15" 2017, Node v10.10.0):

      uniform 100k gauss 100k grid 100k degen 100k uniform 1 million gauss 1 million grid 1 million degen 1 million
    delaunator 82ms 61ms 66ms 25ms 1.07s 950ms 830ms 278ms
    faster‑delaunay 473ms 411ms 272ms 68ms 4.27s 4.62s 4.3s 810ms
    incremental‑delaunay 547ms 505ms 172ms 528ms 5.9s 6.08s 2.11s 6.09s
    d3‑voronoi 972ms 909ms 358ms 720ms 15.04s 13.86s 5.55s 11.13s
    delaunay‑fast 3.8s 4s 12.57s timeout 132s 138s 399s timeout
    delaunay 4.85s 5.73s 15.05s timeout 156s 178s 326s timeout
    delaunay‑triangulate 2.24s 2.04s OOM 1.51s OOM OOM OOM OOM
    cdt2d 45s 51s 118s 17s timeout timeout timeout timeout

    Papers

    The algorithm is based on ideas from the following papers:

    Install

    npm i delaunator

    DownloadsWeekly Downloads

    1,470,937

    Version

    5.0.0

    License

    ISC

    Unpacked Size

    55 kB

    Total Files

    6

    Last publish

    Collaborators

    • mapbox-npm-01
    • mapbox-npm-02
    • mapbox-npm-07
    • mapbox-npm-03
    • mapbox-npm-04
    • mapbox-npm-09
    • mapbox-npm-05
    • mapbox-npm-06
    • mapbox-npm-08
    • mapbox-npm-advanced-actions
    • mapbox-npm-ci
    • mapbox-npm
    • mapbox-admin
    • mapbox-machine-user
    • mourner