Roll Over, Delaunay: Voronoi Library Goes Open-Source

By alan, on December 3rd, 2009

A few people have asked for the code for my Voronoi Toy. I haven’t made the entire program public yet, but I have released the underlying as3delaunay library, which I originally ported from Steven Fortune’s C implementation of his plane-sweep algorithm.

In addition to the Voronoi diagram and the Delaunay triangulation, the library also provides the convex hull, minimum and maximum spanning trees, and several other related geometric entities.

You can download the source and compile it, or just get the compiled swc from the downloads page.

So far I have had two users, JakeTastic (Voronoi shattering complete!) and Li (Faster Voronoi Noise); thanks to them both for jumping on, and to Jake also for finding the two bugs :-)

There’s no documentation yet, but there is a test suite which incorporates an example of using the library for nearest-site queries, and there’s also a mailing list, where I’ve archived Fortune’s paper and his C code, as well as a growing page of interesting links related to Voronoi/Delaunay.

The library is hosted on github, so YOU can conveniently modify, fix, or enhance it!

Roadmap for possible enhancements:
Generalize to support weighted Voronoi diagrams, both additive and multiplicative (This is described in Fortune’s paper)
Generalize to use an arbitrary polygon as a boundary
… what else?

Alan

Looks great Alan, also glad you’ve posted it to github.
alan

Thanks, Alan! (BTW Folks, that’s not me commenting on my own work, it’s Alan Klement.)
Pingback: My most important Twitter Messages #4 | der hess
Pingback: Voronoi diagrams and adaptive subdivision « Ken Huxley
http://www.m0ose.com dood

the delaunay library is really nice. I speed tested it against a couple different ones and it was very fast with dense points.
Also, in the code, the _triangles.push(blabla) is commented out. Why is that? it seems to work fine with it included.
alan

@dood: Thanks for your comments! I just haven’t needed the triangles data per se — it’s redundant information for me, so I decided to save a little time by commenting it out — but I did want to document that the data is available in that format. Glad to hear it works OK!
http://starpause.com/ jordan

thanks for sharing this library … was having fun playing with the toy so i’m looking forward to using this for some VJ tricks!
Pingback: basics in generative art 6 : TRIANGLE « HIDIHO!
http://www.darrellplank.com Darrell Plank

Hi-
I’ve done a Fortune algorithm in C# and it’s working fine, but I’m messing around a bit with trying to properly clip the infinite cells to a box. This is mainly so I can do Lloyd relaxation. I think you return your cells clipped so you must have done this already and I’m wondering if you ran into the same problems I’m running into. Without going into a lot of detail, after dealing with the potential of 1 or possibly 2 doubly infinite lines surrounding your cell due to collinear input points, rays that may originate outside the box and intersect 0, 1 (at one of the box corners) or 2 times or may originate inside the box in which case life becomes a bit easier – anyway, lots of little nitpicky cases. I’m wondering if you found some elegant way to take care of all these cases, or whether you ignored several of them, or whether you handled all those little nitpicky cases like I find myself doing. I can handle them, but it feels like I’m spending an incredibly amount of time and effort on some very corner cases.

I suppose I should take a look at your code, but I’ve got my head buried in my own right now. It seems very quick from the map demo I looked at. Nice job!
http://www.darrellplank.com Darrell Plank

Okay, I did actually take time to look through your code and it looks like you had to stand on your head a bit to take care of this also. I did happen to think of a cheap workaround kind of. I’ve already got a routine which clips convex polys to convex polys so the only cells I have any problem with are the infinite ones and they only occur only on points of the convex hull. If I put four points at the corners or diagonally out some distance from the corners, they would be the only ones on the convex hull so none of the sites within my rectangle would be infinite. That would solve my problem, but I think it’s worth pursuing the “correct” solution here – esp if I put this in public domain which I plan on doing.

BTW, now that I’ve looked at the code, nice job! It’s been a long time since I’ve programmed in ActionScript – this brought back memories.
alan

Hi Darrell,
Yes, the clipping to the bounding rect was a pain, and I’m not that thrilled with my code there. I had started to rework it using more general polygon clipping as you mention, but then I got into implementing the incremental Voronoi algorithm, which handles changes to points in a localized way & therefore avoids recalculating the entire diagram, and also starts with three seed points outside the clipping bounds & therefore makes the clipping simpler — much like what you describe! But that was several distractions (and IDE evaluations) ago, and it’s not moving forward at the moment…
http://simblob.blogspot.com/ Amit Patel

Alan, is the incremental algorithm simpler than Fortune’s algorithm? I’ve been considering porting my map generation project to C++ so that it can run on a server, and haven’t decided how I want to do this (or even whether I should, given all the other projects I want to work on).
alan

Hi Amit,
I would certainly say the incremental algorithm is simpler. Also I think it’s more productive in terms of where it can lead you (into topology-based improvements that can handle many many points, for example, leaving numerical stability problems behind, or so I hear) than the rather confusing sweepline – beachfront – parabolas Fortune algorithm, which for me was a bit of a dead end. Fortune claimed that generalizing his algorithm to the weighted version was straightforward but I haven’t grasped exactly how! Check out this animation of the incremental algorithm.
Pingback: Quick Sketch – Spanning Tree - Ross Kettle's Blog
Marco Quaggiotto

It’s been a while since you released this, but IÂ wantedÂ to let you know that it’s stillÂ appreciatedÂ and used..
Here’s your third (official) user:Â http://www.datainterfaces.org/2011/11/twitter-orographies/
Thanks!
Anonymous

Thanks for the link! Great to see such creative things being built with Voronoi!
Pingback: Darrell plank | Leadinginfluence
http://twitter.com/purpleor Purple Orange Games

Hi there, I just finished coding it on my game: http://purpleorangegames.com/team/UI/Voronoi.png

Since it’s C++ I used this great port of your code: https://github.com/SirAnthony/cppdelaunay
nodename

Haha, from C to AS3 to C++, cool! Both that and your game look great!
http://twitter.com/purpleor Purple Orange Games

Thanks!
I’m using it with the Qt framework but right now I haven’t edited SirAnthony’s code, I do plan on making it work natively with Qt later and also make it with work inside of QML ;D

nodename

Roll Over, Delaunay: Voronoi Library Goes Open-Source

Categories

Archives

A sample text widget

My Open-Source Projects

Subscribe:

geometry

Maps and DataViz

Programming Practice

Quote