morishuz

thanks, good suggestion! earcut plus refine sounds like sensible comparison.

i’ve since reproduced the world dataset benchmark locally and found that polygon validation was taking about two-thirds of delaunay32’s time on the accepted inputs.

ok interesting, thanks for actually running the comparison! looks like it clearly favors earstrip on this workload

For one million unconstrained points on the reference Apple M1 system, eight-thread Delaunay32 completes in roughly 50 ms.

Using that as the 1.0× baseline: • Delaunay32, one thread: ~2.8× runtime. • Fade2D, automatic threads: ~4.5×. • Fade2D, one thread: ~6×. • delaunator-cpp: ~11×. • Triangle: ~11×.

yes, there are currently two modes for internal integer math: 64 and 128 bit. (the internal int math needs larger ranges than the inputs since we work with squares etc)

64bit integers works with an input coordinate range of 29,609. this is typically fine for raster image coordinates or floats that can allow for some quantization (only the triangles/edges are affected by this not the original points!)

if the input range is larger than 29,609, the algorithm switches to a 128bit implementation with a range of 1,940,470,527 which is close to, but still smaller than, what could theoretically be stored in an int32 value. hence that's why the input is currently only up to int32.

in theory it could be extended to 64bit input range but it comes with performance and portability trade-offs that currently don't seem worth it

great. and do let me know if you have any feature requests, noticed bugs etc

for a one million points set i measured 4x faster when using single threaded and 11x when using multi-threaded delaunay32 vs triangle (on my Apple M1)

very nice!

the repo comes with a benchmark tool that you can run on your own machine, which already compares multi vs single threading as well as delaunator-cpp (which is only single threaded)

At one million points, Delaunay32 takes about 147–150 ms with one thread versus 540–555 ms for delaunator-cpp on my machine, so roughly 3.7× faster. Automatic eight-thread mode Delaunay32 takes about 53–54 ms.

thanks!

(i am the author of Delaunay32)

> Are vertex insertion and deletion also supported/accelerated?

no unfortunately not, since this is currently a fast batch triangulator, so vertex insertion/deletion requires rebuilding

>What compromises are keeping this constrained to 32-bit?

it isn’t SIMD-specific. the circle test involves squared coordinates and further multiplications. therefore, 32-bit coordinates inputs can already require 128-bit temporary results internally. Supporting 64-bit exactly would require roughly 256-bit intermediates and come at the cost of speed and portability, so i think 32bit is currently a good trade-off.