3 ms·

Generating Voronoi diagrams using Fortune's algorithm

204 points by redpenguin101 2y ago

dartos 2y ago
What’re the odds! I just did this with Common Lisp!
bambax 2y ago
There is an implementation of that algorithm in JS by Raymond Hill (of uBlock Origin fame): https://github.com/gorhill/Javascript-Voronoi https://github.com/gorhill/Javascript-Voronoi I toyed with it here to have it move: https://animations.adgent.com/voronoi.html https://animations.adgent.com/voronoi.html
- bloopernova 2y ago
  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 :)
  - Sharlin 2y ago
    The technique used in A Scanner Darkly is called rotoscoping, btw.
vvern 2y ago
I made an implementation in clojurescript that animates the algorithm as it goes a while back: https://voronoi.ajwerner.net/#/app-diagrams 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 https://github.com/mapbox/delaunator
- fuzzythinker 2y ago
  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?
  - vvern 2y ago
    It’s all open source, sorry there was no link! https://github.com/ajwerner/voronoi https://github.com/ajwerner/voronoi
Jarmsy 2y ago
A few years back I made this 3d visualisation https://x.com/KangarooPhysics/status/1253336959755251716 https://x.com/KangarooPhysics/status/1253336959755251716
- itishappy 2y ago
  Wow, this made everything click for me. Really nice animation!
talkingtab 2y ago
D3js has a new implementation https://github.com/d3/d3-delaunay 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 https://github.com/d3/d3-voronoi
Kloopvram 2y ago
Cool! Interesting that D3 moved away from Fortune's algorithm to https://mapbox.github.io/delaunator/ 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."
- rikroots 2y ago
  Oh - that's interesting! If D3 think delaunator is the best approach to this sort of effect, then there's no more excuses (beyond my natural procrastination) to stop me adding it to my canvas library: the current code I use to calculate tiles is painfully naive! New discussion: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120 https://github.com/KaliedaRik/Scrawl-canvas/discussions/120
chefandy 2y ago
Houdini’s 3D Voronoi tools are fun.
deleted 2y ago
[deleted]
figomore 2y ago
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.
- mikhailfranco 2y ago
  Build a 3D scene of distinctly colored right circular cones with their apexes at the 2D planar vertices, and their axes perpendicular to the plane. 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).
  - alejohausner 2y ago
    You don't have to use cones. Paraboloids work too.
ulahngising 2y ago
[dead]
bloomingkales 2y ago
Ah, the original latent space.
jahebohay 2y ago
[dead]
omoikane 2y ago
See also: https://news.ycombinator.com/item?id=37998923 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. https://en.wikipedia.org/wiki/Jump_flooding_algorithm https://en.wikipedia.org/wiki/Jump_flooding_algorithm
pfdietz 2y ago
This made me look up where Steve is these days. I knew him decades ago.

204 points by redpenguin101 2y ago

What’re the odds! I just did this with Common Lisp!

There is an implementation of that algorithm in JS by Raymond Hill (of uBlock Origin fame): https://github.com/gorhill/Javascript-Voronoi https://github.com/gorhill/Javascript-Voronoi I toyed with it here to have it move: https://animations.adgent.com/voronoi.html https://animations.adgent.com/voronoi.html

bloopernova 2y ago
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 :)
- Sharlin 2y ago
  The technique used in A Scanner Darkly is called rotoscoping, btw.

vvern 2y ago

I made an implementation in clojurescript that animates the algorithm as it goes a while back: https://voronoi.ajwerner.net/#/app-diagrams 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 https://github.com/mapbox/delaunator

fuzzythinker 2y ago
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?
- vvern 2y ago
  It’s all open source, sorry there was no link! https://github.com/ajwerner/voronoi https://github.com/ajwerner/voronoi

Jarmsy 2y ago

A few years back I made this 3d visualisation https://x.com/KangarooPhysics/status/1253336959755251716 https://x.com/KangarooPhysics/status/1253336959755251716

itishappy 2y ago
Wow, this made everything click for me. Really nice animation!

talkingtab 2y ago

D3js has a new implementation https://github.com/d3/d3-delaunay 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 https://github.com/d3/d3-voronoi

Kloopvram 2y ago

Cool! Interesting that D3 moved away from Fortune's algorithm to https://mapbox.github.io/delaunator/ 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."

rikroots 2y ago
Oh - that's interesting! If D3 think delaunator is the best approach to this sort of effect, then there's no more excuses (beyond my natural procrastination) to stop me adding it to my canvas library: the current code I use to calculate tiles is painfully naive! New discussion: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120 https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

chefandy 2y ago

Houdini’s 3D Voronoi tools are fun.

deleted 2y ago

[deleted]

figomore 2y ago

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.

mikhailfranco 2y ago
Build a 3D scene of distinctly colored right circular cones with their apexes at the 2D planar vertices, and their axes perpendicular to the plane. 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).
- alejohausner 2y ago
  You don't have to use cones. Paraboloids work too.

ulahngising 2y ago

[dead]

bloomingkales 2y ago

Ah, the original latent space.

jahebohay 2y ago

[dead]

omoikane 2y ago

See also: https://news.ycombinator.com/item?id=37998923 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. https://en.wikipedia.org/wiki/Jump_flooding_algorithm https://en.wikipedia.org/wiki/Jump_flooding_algorithm

pfdietz 2y ago

This made me look up where Steve is these days. I knew him decades ago.