4 ms·
This isn't actually a voronoi diagram, it is an (approximate) distance transform - though it is still pretty cool! If you are working on a grid, there are lots
by 33a 10y ago
This isn't actually a voronoi diagram, it is an (approximate) distance transform - though it is still pretty cool!
If you are working on a grid, there are lots of ways to compute distance transforms exactly. An exact and optimal serial algorithm which works for any metric is due to Meijster, and it runs in O(n) time in the number of pixels:
http://parmanoir.com/distance/ http://parmanoir.com/distance/
Distance transforms are a special kind of (max, +) convolution, and have lots of interesting algebraic properties
- vanderZwan 10y agoThe linked paper specifically says "Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform," so are you sure it's not both in this case?
- 33a 10y agoTo compute a voronoi diagram, you also need to reconstruct the boundary and topology of all the cells, which is not being done here. Also most algorithms for computing voronoi diagrams do not snap the vertices to integer lattice coordinates.
- vanderZwan 10y agoWould it be fair to say this is a fast rasterization algorithm?