This made me look up where Steve is these days. I knew him decades ago.
Generating Voronoi diagrams using Fortune's algorithm
21–23 of 23 posts
Re: Generating Voronoi diagrams using Fortune's algorithm
#22If 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.
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).
You don't have to use cones. Paraboloids work too.
Re: Generating Voronoi diagrams using Fortune's algorithm
#23Cool! 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."
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