A Voronoi diagram is a decomposition of space, here a 2d plane, on a nearest neighbour basis. The diagram splits the plane in regions, each corresponding to a site (a point of interest), and containing all the points closer to this site than to any other.

Voronoi diagrams have many applications, in fields as different as botanics and astrology. A few examples of computer graphic uses for Voronoi diagrams include procedural generation of organic forms, crazy image compression, beautiful fractals, noise, etc.

What got me in Voronoi mood however is seeing this this algorithmic collage by Santiago Ortiz from Bestiario. The work’s sheer visual impact shows off the one quality of Voronoi diagrams I appreciate the most – they look awesome. Watching the masks move for a couple of minutes got me terribly into porting Steve Fortune’s algorithm for Voronoi decomposition: I had to see for myself how much stuff could happen on the screen before the player choked.

### Fortune’s algorithm

Fortune’s algorithm, ideally, computes a Voronoi diagram in O(NlogN) time, where N is the number of sites, or the minimum possible time for the job, as O(NlogN) is the time-complexity of optimal sorting algorithms. It sweeps through the plane, maintaining a front of parabolas that progressively traces out the diagram, by spliting and adding curves for each site encountered, and removing arcs whenever a region vertex is determined with certainty. The Wikipedia article has it all explained pretty well, but if you need additional info, give this and this articles a try.

I began with this c++ implementation, which is a simplified take on the algorithm. The latter uses a binary tree for the composition of the beachline, whilst here we’ve got a double linked list. However, I do think that the double-link approach would do better for most visual applications in flash, where the cost of not having quick lookup of beachline parabolas might be offset by not having to reogranise the tree, and by the low overall number of particles. I ended up modifying and optimising most of the code however, and I bet this is the reason for the artifacts that show up every now and then in the last of the three demos.

Below you have a demo showing off 1000 regions, in line with nodename‘s mona-lisa tessalator:

Then 2000 points going around with their speed determined by the values of an image:

Finally, a simple audio visualiser:

Anyway, this really is just a study of how quickly the regions of a diagram can shape up without cheating. There is no bounding box intersection, nor sophisticated output options. Clearly, output of an optimal and informative data structure will be worth the performance kick, and if I get to do my graph theory homework, I’ll be coming back to this.

### Implementations

Fortune’s algorithm is already well implemented and made available by astatic, also nodename shows it off with his Voronoi toy, even though you don’t see the sources. You get a different tool for the same job by HIDIHO!, he goes through Delaunay triangulation, and then translates to a Voronoi decomposition, the two being dual graphs.