Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Generating Voronoi diagrams using Fortune's algorithm

redpenguin101.github.io

Post reply on HN
Print view View original

1–10 of 23 posts

Re: Generating Voronoi diagrams using Fortune's algorithm

#3

Post by 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

Re: Generating Voronoi diagrams using Fortune's algorithm

#5

Post by 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:

https://github.com/d3/d3-voronoi

Re: Generating Voronoi diagrams using Fortune's algorithm

#6

Post by 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."

Re: Generating Voronoi diagrams using Fortune's algorithm

#9

Post by bloopernova »

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 reply on HN