Delaunay32: 10x Faster Exact Delaunay Triangulation for Large Point Sets
Exact, parallel 2D Delaunay triangulation for int32 coordinates
Delaunay32 is a C++17 library for fast, parallel 2D Delaunay triangulation using exact integer predicates. It handles large sets of discrete points (pixels, raster samples, fixed-point geometry) and accepts float input directly, quantizing internally while preserving original coordinates. Benchmarks show it is over 10× faster than delaunator-cpp and about 4× faster than Fade2D on one million points. Features include constrained Delaunay, polygon support with holes, deterministic duplicates handling, and optional multithreading. The library is MIT-licensed and dependency-free.
For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.
- rezaprima
from the site
> For large point sets, Delaunay32 is over 10× faster than delaunator-cpp and around 4× faster than Fade2D.
- hingler36
Great project!
Are vertex insertion and deletion also supported/accelerated?
What compromises are keeping this constrained to 32-bit? It seems like you could cut back on quantization error by increasing bits, but if you're doing some manual SIMD magic to get this performance I can understand sticking with 32 bits.
- MattCruikshank
Neat, now do a 3D Delaunay tetrahedrization! :)