[omoikane]

My favorite algorithm for generating Voronoi diagrams is the Jumping flood algorithm:

https://en.wikipedia.org/wiki/Jump_flooding_algorithm

This is an approximate algorithm that only works in pixel space, but it's lots of fun to implement (simpler to implement than Fortune's algorithm).

[mikhailfranco]

For discrete Voronoi, just render cones from the vertices, using OpenGL/WebGL. Encode the vertex ID in the color. The z-buffer does all the work. Read back the framebuffer.

Just ignore Big O analysis. I guarantee any kind of GPU will blow all CPU algorithms out of the water. This has been known for at least 30 years - I believe there was an SGI demo of it back in the day.

OpenGL can also do edge detection image processing (Laplacian convolution) and give you the line boundaries, if that's what you need. Perhaps a jittered double-rendering can give the same result.

If the resolution is not enough, just multiply the canvas size - x2, x4 ... it will still be faster.

[zimpenfish]

I've implemented JFA successfully (in C) using nothing but the original paper but still haven't managed to get my head around Fortune. It's one of those things that's just crying out for someone to make a "This is how ..." tutorial / walkthrough kind of thing for.