Back To Blog

Sierpinski’s Triangle PT 3

Alternate methods of generating Sierpinski’s Triangle: one using a recursive function, the other using the chaos game.

First: what is recursion? What is the chaos game?

Recursion is a fundamental concept in computer science and mathematics, where a function or algorithm calls itself again and again in order to solve a problem. The principle of recursion is to break down a complex problem into smaller, more manageable sub-problems, then continues until it reaches a condition that can be solved without further recursion, usually referred to as the ‘base case’. One very common example of recursion is the factorial (the product of all positive numbers up to a number). Here it is in Python:

def factorial(n):
    # Base case: factorial of 1 is 1
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

In this example, factorial(n-1) is the recursive call. When you call factorial(n), it calls factorial(n-1), which calls factorial(n-2), and so on, until it reaches factorial(1). This base case returns a simple, non-recursive result, which is 1 in this case.

The Chaos Game is a mathematical procedure that generates a sequence of points in a space, often resulting in a fractal pattern. Invented by mathematician Michael Barnsley, it’s part of the study of chaotic dynamical systems.

Here is the basic process of the Chaos Game:

  1. Begin by defining a set of rules or transformations. Typically, these involve geometric operations like rotations, translations, and scaling.
  2. Choose an initial point in the space.
  3. Apply one of the transformations to the point at random. The result is a new point.
  4. Repeat step 3 for the new point, and continue doing so. The key is that the choice of transformation is random at each step, introducing an element of unpredictability or “chaos”.

The Chaos Game is fascinating because it demonstrates how complex and intricate structures can emerge from simple rules and random behavior. This makes it a useful tool in the study of chaos theory and fractals.

Let’s try a relatively simple example by creating the Barnsley Fern.

The Barnsley Fern is a fractal named after British mathematician Michael Barnsley who first described it in his book “Fractals Everywhere”. The fern is created by plotting a sequence of points in the plane according to a set of four affine transformations chosen at random.

Here is a simple Python code using matplotlib and numpy:

import numpy as np
import matplotlib.pyplot as plt
# Define the transformation functions
def f1(x, y):
    return 0, 0.16*y
def f2(x, y):
    return 0.85*x + 0.04*y, -0.04*x + 0.85*y + 1.6
def f3(x, y):
    return 0.2*x - 0.26*y, 0.23*x + 0.22*y + 1.6
def f4(x, y):
    return -0.15*x + 0.28*y, 0.26*x + 0.24*y + 0.44
# Create an array of transformation functions
fs = [f1, f2, f3, f4]
# Choose an initial point
x, y = 0, 0
# Initialize arrays to hold x and y values
xs = [x]
ys = [y]
# Iterate the transformations
for i in range(100000):
    # Choose a random transformation function and call it
    f = np.random.choice(fs, p=[0.01, 0.85, 0.07, 0.07])
    x, y = f(x, y)
    xs.append(x)
    ys.append(y)
# Plot the points
plt.scatter(xs, ys, s=0.2, color='green', lw=0)
plt.show()

In this code, we define four transformation functions f1, f2, f3, and f4, which correspond to the four transformations used to generate the Barnsley Fern. We then apply one of these functions at each step, chosen at random according to specified probabilities. Despite the randomness, the sequence of points forms the recognizable shape of a fern.

  1. Recursive Function:

This function involves dividing a triangle into four smaller triangles and removing the center one, and then repeating this process for the remaining triangles. Here’s a simple way to do this using the turtle module in Python:

import turtle
def draw_sierpinski(length, depth):
    if depth==0:
        for i in range(3):
            turtle.forward(length)
            turtle.left(120)
    else:
        draw_sierpinski(length / 2, depth - 1)
        turtle.forward(length / 2)
        draw_sierpinski(length / 2, depth - 1)
        turtle.backward(length / 2)
        turtle.left(60)
        turtle.forward(length / 2)
        turtle.right(60)
        draw_sierpinski(length / 2, depth - 1)
        turtle.left(60)
        turtle.backward(length / 2)
        turtle.right(60)
# Initial settings
turtle.speed(0)
turtle.penup()
turtle.goto(-200, -200)
turtle.pendown()
# Draw Sierpinski Triangle
draw_sierpinski(400, 4)
# End drawing
turtle.done()

In this code, draw_sierpinski is a recursive function where length is the side length of the triangle and depth is the recursion depth. The turtle starts by moving forward, then recurses, moves forward again, recurses, moves backwards, and finally turns to start the next recursion.

  1. Chaos Game:

The chaos game is a method of creating a Sierpinski triangle by randomly moving a point half the distance towards the corners of an initial triangle. Here’s a way to do this using matplotlib and numpy:

import numpy as np
import matplotlib.pyplot as plt
# Initialize the triangle corners
corners = np.array([[0, 0], [0.5, np.sqrt(3)/2], [1, 0]])
points = np.zeros((100000, 2))
points[0, :] = [0, 0]
for i in range(1, len(points)):
    # Randomly select a corner
    corner = corners[np.random.randint(3)]
    # Move half the distance to the chosen corner
    points[i] = (points[i-1] + corner) / 2
# Plot the result
plt.scatter(points[:, 0], points[:, 1], s=0.1, color='k')
plt.axis('equal')
plt.show()

In this code, corners contains the coordinates of the three corners of the initial triangle, and points is an array of points that will be plotted. In each step of the loop, a corner is randomly selected, and the next point is set to be halfway between the previous point and the selected corner. The result is a scatter plot of all the points, which forms a Sierpinski triangle.

Back To Blog

SierPinski’s Triangle PT 2

In Part I, I explained what the Sierpinski’s Triangle is, and how it is based on fractals. In this post, we will actually build the Sierpinski’s Triangle, reviewing the basic mathematical concepts behind the Triangle, then using Python to build it. This tutorial is based on Giles McCullen-Klein’s ‘Sierpinski’s Triangle’ section of his excellent ‘Python Programming Bootcamp‘ course on the 365 Data Science platform (also on Udemy):

To review, the Sierpinskis Triangle is a fractal, a self-replicating geometric pattern that exhibits intricate detail and self-similarity at different scales. It is named after the Polish mathematician Wacław Sierpiński, who first described the pattern in 1915.

The Sierpinski Triangle is formed by recursively subdividing an equilateral triangle into smaller equilateral triangles. The process begins with a single large equilateral triangle. Then, at each iteration, we:

  1. Divide the initial triangle into four smaller equilateral triangles by connecting the midpoints of each side.
  2. Remove the central triangle, leaving three smaller equilateral triangles that form a larger equilateral triangle.
  3. Repeat steps 1 and 2 for each of the remaining smaller triangles, continuing indefinitely.

As the number of iterations approaches infinity, the resulting pattern becomes an increasingly intricate set of triangles, with the final Sierpinski Triangle having an infinite number of triangles and a total area of zero.

The Sierpinski Triangle is an example of a deterministic fractal, meaning that it can be generated through a specific set of rules. It has been studied extensively in mathematics and has applications in areas such as computer graphics, geometry, and the study of complex systems.

To recap, here are our three basic mathematical formulas:

First Transformation:

x_{n+1} = 0.5x_n 
y_{n+1} = 0.5y_n

Second Transformation:

x_{n+1} = 0.5x_n + 0.5
y_{n+1} = 0.5y_n + 0.5

Third Transformation:

x_{n+1} = 0.5x_n + 1
y_{n+1} = 0.5y_n

Next, we take these formulas and express them in Python:

from random import choice
def trans_1(p):
    x = p[0]
    y = p[1]
    x1 = 0.5 * x
    y1 = 0.5 * y
    return x1,y1
def trans_2(p):
    x = p[0]
    y = p[1]
    x1 = 0.5 * x + 0.5
    y1 = 0.5 * y + 0.5
    return x1,y1
def trans_3(p):
    x = p[0]
    y = p[1]
    x1 = 0.5 * x + 1
    y1 = 0.5 * y
    return x1,y1

transformations = [trans_1,trans_2,trans_3]
a1 = [0]
b1 = [0]
a,b = 0,0
 
for i in range(100):
    trans = choice(transformations)
    a,b = trans((a,b))
    a1.append(a)
    b1.append(b)

Then we use Matplotlib to visualize our triangle (we’ll have to import matplotlib first):

import matplotlib.pyplot as plt 
%matplotlib inline
plt.rc('figure',figsize=(16,16))
plt.plot(a1,b1,'o')
plt.savefig('my_figure.png')

as we can see, at 100 points our triangle barely exists. Let’s try again at 1000:

for i in range(1000):
    trans = choice(transformations)
    a,b = trans((a,b))
    a1.append(a)
    b1.append(b)

Ok, our triangle is starting to take shape. Let’s skip ahead and try again at one million:

Ta-dah! There we have it, our Sierpinski’s Triangle. The first time I saw the triangle appear in Giles’ lesson, I thought it was a miracle.

Part 3: Alternative Ways to Generate the Sierpinski’s Triangle