I set myself a challenge last weekend: starting only from the code for the intersection point of two lines, I would try to make a Voronoi fractal applet without using any further reference. This actually had a reason: I can draw a Voronoi graph on paper but I do not know how to draw it. Bear with me on this, it’ll make sense…

Try it yourself, constructing a sketch of a Voronoi graph is simple:

1. Draw some random dots.
2. Connect all dots with straight lines.
3. Bisect all connecting lines (i.e. draw a perpendicular straight line through the middle of the connecting lines).
4. Select pieces of the bisecting lines so each point is encapsulated in its own cell.

One of my rough sketches:

A deceptively simple process. Steps 1 to 3 are easy enough to implement, just a matter of basic geometry. The tricky part is point 4, I couldn’t figure out how I did it on paper. I, and undoubtely you too, just draw the cells based on the network of bisecting lines.

In the end, I found a way of making the computer do the same thing. But it involves a rather exhaustive search and is a far cry from the effortless elegance of a human being. Turning a Voronoi graph into something fractal-like was the next step. Getting the borders of each cell sorted out was a bit of headache but now works as long as floating-point errors don’t mess things up.

Two nights and an insight in yet another amazing way our brains work later, this is what I came up with. It definitely has potential for further development. As always the code is up for grabs (and rather rough). Currently, because it’s a bit of a memory hog, the online version is limited in depth . Update : I’ve replaced the applet with a new version using less memory.

Tags: fractal, geometry, Processing, voronoi

This entry was posted on Tuesday, April 1st, 2008 at 00:56 and is filed under Processing. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.