[HN Gopher] Generating Voronoi diagrams using Fortune's algorithm
       ___________________________________________________________________
        
       Generating Voronoi diagrams using Fortune's algorithm
        
       Author : redpenguin101
       Score  : 193 points
       Date   : 2025-02-08 10:41 UTC (1 days ago)
        
 (HTM) web link (redpenguin101.github.io)
 (TXT) w3m dump (redpenguin101.github.io)
        
       | bambax wrote:
       | 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
        
         | bloopernova wrote:
         | 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 wrote:
           | The technique used in A Scanner Darkly is called rotoscoping,
           | btw.
        
       | vvern wrote:
       | 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
        
         | fuzzythinker wrote:
         | 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 wrote:
           | It's all open source, sorry there was no link!
           | 
           | https://github.com/ajwerner/voronoi
        
       | Jarmsy wrote:
       | A few years back I made this 3d visualisation
       | https://x.com/KangarooPhysics/status/1253336959755251716
        
         | itishappy wrote:
         | Wow, this made everything click for me. Really nice animation!
        
       | talkingtab wrote:
       | 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
        
       | Kloopvram wrote:
       | Cool! Interesting that D3 moved away from Fortune's algorithm to
       | https://mapbox.github.io/delaunator/ because it
       | 
       | "is 5-10x 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 wrote:
         | 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
        
       | chefandy wrote:
       | Houdini's 3D Voronoi tools are fun.
        
       | figomore wrote:
       | 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 wrote:
         | 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 wrote:
           | You don't have to use cones. Paraboloids work too.
        
       | bloomingkales wrote:
       | Ah, the original latent space.
        
       | dartos wrote:
       | What're the odds!
       | 
       | I just did this with Common Lisp!
        
       | omoikane wrote:
       | See also:
       | 
       | 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
        
       | pfdietz wrote:
       | This made me look up where Steve is these days. I knew him
       | decades ago.
        
       ___________________________________________________________________
       (page generated 2025-02-09 23:02 UTC)