- Draw an equilateral triangle and label the point red, blue, and green
- Start at any vertex
- Roll a die to get the next color (red, blue, or green)
- Draw a point halfway between the starting point and the vertex determined by the die roll
- This new "halfway point" becomes the starting point for the next iteration
- Keep repeating the procedure until a pattern emerges

It takes quite a few iterations for a pattern to emerge, so this is a perfect problem for setting up a simulation. You'll need Python and the Python Imaging Library (PIL) to run the following code.

from PIL import ImageThe code above creates a blank Image canvas and puts random pixels on it, but those pixels form a definite pattern. The pixels are selected by picking a random corner of the triangle and calculating the midpoint between that corner and the previous point drawn.

import random

# calculate the midpoint between two points

def midpoint(p1, p2):

return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)

# define the size of the image and a few color constants

# the hieght of an equilateral triangle is sqrt(3)/2 * base

size = 410, 356 # width, height

white = (255, 255, 255)

black = (0, 0, 0)

# set the corner positions of the triangle

blueCorner = (5, 351)

redCorner = (205, 5)

greenCorner = (405, 351)

corners = (redCorner, blueCorner, greenCorner)

triangle = Image.new("RGBA", size, white)

pivot = blueCorner

for i in range(50000):

randCorner = corners[ random.randint(0, 2) ]

pivot = midpoint(pivot, randCorner)

triangle.putpixel(pivot, black)

triangle.save("triangle.gif")

This is called the Sierpinski triangle, a fractal first described by Polish mathematician Wacław Sierpiński.

This isn't the only fractal that can be created by the Chaos Game. A more general set of rules for the Chaos Game are to start at one vertex of a regular polygon, then draw the next point a fraction r of the distance between it and a vertex picked at random. Most combinations of polygons and fractions won't produce a fractal of course, but there are several that do. From Wolfram MathWorld's article on the Chaos Game we find that for a regular pentagon the fractions 1/3 and 3/8 both produce fractals, as does a regular hexagon with the fraction 1/3.

We'd only need to make a few minor changes to the code above, including the midpoint function, the set of vertices, and the range of the random number generator, in order to generate these fractals. Here are the results.

## 6 comments:

It's amazing the complex patterns that emerge from simple rules.

The Sierpinski triangle is particularly interest because it can be generated in so many different ways.

The sierpinski gasket makes Jonathan Coulton wanna cry.

This can be extended into three dimensions as well. I remember using qbasic to generate a gigantic pov ray file way back when doing this same thing. Pick 4 points in three dimensional space and use r=1/2 works just as well. This makes me wonder what the relationship is between r, p, and dimensionality that will produce fractals?

Your code syntax highlighter isn't preserving indentations, which is crucial for Python programs. granted, it's easy enough to figure out in this case, but I just thought I'd mention it.

Matt,

Thanks for the heads up on the code formatting. Blogger's editor "fixes" indentation for you when you switch from HTML view to the normal editor, so blogging about programming can be a particular pain sometimes. :)

God, the Creator, is orderly. This attribute can be found in many and unexpected ways and places. Amazing.

Post a Comment