Fractal Friday (Or Sierpinski Saturday)

The Sierpinski triangle (or gasket as his friends call him) is everywhere. It’s hiding in the rows of Pascal’s triangle, emerging from the Chaos Game, or being drawn by turtles in all sorts of imaginative ways. I hear from a reliable source that my EPP teacher from 6th grade might be introducing his class to this ubiquitous fractal. So, for today’s Fractal Friday, I thought I’d show you just a few of the places that gasket likes to show up:

The Chaos Game

1. Choose 3 vertices of a triangle.

2. Pick a point inside that triangle.

3. Each time we draw a new point, we roll a die to determine which vertex we’re moving toward.

4. Draw a point halfway between your current point, and the vertex you rolled.

5. Repeat 1000s of times.

(Read here for more details, or Chapter 1 of Fractals: A Programmer’s Approach)

Affine Transformations

Similar to the Chaos Game, but this time using transformation equations. The basic form of an affine transformation is:

x' = ax+by+e
y' = cx+dy+f

With x and y being your current position, and x’ and y’ being your new point. The constants a-f determine where your next point will go.

For the Sierpinski Triangle we use three sets of equations:

1) x' = 0.5*x + 0.0*y + 0.0
   y' = 0.0*x + 0.5*y + 0.0
2) x' = 0.5*x + 0.0*y + 0.5
   y' = 0.0*x + 0.5*y + 0.0
3) x' = 0.5*x + 0.0*y + 0.25
   y' = 0.0*x + 0.5*y + 0.5

(For more details check out Chapter 2 of Fractals: A Programmer’s Approach)

Turtle Graphics

Drawn using a series of commands for drawing a line forward or turning to the right or left. The name “turtle graphics” comes from the imaginary turtle representing the current position of the draw cursor. By giving the turtle a series of commands to draw a line forward, or turn, we can create all sorts of images including the one above. The pseudo-code for drawing the Sierpinski Gasket can be found in Abelson and diSessa’s Turtle Geometry (page 88):

TO NESTED.TRIANGLE SIZE
   IF SIZE < 10 THEN RETURN
   REPEAT 3
      NESTED.TRIANGLE SIZE/2
      FORWARD SIZE
      RIGHT 120

(For more details check out Chapter 3 of Fractals: A Programmer’s Approach or Turtle Geometry by Abelson and diSessa)

L-Systems

L-Systems (named for Aristid Lindenmayer who created them) are a different way of describing the commands we give to our metaphorical turtle. We use a sequence of characters to give the turtle commands; typically F for forward, + for turn right, and – for turn left. Sometimes we use another character like G or f to move forward without drawing a line.

We start with a string (sentence) of characters called the Axiom. For a triangle this is often F++F++F (each turn is 60 degrees). We go through this string a character at a time and replace certain characters according to our replacement rules. After doing this a number of times, we go through the string of characters again, but this time just execute the commands they represent to draw the final shape. There are a number of L-Systems for drawing the Sierpinski triangle. Here are a few of my favorites:

Classic Gasket

Forward = “F”, Right = “+”, Left = “-“, Move = “G”
Axiom = “F--F--F”
Replacement rules = {F --> F--F--F--GG, G --> GG}

Sierpinski Arrowhead

Forward = "A and B", Right = "+", Left = "-"
Axiom = “A”
Rules = {A --> B-A-B, B --> A+B+A}

Sierpinski Maze

Forward = “F”, Right = “+”, Left = “-“
Beg recursion = “[“, End recursion = “]”, Move = “f”
Axiom = “F”, Variables {A = 3}
Replacement rules = {F -> [fF][+fA-F][f+f+F], f -> ff}

(For more details look here, or check out Chapter 4 of Fractals: A Programmer’s Approach)

Pascal’s Triangle

Image Source (Math Research, Tips and Tricks – http://malsmath.blogspot.com/2006/12/pascals-triangle-and-prime-numbers.html)

Pascal’s triangle, each row created by adding the numbers of the row above it, contains the Sierpinski triangle (and a number of other interesting patterns), depending on how you shade in the numbers. If you shade all odd numbers, there’s that gasket.

So that’s … seven methods for drawing the Sierpinski triangle. Know any others?