voronoi fractal

I set myself a chal­lenge last week­end: start­ing only from the code for the inter­sec­tion point of two lines, I would try to make a Voronoi frac­tal applet with­out using any fur­ther ref­er­ence. This actu­ally had a rea­son: 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 your­self, con­struct­ing a sketch of a Voronoi graph is simple:

1. Draw some ran­dom dots.
2. Con­nect all dots with straight lines.
3. Bisect all con­nect­ing lines (i.e. draw a per­pen­dic­u­lar straight line through the mid­dle of the con­nect­ing lines).
4. Select pieces of the bisect­ing lines so each point is encap­su­lated in its own cell.

One of my rough sketches:

A decep­tively sim­ple process. Steps 1 to 3 are easy enough to imple­ment, just a mat­ter of basic geom­e­try. The tricky part is point 4, I couldn’t fig­ure out how I did it on paper. I, and undoubtely you too, just draw the cells based on the net­work of bisect­ing lines.

In the end, I found a way of mak­ing the com­puter do the same thing. But it involves a rather exhaus­tive search and is a far cry from the effort­less ele­gance of a human being. Turn­ing a Voronoi graph into some­thing fractal-like was the next step. Get­ting the bor­ders 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 amaz­ing way our brains work later, this is what I came up with. It def­i­nitely has poten­tial for fur­ther devel­op­ment. As always the code is up for grabs (and rather rough). Cur­rently, because it’s a bit of a mem­ory hog, the online ver­sion is lim­ited in depth.

Update : I’ve replaced the applet with a new ver­sion using less memory.

This entry was posted on Tuesday, April 1st, 2008 at 00:56. It is filed under Blog, Inspiration, Portfolio, Processing and tagged with fractal, geometry, Processing, voronoi. You can follow any responses to this entry through the RSS 2.0 feed.