Exact, parallel 2D Delaunay triangulation for int32 coordinates
Meet Delaunay32, a C++17 library for blazing-fast, parallel 2D Delaunay triangulation, achieving over 10x performance gains on large datasets. It leverages exact integer predicates and careful design for robustness and determinism, handling both integer and quantized float inputs. This technical powerhouse offers a highly optimized and reliable open-source solution for graphics, mapping, and meshing applications.
The Lowdown
Delaunay32 is a powerful C++17 library designed for efficient and robust 2D Delaunay triangulation of large discrete point sets. It caters to applications ranging from pixel data and raster samples to fixed-point geometry, offering significant speed improvements over existing solutions while maintaining exactness and determinism.
- Core Technology: The library employs exact integer predicates combined with a Morton-ordered divide-and-conquer algorithm and compact two-dart topology.
- Performance: It boasts impressive speed, being over 10 times faster than
delaunator-cppand approximately 4 times faster thanFade2Dfor large point sets, validated through benchmarks. - Input Flexibility: It supports signed 32-bit integer coordinates directly and also handles finite
floatpoints by quantizing them internally, preserving original float indices in the output. - Key Features: Includes serial and shared-memory parallel execution, deterministic handling of duplicate points, constrained Delaunay triangulation, polygon triangulation with holes, and optional extras for sampling and SVG export.
- Robustness: Guarantees exact orientation and in-circle predicates for certified coordinate ranges, ensuring high precision for critical applications.
- Architectural Design: Follows established divide-and-conquer Delaunay family algorithms, using techniques like radix sorting and parallel merging to optimize performance.
- Licensing: The library is MIT licensed, promoting open and flexible use without dependencies for its core functionality.
Delaunay32 stands out as a high-performance, robust, and open-source option for developers requiring fast and exact 2D Delaunay triangulation, particularly where data can be uniformly quantized or is inherently discrete. Its comprehensive feature set and proven speed make it a valuable tool for a variety of computational geometry tasks.