Constrained minimum spanning trees as shape fills, the moving version of my earlier post The Name of the Node. On each frame one point is added, all the points move, and their spanning trees are drawn. Character: JIE2, “knot”.

(Be sure to view the movie in 480p.)

Note that since the segments are filled with trees, which may branch but never loop, the KOU3 (”mouth”) in the lower right quadrant is never a closed box. In every frame there is an escape path from the inside to the outside.

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?