Delaunay32 claims over 10x faster exact 2D triangulation

Delaunay32 is a new C++17 library, released under the MIT license, for triangulating large sets of discrete two-dimensional points: pixels, raster samples, voxel projections, fixed-point geometry, and other quantized spatial data. Points are taken as signed 32-bit integers, including negative coordinates and large offsets, or as finite floating-point values that the library quantizes internally; either way, the triangle indices in the result reference the original input coordinates, not the quantized ones. According to its GitHub README, the design goal is a triangulator that is deterministic, robust, and particularly fast on large point sets.

The library combines exact integer orientation and in-circle predicates, certified for defined coordinate ranges, with a Morton-ordered divide-and-conquer algorithm, a compact two-dart mesh topology, and optional shared-memory multithreading. At a high level, the pipeline works by shifting all coordinates relative to the input's minimum values and establishing certified predicate precision, then generating Morton keys and radix-sorting the points, building small divide-and-conquer leaves with the exact predicates, and merging neighboring triangulations through compact edge rings; an optional final pass recovers constrained segments with edge flips and legalizes the remaining unconstrained edges. Beyond plain triangulation, Delaunay32 supports constrained Delaunay triangulation of noncrossing integer segments and triangulation of polygon domains that include holes, plus opt-in features such as halfedge adjacency, convex hull output, and deterministic duplicate-point handling.

The README's performance claims come from Release-build benchmarks run on one million points. In that setup, Delaunay32's own automatic multithreaded mode is defined as the 1.0x baseline, with lower ratios meaning faster; measured against it, for large point sets, delaunator-cpp took over 10 times as long and Fade2D, tested at version 2.17.3 with its bulk insertion API, took around 4 times as long. Because delaunator-cpp does not support constrained triangulation, it has no result in the benchmark's constrained-triangulation row; it is included in the repository purely as a submodule for that optional benchmark, and Delaunay32 itself does not depend on it. The README describes these figures as rounded averages across several point distributions, and, for the constrained case, several constraint layouts, and states plainly that the ratios are approximate and depend on the machine and workload.

Delaunay32 is MIT licensed and dependency-free for normal library use, built with CMake, and the README documents builds on Linux, macOS, and Windows, the last through Visual Studio's multi-configuration generator. An opt-in companion target, delaunay32::extras, adds point sampling, SVG export, and a documented JSON format for points, constraints and polygon rings, without the core triangulator depending on it. The README also flags a limitation: when float input is triangulated directly, only the edge decisions are computed on the internally quantized integer grid, so the resulting mesh is normally very close to, but not guaranteed identical to, an exact Delaunay triangulation of the original floating-point coordinates; differences are most likely near nearly coincident, collinear or cocircular points, and the README recommends an adaptive-exact triangulator instead when the exact float topology matters. The project situates itself within the established divide-and-conquer Delaunay literature, citing a 1985 paper by L. Guibas and J. Stolfi on subdivision manipulation and Voronoi diagrams, and a second paper by R. A. Dwyer whose title is cut off in the crawled page after the words 'A Faster Divide-and'.

Key facts

Delaunay32 is a new open-source (MIT licensed) C++17 library for exact, deterministic 2D Delaunay triangulation of large point sets, taking signed 32-bit integer coordinates or float input that it quantizes internally while keeping the output indexed to the original coordinates.
It combines exact integer orientation and in-circle predicates with a Morton-ordered divide-and-conquer algorithm, compact two-dart topology, and optional shared-memory multithreading.
In the project's own Release-build benchmarks on one million points, with Delaunay32's automatic multithreaded mode as the 1.0x baseline, delaunator-cpp took over 10 times as long and Fade2D 2.17.3 took around 4 times as long, for large point sets.
The library also supports constrained Delaunay triangulation of noncrossing integer segments and triangulation of polygon domains with holes, plus an opt-in extras module for point sampling, SVG export, and geometry JSON I/O.
The README states its benchmark ratios are rounded averages that are intentionally approximate and machine- and workload-dependent, and the crawled page names no author, release date, or test hardware.

Why it matters

Delaunay32's core pitch is combining three things that are often traded off against each other in triangulation libraries: exactness, determinism, and speed on large inputs. Because it works from signed 32-bit integer coordinates and exact orientation and in-circle predicates, its results do not depend on floating-point rounding, and duplicate points are handled deterministically rather than arbitrarily; that matters for reproducible pipelines that need the same triangulation every time given the same input. On top of that, the project's own Release-build benchmarks on one million points report Delaunay32's automatic multithreaded mode running over 10 times faster than delaunator-cpp and around 4 times faster than Fade2D 2.17.3 for large point sets. The library also natively supports constrained triangulation and polygon domains with holes, features that otherwise often require pairing a plain Delaunay library with separate constraint-handling code.

Who it affects

The library targets C++17 developers working with large, already-discrete or quantizable 2D point sets: image-space geometry, raster and height-field samples, projected voxel data, fixed-point maps, and other graphics or spatial datasets, per the README's own description of its intended use. Because it also accepts direct float input through triangulate_float(), it is usable for general graphics, mapping, visualization, and meshing work where exact edge topology is not required. Teams already using delaunator-cpp or Fade2D, the two libraries Delaunay32 benchmarks itself against, are the most direct comparison audience. Its MIT license and lack of runtime dependencies make it easy to drop into commercial or open-source projects on Linux, macOS, or Windows, the last built through Visual Studio.

How to use it

Delaunay32 is MIT licensed and, per the README, dependency-free for normal library use; delaunator-cpp is pulled in only as a submodule for the optional benchmark and is not a runtime dependency. It builds with CMake: cloning the repository, initializing the git submodule that supplies the optional benchmark dependency, then running CMake's usual configure, build, and install steps, with the benchmarks, tests, and examples individually toggleable through CMake flags. On Windows, the README calls for Visual Studio's Desktop development with C++ workload plus Git and CMake, using the multi-configuration generator so built binaries land under build\Release. The exported CMake targets are delaunay32::delaunay32 for the core triangulator and an optional delaunay32::extras for companion utilities such as point sampling, SVG export, and a documented geometry JSON format; the extras target links to the core, never the reverse. At the API level, triangulate_int() and triangulate_float() cover plain triangulation, triangulate_constrained_int() adds edge constraints, and triangulate_polygon_int() triangulates a polygon domain with holes; 'full' variants of these calls add halfedge adjacency, convex hull output, duplicate-point representative mapping, and, for float input, a QuantizationReport with the grid step, measured coordinate error, and collision count.

How solid is it

Every number here comes from Delaunay32's own GitHub README, and the crawled page gives no hardware specification for the Release-build benchmark despite stating that its ratios are machine- and workload-dependent. No absolute timings, in seconds or milliseconds, are given for any test; every reported result is a multiple of Delaunay32's own 1.0x baseline. The comparison names one specific version, Fade2D 2.17.3, but Delaunay32's own version number does not appear anywhere in the crawled text, and no author, maintainer, organization, or release date is named either. On Hacker News, the submission (by user oryx1729) had drawn 39 points and 5 comments after roughly five and a half days online, a modest and slow-moving discussion that has not yet produced independent scrutiny of the benchmark claims.

Risks and caveats

The float-input path is an approximation, not an exact computation: triangulate_float() keeps the original coordinates but computes edge decisions on an internally quantized integer grid, so the resulting mesh, while normally very close to an exact floating-point Delaunay triangulation, is not guaranteed to have identical edges, with the biggest risk near nearly coincident, collinear, or cocircular points; the README directs readers who need exact float topology to use an adaptive-exact triangulator instead. Polygon triangulation has firm structural limits: rings must be simple and may not cross or touch one another, holes must sit strictly inside the outer ring without overlapping or nesting, and the implementation does not insert intersection or Steiner points to work around violations. A single Triangulator instance is not safe to call concurrently, so parallel use requires separate instances. And because the speed claims are self-reported, rounded averages that the README itself calls approximate, actual results on any particular machine or dataset may land meaningfully above or below the over 10x and around 4x figures quoted.

“For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.”

— Delaunay32, in its GitHub README