delaunator

Significantly improved robustness, fixing a few edge cases leading to a broken triangulation. #51

• Define tessellation of collinear input, returning an empty result with an ordered hull instead of throwing an error. Allows building Voronoi tessellation for degenerate cases. #47 (by @Fil)
• Added an update method for updating the triangulation after changing coords in place (useful for iterative relaxation algorithms). #48
• Improved performance by ~5-10%. #35
• Fixed a rare race condition that could lead to an infinite loop. #49

Improve performance further.

• Improved performance further, and made the algorithm easier to port to compiled languages. #32
• ⚠️ Breaking: hull API changed: delaunay.hull is now just a typed array of indices to hull edges in order (instead of a linked list). This wasn't publicly documented, but have to release a major version anyway because d3-delaunay depended on it.

Minor robustness improvements.

Improved numerical robustness.

• Improve performance on certain kinds of inputs. ~1.5x faster for grids, orders of magnitude faster for degenerate inputs like concentric circles.
• Fix race condition that produced broken triangulation on certain kinds of degenerate input, e.g. points on a circle.

• 🐞Fix a rare race condition that could produce corrupt halfedges structure. #25
• ✨Add a guide to Delaunator data structures by @redblobgames #23

Accept plain (non-typed) arrays in Delaunator constructor.

⚠️ breaking: Delaunator constructor now accepts a typed flat array of coordinates:

const coords = new Float64Array(x0, y0, x1, y1, ...);
const delaunay = new Delaunator()

For the old constructor behavior, use Delaunator.from:

const delaunay = Delaunator.from([[10, 10], [20, 20], ...]);

🍏 Delaunator can now be used as a ES module in environments that support them:

import Delaunator from 'delaunator';

• Add browser builds and CDN links (thanks @mbostock)
• Support default export in environments with ES modules
• A tiny performance improvement

Fixed an issue where halfedges structure would get invalid in rare cases. #11

• Expose delaunay.halfedges array for traversing the triangulation.
• Improve documentation.

~2x performance improvement! See #3

• ~17% faster triangulation.
• delaunay.triangles now returns a Int32Array instead of Array.