4 ms·
You can compute Voronoi diagrams for each pixel of an image with distance fields in O(N) where N is the number of pixels. This is faster than the shown jump fl
by geometryguy 4y ago
You can compute Voronoi diagrams for each pixel of an image with distance fields in O(N) where N is the number of pixels. This is faster than the shown jump flooding algorithm, which is only O(N log N).
Here is an example for a CPU-based implementation: https://github.com/983/df https://github.com/983/df
It is not difficult to implement for the GPU because the algorithm can be run in parallel for each image row and column, assuming general GPU compute capability, which admittedly is still lacking in some browsers.
- SOLAR_FIELDS 4y agoDistance field approach is actually discussed in the article. One thing that is interesting to point out, is how these approaches differ from the classic approach: Fortune's algorithm: https://en.wikipedia.org/wiki/Fortune%27s_algorithm https://en.wikipedia.org/wiki/Fortune%27s_algorithm One particular differential to make is the "where" part here. O(N) always sounds good, but in this particular discussion we note that O(N) is the number of pixels, whereas in Fortune's algorithm O(N log N) time and O(N) space is the number of points. I wonder which one is faster and if it depends on the input. For example, I imagine a massive field with quintillions of pixels and only two or three points - it seems Fortune's would be the way to go. Now I imagine another massive field with quintillions of pixels and trillions of points. Now I might be interested in doing a distance field like approach.
- geometryguy 4y ago