Back To Blog Page

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.

.entry-footer

Leave a Reply

Your email address will not be published. Required fields are marked *