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?

This is about implementing an enum in AS3 with value restriction ( i.e. the programmer should be unable to diminish or add to the set of values) and type safety.

We’ll implement the data type as a Class. In order to keep the programmer from adding to the set of values, we need to disallow invocation of the constructor.

Back when AS3 came out, there was much talk about the lack of private constructors and what to do about it, especially with regard to implementing the Singleton pattern. My favorite of the solutions is to define a file-level class and require it (the class, not an instance!) as a constructor parameter.

From there we can proceed just as Daniel Savarese describes in Implementing Enumerated Types in Java.

I don’t show how to implement an ordering on the enum values. See the Savarese article for that, too.

package
{
	import flash.errors.IllegalOperationError;

	public final class PailContents
	{
		public static const WATER:PailContents = new PailContents(PrivateConstructorEnforcer, "water");
		public static const CHICKENFEED:PailContents = new PailContents(PrivateConstructorEnforcer, "chicken feed");
		public static const MILK:PailContents = new PailContents(PrivateConstructorEnforcer, "milk");
		public static const OATS:PailContents = new PailContents(PrivateConstructorEnforcer, "oats");

		private var _name:String;

		public function PailContents(lock:Class, name:String)
		{
			super();
			if (lock != PrivateConstructorEnforcer)
			{
				throw new IllegalOperationError("Invalid constructor access");
			}
			_name = name;
		}

		// don't forget to implement toString() to support implicit conversion to String for trace() etc:
		public function toString():String
		{
			return _name;
		}

	}
}

// defined outside the package, and therefore visible only within this source file:
class PrivateConstructorEnforcer {}

No, this isn’t about some hot new way of using Voronoi diagrams to google myself; I’ll leave that challenge to Mario.

I was looking over the search terms that had led people to my blog today, and decided to click on “Alan Shaw” Voronoi. Among all the recent stuff, I came across some papers and articles from my pre-Flash (and pre-C++) days:

Automatic construction of polyhedral surfaces from voxel representations (1988)
Generalized map makers problem: optimal flattening of polyhedral surfaces

Applications of Computer Graphics and Image Processing to 2D and 3D Modeling of the Functional Architecture of Visual Cortex
A Numerical Solution to the Generalized Mapmaker’s Problem: Flattening Nonconvex Polyhedral Surfaces

Now to reread them after twenty years and see if they were all bullshit.

We achieved reasonable performance on a Sun-2 microprocessor system (which is roughly comparable to a VAX-750).

Uh huh.

Here’a a video by mike40033:

Just about every weekend I go to my favorite local restaurant, China Fun, for one of the traditional meals I got accustomed to long ago in Taiwan: 鹹豆漿 xián dòujiāng — “salty” soybean milk, meaning hot soybean milk with sliced-up 油條 yóutiáo (”oil-stick,” i.e. fried cruller), dried baby shrimp, pickled veg, cilantro, etc, as opposed to 甜豆漿 tián dòujiāng “sweet” soybean milk with just sugar in it — and 韮菜鍋貼 jiŭcài guōtiē — chive (and pork) fried dumplings, or “pot-stickers” by literal translation of 鍋貼. Up here on the Upper West Side the soybean milk is only available on the weekend, although in Chinatown of course it’s a daily staple. They know me pretty well at China Fun; I never spoke English to them for the first few years, in order to encourage them to help me keep up my Chinese. And when I show up on a Saturday or Sunday afternoon they pretty much know what I want. But of course one has to make sure.

There are two expressions I hear for “the usual”:

照舊 zhàojiù “according-old”
老樣子 lăo yàngzi “old appearance/way”

舊 and 老 both mean “old”; usually 舊 is applied to things, and 老 refers to age, as of people or animals. I believe that 老 is natural in the expression 老樣子 because 樣子 originally refers to a person’s appearance. In fact 樣 shows up in Japanese as the formal suffix -sama, used in place of the more neutral form of address -san.

I have a feeling that 照舊 may be a bit more correct/formal than 老樣子 for “the usual.” Certainly it’s higher on the literary vs. colloquial scale.

In Flash we can HARNESS THE POWER OF BITMAPDATA (as it might be put in a conference session blurb) to grow Voronoi regions under differing conditions, without doing any algebra. Click on the image to launch the Voronoi Generator.

Variations on Voronoi Diagrams, from Geometry in Action:

One way of getting Voronoi diagrams is by growing crystals. If you start a number of crystals, all growing at the same rate, and all starting at the same time, you get a number of growing circles. As these circles meet, straight line boundaries appear between them. Eventually, the entire plane will be filled up. Each crystal will exactly fill up the Voronoi region of its point of origin.

This is a little too simple. In reality, crystals start growing at different times. Even if they still grow at the same rate, if they start at different times, they will no longer meet in straight lines. Instead, they will meet in hyperbolic segments. The diagram you get is called the “additively weighted Voronoi diagram”. It’s defined just like the usual Voronoi diagram, but each site has a weight, and you measure distance to a site, you add its weight to the usual Euclidean distance.

Now suppose instead that all the crystals start at the same time, but grow at different rates. Now you get what’s called the “multiplicatively weighted Voronoi diagram”. Once again, each site is given a weight, but when you measure the distance to a site, you multiply by its weight. Now the boundaries between different regions are segments of circles.

This model still has some problems. For example, in a multiplicatively weighted Voronoi diagram, it’s possible for a region to be disconnected [ see picture above -- AS ]. Obviously, this can’t happen with real crystals. So there’s yat another version which treats existing crystals as obstacles, and lets fast-growing crystals grow around the slower ones. Now the boundaries between neighboring regions are sort of tear-shaped. This variation is called the “multiplicatively weighted crystal growth Voronoi diagram.”

There are several other variations. You can change the metric from the normal Euclidean distance to L₁, or L_p, or L_infinity, or even stranger distance functions. You can weight the sites additively and mulitplicatively. You can change the sites from points to line segments or circles or polygons. You can generalize to higher dimensions. You can associate points with the farthest site, instead of their nearest site. And so on.

Different applications of Voronoi diagrams require different variations. For example, motion planning algorithms for circular robots often use the Voronoi diagram of the obstacles. If there is a path from one location to another, then there must be a path that follows the edges of the Voronoi diagram, since those edges are by definition as far from the obstacles as possible.

The “L₁ metric” is called the Manhattan metric or city-block distance. “Manhattan metric” is a misnomer, though, because in Manhattan the east-west blocks are much longer than the north-south blocks.

The crystal-growth model is equivalent to the “evil forest ranger model,” in which instead of watching for forest fires, the rangers set fire to their lookouts, sometimes at different times, and the fires may spread at different rates. Voronoi diagrams indeed find application in crystallography and in forest-fire modelling.

And here is a post about a far-from-evil lookout.

A little code for a change.

Sakri was working on this, and I ported a class from Java which I believe he adapted into his final implementation. It’s a basic tool for morphing, 3D surface reconstruction, and vectorization.

I’ve cleaned up my version of it and I offer it here. The important function signature looks like this:

public static function perimeter(data:BitmapData, x:int, y:int):Vector.<Point>

It returns a list of pixels representing the boundary between opaque and transparent pixels, starting from a single boundary point that you provide.

You can get a boundary point using Sakri’s and Mario’s EdgeFinder class.

Download the source.

How it works: Marching Squares on Wikipedia

Click on the image to see 1000 Voronoi points in motion. Keyboard controls as in the Voronoi Toy.

If the popup won’t go away when you click the X, click in the movie and hit “s” to stop the moving points.

I couldn’t resist, Frank!

Jim Armstrong, the Flash community’s primary math whiz, has encouraged me in the past, and today he did so publicly. I’m very grateful for this recommendation.

Here’s the crass part: I’m available for contract or permanent work, locally or remotely. I live in New York City. CV, references, and samples of my work are available. Please hit the Contact link to get in touch.

See you in Minneapolis?

And we’ll now return to tech talk…

I’ve rendered some images using the Voronoi Toy from my last post.

I’ve used my logo 結 (as in 結點 “node”) as the input image, run Sakri Rosenstrom’s image segmentation algorithm on it, dropped 10,000 random points into the segments, and drawn the minimum spanning tree of each set of points, thus creating a sort of space-filling tree.

The idea for this kind of fill comes from Mario Klingemann’s presentation at FITC.

Click on each image for a larger version.