GitHub - morishuz/delaunay32: Fast, parallel 2D Delaunay triangulation using exact integer predicates

Fast, parallel 2D Delaunay triangulation using exact integer predicates, with direct float input. Delaunay32 is a C++17 library for triangulating large sets of discrete 2D points: pixels, raster samples, voxel projections, fixed-point geometry, and other quantized spatial data. Finite float points can also be passed directly; the library quantizes them internally while output indices continue to reference the original coordinates. It combines exact integer predicates with a Morton-ordered divide-and-conquer algorithm, compact two-dart topology, and optional multithreading. The result is a triangulator that is deterministic, robust, and particularly fast on large point sets. For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D. Highlights Exact orientation and in-circle predicates for certified coordinate ranges Signed 32-bit integer input, including negative coordinates and large offsets Serial and shared-memory parallel execution Deterministic handling of duplicate points Constrained Delaunay triangulation for noncrossing integer segments Triangle indices referencing the original input, counterclockwise on the triangulation grid Opt-in halfedge adjacency, convex hull, and duplicate representative mapping Automatic, fixed-step, or fixed-scale float quantization with precision limits and collision policies Optional delaunay32::extras companion target for point sampling, Delaunay32 geometry JSON, domain queries, and SVG export MIT licensed and dependency-free for normal library use Documentation Usage guide: complete API, type, exactness, quantization, threading, and error contracts Changelog: release notes and breaking API changes Contributing guide: bug reports, validation, and pull request expectations Security policy: supported versions and private reporting Float SVG example: end-to-end float input with a QuantizationReport Constrained SVG example: ordinary and constrained triangulations of the same fixed geometry Polygon SVG example: a concave integer domain with three holes and points omitted by domain clipping Polygon logo SVG example: fresh blue-noise points inside ten JSON-defined polygonal glyph domains Integer SVG example: generated or JSON integer input When to use it Delaunay32 is intended for data that is already discrete or can tolerate a high-resolution uniform quantization. Typical examples include image-space geometry, raster and height-field samples, projected voxel data, fixed-point maps, graphics, and projected spatial datasets. Direct float input is practical for most graphics, mapping, visualization, and general meshing applications where exact edge topology is not required. triangulate_float() keeps source coordinates untouched and returns indices into the original input. Only the edge decisions use internally quantized integer coordinates. The resulting mesh will normally be very close to one computed directly from the source values, but its edges are not guaranteed to be identical. Differences are most likely for nearly coincident, collinear, or cocircular points. Use an adaptive-exact triangulator when the precise Delaunay topology of the original floating-point coordinates is required. Performance The following results summarize Release-build benchmarks with one million points. Delaunay32 automatic multithreaded mode is the 1.0× baseline, and lower is better: 4.0× means an implementation took approximately four times as long. Each comparison used identical input points for every library. Results are rounded averages across the measured point distributions and, for constrained triangulation, several representative constraint layouts. workload Delaunay32 Fade2D delaunator-cpp Unconstrained Delaunay 1.0× ~4.5× ~11× Constrained Delaunay 1.0× ~4.3× — delaunator-cpp does not support constrained triangulation, so no result is shown for it in the constrained row. The Fade2D results were measured with Fade2D 2.17.3 using its bulk insertion API. delaunator-cpp is included as a submodule solely for the optional benchmark. Delaunay32 itself does not depend on it. These ratios are intentionally approximate and remain machine- and workload-dependent. The repository includes a detailed benchmark comparing unconstrained Delaunay32 with delaunator-cpp across different point distributions. Run it on your machine for more detailed performance information. Quick start Clone the repository and initialize the optional benchmark dependency: git submodule update --init --recursive cmake -S . -B build -DCMAKE_BUILD_TYPE=Release cmake --build build -j ctest --test-dir build --output-on-failure For a library-only build, Delaunator is not required: cmake -S . -B build \ -DCMAKE_BUILD_TYPE=Release \ -DDELAUNAY32_BUILD_BENCHMARKS=OFF \ -DDELAUNAY32_BUILD_TESTS=OFF \ -DDELAUNAY32_BUILD_EXAMPLES=OFF cmake --build build -j The separately linked extras companion is built by default. Add -DDELAUNAY32_BUILD_EXTRAS=OFF for a strictly core-only build. Install with: cmake --install build Windows with MSVC Install Visual Studio with the Desktop development with C++ workload, plus Git and CMake. From PowerShell, use the multi-configuration Visual Studio generator as follows: git submodule update --init --recursive cmake -S . -B build cmake --build build --config Release --parallel ctest --test-dir build -C Release --output-on-failure cmake --install build --config Release Unlike single-configuration Linux and macOS builds, Visual Studio selects the configuration when building, testing, and installing. Built executables are therefore under build\Release\, for example build\Release\delaunay_benchmark.exe. The exported CMake targets are delaunay32::delaunay32 for triangulation and delaunay32::extras for the optional companion utilities. The extras target links to the core target; the core target never links to extras. Usage Integer input #include <delaunay32/delaunay.hpp> #include <vector> int main() { std::vector<delaunay32::Point> points = { {0, 0}, {100, 0}, {100, 100}, {0, 100}, {48, 37}, }; // 1 selects the serial path; 0 selects the hardware thread count.