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.

Awright, makin some VoroNOIZE!

I love these demos!

I look forward to reading this code. I didn’t know about the C++ implementation. The algorithm as described in Fortune’s paper generalizes easily to weighted sites, but it’s hard for me to see how his own C code would support that.

Nice work! looks very beautiful)

amazing to see such a complex process running so fast within the flash player.

really great demos and definitely great blog :)

Thanks everyone for the nice comments! I’ll try to put up a decent API these days, we’ll see how quickly it will be running once it’s actually doing something useful

This is really cool, and very useful. But… looking at the source code, my head exploded. This source code makes me feel very stupid… is it strange? I’m kind of new to flash so I guess i need to dunk my head in professional code from time to time. :)

Hey, the algo makes use of heavy inlining of the original methods (actually there’s one method remaining to be inlined, so it’ll get worse) in order to save those few milliseconds that kick up the framerate a little more. What’s good is that everything is coded only once, which doesn’t bloat the source code as automated inlining would tempt one to do, so it’s kind of space-efficient also. What’s bad is that I might have exaggerated with reusing the same variables, so the code may indeed not be terribly readable.

What you can do, if you are really interested, is to compare my port to the original c++ code, that might give you some ideas and insights about basic code refactoring.

If you have any questions, don’t hesitate to drop me a line. Don’t explode that head, you’ll need it next time.

This is great, I had a quick look into the source and it’s quite complex, amazing you get that speed! I am going to try it in the future for some live face 3D triangulation. Very nice blog Hristo – subscribed :)

Nice to hear, thanks for the comment!

The speed of your implementation is really impressive, so I’m currently checking it out since the one I have been using until now is Delaunay based and not running 100% perfect.

I ran into an issue with your code where it sometimes displays me rougue or dangling edges and I suspect it is caused by the intersection at line 482:

z.x = ( a.p.x * a.p.x + ( a.p.y – p.y ) * ( a.p.y – p.y ) – p.x * p.x ) / ( 2 * a.p.x – 2 * p.x );

It turns out that 2 * a.p.x – 2 * p.x can become 0 which makes z.x infinite. Are you using a different version of your code in the examples since I don’t see that bug there?

Hey Mario,

First of all, great to hear from all of you great thinkers here, its quite a kick actually. And no, not really, if you check out the audio demo, you’ve got some artifacts that might be due to what you have pinpointed – have you tried to simply deny the case of non-numeric Numbers as coordinates?

Please share your sources; I’ll have to put up a decent result datastructure for the solver anyway, so I’ll be working on this code again eventually.

Ha : I am actually. I’ll update the source – the intersection code is the same though. Tell me what happens.

Very, very cool! I’ll give this a look, hopefully it can be used to obtain delaunay triangulations too, which are extremely useful for building 3D meshes. Thanks for sharing!

Here’s a little experiment I did with your code. It tries to set out the principles for creating a fast ‘Worley’ noise routine by using fortune’s algorithm.

http://www.lidev.com.ar/demos/voronoi/noise/

Do you have any suggestions for obtaining the Delaunay Triangulation out of your code?

Hey Li!

If you want to get the Delaunay Triangulation out of this code, right now, you simply have to do all the math yourself.

What I had and still have to do, is to make it output actual geometry, not a bunch of anonymous segments, so that you can run whatever processing you want on the polygons later.

Right now, best go to Nicoptere’s experimentorium, you have both Voronoi and Delaunay there produced by the same algo.

Cheers and sorry for my late reply,

Hristo

I am curious to know if you used the double linked list or the binary tree implementation?

I actually did refer to the same double linked list reference implementation, tried to get some sample output, and I realized that it wasn’t exactly giving all the edges as required.

So I tried to do one in c\c++ with the binary tree instead since it was hard to visualize the double linked list. I won’t say that the binary tree one is working completely well either. I managed to get some of the missing edges but just that not all the end points of the edges are correct at the moment.

A double linked list. The underlying data-structure shouldn’t be influencing your output really; there’s another problem with the implementation which could yield some artefacts, Mario described it pretty well a few comments above.

Choosing between double-linked and binary tree depends on what you want to achieve – if you’re planning to render huge graphs with tens of thousands of vertices, a binary tree will probably speed things up. However, for real time stuff in flash, where you’d probably have less than a thousand vertices, a double linked list, with approximative lookup of a ‘nearest’ arc before intersection tests kick in could be cheaper than the tree reorganisation logic.

This said, I have little to no experience with binary trees, so I might be wrong.

marvellous monsieur !

delaunay/voronoi makes beautiful sense to me – check CGAL for inspiration (c++)

- but i think real time 3d modelling through AR input in flash is coming! anyone interested? I think so !

I absolutely agree with the previous post – a double linked list (plus a nice dictionary object for keeping the whole thing tidy) is the way to go ….inline code is the new oop … (only kidding!) – but yes, i think perhaps its time to get mr j. ebert into this conversation for some SERIOUS optimisations – this is a real case for pushin it to the max……lovin your work!…hope to ping pong a few files of my own to add to the conversation v soon. all power to your elbow – ancient alexandria had nothing on the new mathematical playground – we are all allowed to play now ! j

Hi Hristo,

Great library! I’m really enjoying working with it. I found a small issue, and wanted to let you know about it. If there are two or more points with exactly the same x value that are the furthest point to the left, you will see a lot of strange artifacts, with overlapping surfaces. The issue appears to be in the intersection function in Fortune.as in the if statement where p0.x == p1.x. It looks like there needs to be another condition there.

Its late here, so I took the easy way out and added a new point so far to the extreme left that the issue never surfaces. I feel so lazy. ;)

Justin

Thanks! And point taken … one day I’ll have to come back to this code, it needs a lot of work unFortunately hihi

Very cool! I’m happy to see somebody managed to do something awesome based on my old hastily-written C++ code.

Hey Matt!

Actually, I’m seeing that, except for the link, I haven’t really explicitly credited you for the code in the post – sorry for that, will fix it.

Meanwhile, have you got any clues about the math problems we’re seeing here? Is it my interpretation of your math that’s off?

Thanks!

Nice work and impressive speed with your demo’s.

My own experiments don’t run this fast, yet.

Wanted to look at your source but noticed there gone.

You probably didn’t get around to do it after your WP blog collapsed.

Hi. Links to .as files are broken. :(

Most excellent – getting a 404 when trying to access the source – can u please update links ?

Thanks again.

Hi hristo,

It seems the links to your source files are down.

Any way I could still get my hands on them? Your examples look beautiful and run smooth, would love to use that code if I might.

Kind regards,

Sven

Hi there. Congrats for such an awesome work. It looks like the source code is not longer available. Is it possible to download it from somewhere else?

Cheers!

Thanks for posting the code back!