delaunator

I made an implementation in clojurescript that animates the algorithm as it goes a while back: https://voronoi.ajwerner.net/#/app-diagrams It’s a very beautiful algorithm. However, after that project I sort of came to dislike Fortune’s algorithm because it isn’t numerically stable with floating point numbers. If you have points that are colinear, or nearly colinear in fp, things can break. The delaunator is better in this regard iirc: https://github.com/mapbox/delaunator

Great article! How does this algorithm compare to others, e.g. sweep algorithms like the one used by delaunator[0]? An obvious difference is sweep algorithms sort the points in some way before adding them, is that a key to efficiency gains? 0: https://github.com/mapbox/delaunator/blob/main/README.md#pap...

You're right! In my experience, today JavaScript is so fast on careful code like this that even ports to C++ or Rust aren't much faster, and any gains would likely be offset by JS <-> WebAssembly communication overhead (although this is being rapidly improved). Here's a good thread with benchmarks that compare Earcut (also one of my libraries) to C++ and AssemblyScript WebAssembly ports: https://github.com/mapbox/mapbox-gl-js/issues/4835 (in short, mostly slower than JS) Another anecdotal example is that C++ and Rust ports of https://github.com/mapbox/delaunator (my Delaunay triangulation library) are only 10-15% faster.

I agree, Voronoi diagrams are so much fun! For that map project, at the last minute I switched to something slightly different. The page still says "Voronoi" but the actual demo doesn't use Voronoi. The Voronoi diagram uses the circumcenters of the triangles produced from Delaunay triangulation. I found that for my needs, the centroids worked better ("barycentric dual mesh"). Some comparison pictures here: https://www.redblobgames.com/x/1721-voronoi-alternative/ The graph connectivity is the same but the shapes are rounder. I've not implemented Fortune's myself. I use the Delaunator library, which maintains all the additional information I wanted in the form of a half-edge triangle mesh: https://github.com/mapbox/delaunator ; Mike Bostock wrote a Voronoi wrapper on top it: https://beta.observablehq.com/@mbostock/the-delaunays-dual