Delaunay32

Fast, parallel 2D Delaunay triangulation for signed 32-bit integer points.

Delaunay32 is a C++17 library built around exact integer predicates. A reusable Triangulator receives points, constraints, and polygon domains as one configured problem, then builds and exports the topology in a single triangulate() call.

The core API accepts std::int32_t coordinates exclusively. Floating-point input is converted explicitly with the standalone quantize() utility before it reaches the triangulator.

For browser and JavaScript/TypeScript use, see the Delaunay32 WebAssembly package and its interactive demo.

Measured runtime for one million unique, unconstrained integer points on an Apple M1 (8 cores, 16 GB RAM), with triangle-only output. Relative runtime is normalized to eight-thread Delaunay32. Lower is better:

• Exact predicates for every accepted integer input
• Serial or shared-memory parallel execution
• Deterministic coincident-point handling
• Standalone constraints and disjoint polygon domains with holes
• One batched topology for constraints and all polygon boundaries
• Triangle-only or full topology results with an operation report
• Explicit, configurable float-to-integer quantization
• Original input indices in every returned triangle
• No bundled third-party source dependencies

The default top-level build includes the library, extras, tests, benchmark, and the complete example suite:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
ctest --test-dir build --output-on-failure

For a library-only build:

cmake -S . -B build \
  -DDELAUNAY32_BUILD_BENCHMARKS=OFF \
  -DDELAUNAY32_BUILD_EXTRAS=OFF \
  -DDELAUNAY32_BUILD_EXAMPLES=OFF \
  -DDELAUNAY32_BUILD_TESTS=OFF
cmake --build build --parallel

Link the core CMake target as delaunay32::delaunay32. Optional JSON, sampling, and SVG utilities are available through delaunay32::extras.

#include <delaunay32/delaunay.hpp>

#include <vector>

int main() {
    const std::vector<delaunay32::Point> points = {
        {0, 0}, {100, 0}, {100, 100}, {0, 100}, {48, 37},
    };

    delaunay32::TriangulationOptions options;
    options.thread_count = 0; // Select the hardware thread count.

    delaunay32::Triangulator triangulator;
    triangulator.set_options(options);
    triangulator.set_points(points);
    const delaunay32::TriangulationResult result =
        triangulator.triangulate();

    for (const delaunay32::Triangle& triangle : result.triangles) {
        const auto& a = points[triangle.i0];
        const auto& b = points[triangle.i1];
        const auto& c = points[triangle.i2];
        // a, b, c are counterclockwise.
    }
}

triangulate() consumes the configured problem, including when it throws. Call set_points() to begin another problem. This clears the previous constraints and polygon domains while preserving options, allocations, and worker threads.

Constraints and polygons are configured before the run:

triangulator.set_points(points);
triangulator.set_constraints(constraints);
triangulator.set_polygons(polygons);
const auto result = triangulator.triangulate();

For adjacency, the complete input hull, and duplicate representatives, select ResultDetail::Full. Triangle detail is the default.

Floating-point conversion is deliberately separate:

#include <delaunay32/quantization.hpp>

const delaunay32::QuantizationResult converted =
    delaunay32::quantize(float_points);

triangulator.set_points(converted.points);
const auto result = triangulator.triangulate();

The converted vector preserves the source length and index order. Its QuantizationReport records the mapping, measured error, and collisions.

• Usage guide — lifecycle, quantization, constraints, polygons, and results
• Hello mesh example — minimal fixed-point triangulation and SVG output
• Constraints example — require a simple indexed polyline in the mesh
• Polygon example — triangulate one outer ring with one hole
• Quantization example — large nearby floats, conversion modes, reports, and rejection policies
• Logo example — one batched multi-domain run
• Changelog — release history and breaking changes
• Release process — maintainer checklist

Run ./build/delaunay_benchmark --quick for a short local performance run across uniform, clustered, and diagonal point distributions.

With extras enabled, ./build/delaunay_workload_benchmark --quick also covers constraints, full results, SVG recording/serialization, and bounds/disconnected polygon sampling. Omit --quick for larger fixtures and seven measured runs. CSV results report median milliseconds; input generation is excluded, while output destruction and (for triangulation) set_points() are included.

MIT. See LICENSE. Third-party dependency status is recorded in THIRD_PARTY.md.