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:

- Draw some random dots.
- Connect all dots with straight lines.
- Bisect all connecting lines (i.e. draw a perpendicular straight line through the middle of the connecting lines).
- 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.