$ cat /home/buntine/mind_melting_brilliance

Following on from my last article, I'd like to show you a common fractal pattern known as the Sierpinski Triangle. It was first described formally in 1915 by Waclaw Sierpinski. You've probably seen it before -- it's basically a triangle, which contains three smaller triangles within it. This process can be repeated ad infinitum.

There are many ways to construct the Sierpinski Triangle, but one method that really grabbed my attention involved an approximation from the rows of Pascal's Triangle. It's really quite simple, but I'll briefly explain Pascal's Triangle first.

Pascal's Triangle is an ancient (discovered long before Pascals time) pattern of numbers in which each number within the triangle is the sum of the two numbers directly above it. The first row is simply 1, and the sides of the triangle are made up of 1's. So it grows like this: [1], [1, 1], [1, 2, 1], [1, 3, 3, 1], etc. Take a look at the Wikipedia article for a proper introduction.

As it turns out, if we generate Pascal's Triangle to 64 rows (or, more formally, any 2^n) and then colour all of the odd numbers in, we get a bloody good representation of the Sierpinski Triangle! I'd think that if we continued this process infinitely (or to some very large n), you'd be unable to tell the difference between the two.

Writing a program to demonstrate this cool little trick was pretty simple. It's just a matter of generating the triangle as a list of expanding lists (one for each row) and then painting each row of numbers to the window by traversing it and selecting the correct colour based on the each value (dark blue for odd, light blue for even). It looks like this:

You can take a look at the source code here: http://github.com/buntine/Fractals/blob/master/pascals-triangle.scm

A few weeks ago I stumbled upon this rather eccentric documentary, narrated by Arthur C. Clarke, about the discovery of the Mandlebrot set and fractal geometry in general: Fractals - The colors of infinity.

A fractal, described very simply, is a geometric pattern that is repeatable at every level of magnification. Fractals, therefore, cannot be described by our traditional models of geometry. Typically, if you inspect a fractal at differing levels of magnification, you will see identical (or very similar) copies of the whole pattern. Of course, such phenomena has always existed, but it hasn't been until the advent of sufficiently powerful computers that we have been able to generate fractals on a large scale of complexity.

In nature, one of the most simple examples of a fractal-like shape is a tree. Using a recursive algorithm and a simple graphics library, we are able to easily generate a fractal tree. I chose the Lisp language PLT Scheme (or Racket, as it's known these days) to write my programs. Here is my first attempt:

Not bad. Well, perhaps a little too uniform. It works by implementing a recursive pattern known (not surprisingly) as tree recursion. That is, each invokation of the function triggers two further recursive calls. Each call to the function plots a new X/Y position by translating a radian (angle * (PI / 180)) and a length into "cartesian coordinates". It then calls itself again with the new X/Y as a starting position and a new angle, once for (angle - 20) and again for (angle + 20) to simulate the splitting of a branch. This process is repeated a finite number of times and the length of each branch is relative to the current depth of recursion.

By simply adding some randomisation into the angles of each branch (instead of always bending 20 degrees), we start to see a slightly more realistic looking tree! See my second attempt below, which draws four trees with some randomised angles to simulate a burnt-out looking forest:

The source code for both of these programs is available on my Github account here http://github.com/buntine/Fractals/blob/master/uniform-tree.scm; and here: http://github.com/buntine/Fractals/blob/master/random-tree.scm.