Generating Voronoi Diagrams Using Fortune's Algorithm (With Odin)
8 comments
·February 8, 2025bambax
bloopernova
Your animation reminded me of the style used in A Scanner Darkly (2006)
I wonder if it's possible to use video as an input to an algorithm that displays using Voronoi? Probably at that point it wouldn't be a Voronoi diagram, but it might look cool :)
Jarmsy
A few years back I made this 3d visualisation https://x.com/KangarooPhysics/status/1253336959755251716
vvern
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
talkingtab
D3js has a new implementation
https://github.com/d3/d3-delaunay
at the bottom of that page is a discussion of the sweep algorithm used and a list of other (non-javascript) language implentations.
The original d3-voronoi is deprecated but can be found here:
Kloopvram
Cool! Interesting that D3 moved away from Fortune's algorithm to https://mapbox.github.io/delaunator/ because it
"is 5-10× faster than d3-voronoi to construct the Delaunay triangulation or the Voronoi diagram, is more robust numerically, has Canvas rendering built-in, allows traversal of the Delaunay graph, and a variety of other improvements."
null
chefandy
Houdini’s 3D Voronoi tools are fun.
There is an implementation of that algorithm in JS by Raymond Hill (of uBlock Origin fame):
https://github.com/gorhill/Javascript-Voronoi
I toyed with it here to have it move:
https://animations.adgent.com/voronoi.html