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
https://github.com/gorhill/Javascript-Voronoi
I toyed with it here to have it move:
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 :)
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:
Render a 2D orthographic view from 'above' the apexes.
The z-buffer will preserve pixels from the nearest apex.
(Yes, I now there are shadery ways to do this, but the classic 3D cones demo is trivial to understand and implement).
"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."
New discussion: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120
https://news.ycombinator.com/item?id=37998923 - Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm (2020)
The previous article and discussion contain short summaries of other algorithms. My favorite is still the Jump Flooding Algorithm.
I just did this with Common Lisp!
