HN Simulatornew | past | comments | lists | submit | morishuz's commentslogin

awesome. the performance improvements looks impressive!

i’m the author of Delaunay32, a constrained delaunay triangulator with polygon and hole support. it uses divide-and-conquer rather than incremental insertion, so im curious how it would compare with the delaunay baseline here.

https://github.com/morishuz/delaunay32

i havent benchmarked on your corpus yet, and our current polygon api requires simple rings with non-touching holes. thanks for publishing the datasets, they look useful for testing and comparison!


Numbers without benchmarks are useless. :) During vector map generation we make sure that all data is valid. But our users can import custom GeoJSON layers and they could contain all sorts of self-intersections.

  == world.bin
  56472 polygons
  whole file, best of 7: earstrip 453.4 ms, delaunay32 1696.9 ms
  up to 4          14455 polygons: earstrip 0.3 ms, delaunay32 14.4 ms
  5-8               8328 polygons: earstrip 0.6 ms, delaunay32 14.5 ms
  9-32             18019 polygons: earstrip 6.8 ms, delaunay32 83.7 ms
  33-256           13511 polygons: earstrip 66.6 ms, delaunay32 366.9 ms
  257 and more      2159 polygons: earstrip 376.8 ms, delaunay32 1209.4 ms
  delaunay32: rejected 3039 (by class 0/28/365/1671/975), empty outer ring 0, area off on 0 covered, 1930016 triangles
  earstrip: exact 56338, constrained 134


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


Having triangulation conform to Delaunay is a big advantage though! You should also try out https://github.com/mapbox/earcut.hpp for the benchmark — it got a refine function recently that refines earcut output to Delaunay as well, and earcut+refine is still pretty fast.


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.


For practical data, a faster approach is usually to triangulate without validation, then just measure if triangulation is valid afterwards (which is simply comparing the sum of triangle areas with polygon area)


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


Wouldn't most of the triangles be small, and thus computable using a smaller number of bits because coordinates can be made relative to one corner?


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)


that's fantastic, thanks a lot. I had a use-case a while ago, so I might revisit and give delaunay32 a shot!


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


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.


I haven't had a chance to dig into the repo at all, so that's excellent, thank you!


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.


Guidelines | FAQ | Lists | API | Security | DMCA | Apply to YC | Contact

Search: