Generating Voronoi diagrams using Fortune's algorithm

Post by ulahngising » Sat, Feb 08, 2025, 5:08 PM UTC

Post by dartos » Sat, Feb 08, 2025, 5:18 PM UTC

Post by Sharlin » Sat, Feb 08, 2025, 5:44 PM UTC

bloopernova wrote: post #9

bambax wrote: post #2

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

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 :)

Post by vvern » Sat, Feb 08, 2025, 8:22 PM UTC

fuzzythinker wrote: post #17

vvern wrote: post #3

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…

The animation is the best I've seen. I see the "old" implementation link in the references page; any chance of open sourcing the current animation one?

Post by mikhailfranco » Sun, Feb 09, 2025, 6:16 AM UTC

figomore wrote: post #10

If you are not interested in the edges, only painting the sites with different colors, you can use a variation of flood fill starting with the seeds and only stacking the pixel if that color has distance lower than the one already painted that pixel.