Sierpiński Triangle: Fractal Christmas Tree

The Sierpiński triangle named after the Polish mathematician Wacław Sierpiński), is a fractal with a shape of an equilateral triangle. The triangle is subdivided indefinitely into smaller equilateral triangles resembling exactly the original triangle. As such, the Sierpiński triangle really resembles a Christmas tree. An infinite Christmas tree! With this fractal, you will never run out of Christmas trees 😁

The Sierpiński Triangle as a Christmass Tree

In this short post, we will see how to create such a fractal in Python. Then, we will create an animated visualization using the Matplotlib Animation API.

How to create the triangle?

There are multiple ways to generate the triangle as summarized in the Wikipedia article for the Sierpiński triangle. One of the most popular methods is the one based on Chaos Game. Here is how it works in short.

First, we need to take any three points in the plane that form an equilateral triangle. Without loss of generality, we can select the points \( A = (0.0, 0.0), B = (0.5, 1.0), C = (1.0, 0.0) \). We don't need to draw these points. Then we randomly select any point inside the triangle, considering it as the current position \( P \). Then, we repeat the following 3 steps over and over:

1. Randomly select any of the three vertex points \( A, B, C \). Let's denote it as \( R \)
2. Move half the distance from the current position \( P \) to the selected vertex \( R \)
3. Plot the current position

Here is an implementation in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import random
from operator import add

def generate_sierpinski_triangle(n: int):
    sierpinski_triangle = []  # final list of points

    # initial points
    A = (0.0, 0.0)
    B = (0.5, 1.0)
    C = (1.0, 0.0)
    triangle_vertices = [A, B, C]

    # starting point
    moving_point = random.choice(triangle_vertices)

    for i in range(n):
        offset_point = random.choice(triangle_vertices)
        moving_point = list(map(lambda x: x / 2.0, list(map(add, moving_point, offset_point))))
        sierpinski_triangle.append(moving_point.copy())
    
    return sierpinski_triangle

Next, we'll see how to make an animation.

Making an animation: triangle within a triangle

To demonstrate the fractal nature of the triangle we will make an animation by zooming in on one part of the original triangle. For this purpose, we use the Matplotlib Animation API.

It is quite straightforward to make such an animation. In each iteration, we draw all the points, but we only reduce the x- and y-axis limits as a function of the iteration number. This creates a zooming effect. The Python implementation is given below:

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import matplotlib.pyplot as plt
import matplotlib.animation as animation

def make_animation(sierpinski_triangle: list):
    num_points = len(sierpinski_triangle)
    points_split = list(zip(*sierpinski_triangle))
    xx, yy = points_split[0], points_split[1]
    fig = plt.figure(figsize=(10, 10))

    def init():
        ax = plt.axes(xlim=(0, 1), ylim=(0, 1))
        ax.set_xticks([], [])
        ax.set_yticks([], [])
        ax.set_axis_off()
        return ax.plot(xx, yy, "g.")

    def animate(i):
        scale = 1 - i * 0.02  # calculate the new scale
        ax = plt.axes(xlim=(0, scale), ylim=(0, scale))
        ax.set_xticks([], [])
        ax.set_yticks([], [])
        ax.set_axis_off()
        return ax.plot(xx, yy, "g.")

    anim = animation.FuncAnimation(fig, animate, init_func=init, frames=50,
                                interval=200, blit=False)

The resulting animation is shown below. As we can see the same structure appears again and again. Because this is a simulation, the number of points is finite, so the pattern will stop appearing at some point. If we were able to generate an infinite number of points, the pattern would never disappear.

Animation: Sierpiński Triangle Fractal

The source code for this animation of the Sierpiński triangle Jupyter Notebook. For more information, please follow me on LinkedIn or Twitter. Additionally, you can subscribe to the mailing list below.

Appendix: Sierpinski triangle from cellular automata

In one of the previous blog posts, we covered cellular automata. It is also possible to see the pattern from the Sierpinski triangle, by running the Rule 90 as depicted below:

Animation of Rule 90

References

[1] João Ventura, https://joaoventura.net/blog/2016/sierpinski-triangle/