The Sierpinski Triangle - Recursive Construction of Fractals

Various fractals created with the algorithm described here.

The Sierpinski Triangle

The Sierpinski triangle already appeared in the Chaos game, where it was generated by a random iteration algorithm. It is often used as a teaching example for the construction of self-similar sets, because it contains exact copies of itself no matter how much you enlarge it. The method of construction described here is based on recursive function calls.

In the first step, one starts with an equilateral triangle. In the next step, this triangle is divided into three triangles, each half the size of the other. The middle part of the original triangle remains empty. In the next step you repeat this process. If you do this infinitely often, you get a Sierpinski triangle.

Construction of a Sierpinski Triangle

The Sierpinski triangle is a kind of intermediate between a surface and a curve. Topologically, one speaks of a nowhere dense, locally connected, metric continuum [1]. Mathematically this is described by the so-called fractal dimension. The fractal dimension of the Sierpinski triangle is:

\begin{equation} D = log_2 3 \approx 1.58486... \end{equation}

Which puts it somewhere between a plane and a line.

Sierpinski triangle calculated with the program shown here.

Source code (Sierpinski triangle)

Programming-wise, this algorithm can be implemented in Python in a few lines of source code. Here a slightly modified version is shown, which only draws the outlines and no filled triangles. This makes no difference, since all algorithms for generating Sierpinski triangles converge to the same result in the end.

The algorithm starts with the vertices of a triangle and subdivides this triangle into three smaller triangles in the subdivide function. Then the subdivide function recursively calls itself for each of the new triangles and repeats the process.

The program terminates after 9 subdivision steps, because at this point there is no point in subdividing further. The triangles have become so small that the computer graphics can no longer resolve them. The result of a program run is shown in the picture on the right.

import pygame
from pygame.locals import *

def subdivide(surface, p1, p2, p3, level):
    if level >= 9:
        return

    pygame.draw.lines(surface, (255, 255, 255), True, (p1, p2, p3))
    pygame.display.update()

    subdivide(surface, p1, ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2), ((p1[0] + p3[0]) / 2, (p1[1] + p3[1]) / 2), level + 1)
    subdivide(surface, p2, ((p2[0] + p3[0]) / 2, (p2[1] + p3[1]) / 2), ((p2[0] + p1[0]) / 2, (p2[1] + p1[1]) / 2), level + 1)
    subdivide(surface, p3, ((p3[0] + p2[0]) / 2, (p3[1] + p2[1]) / 2), ((p3[0] + p1[0]) / 2, (p3[1] + p1[1]) / 2), level + 1)

def main():
    pygame.init()
    surface = pygame.display.set_mode((800, 600))

    subdivide(surface, (400, 100), (100, 500), (700, 500), 0)

    while True:
        for event in pygame.event.get():
            if event.type == QUIT:
                pygame.quit()
                return

if __name__ == "__main__":
    main()

The source code of this program can be found in the file sierpinski.py of the source code archive on GitHub.

Generalization and extension of the construction rules

Based on the source code described above, we extend the construction algorithm. The first change is that we do not want holes in the fractal as in the classical Sierpinski triangle. Therefore, each triangle is divided into four smaller triangles so that its area is completely filled.

Furthermore, we want to bring color into the fractal. We therefore assign the color yellow to each vertex of the starting triangle. The triangle itself is assigned the color red. The color of the vertices does not matter at first when drawing, the triangle is colored red. However, the corner point color can be assigned to the subordinate triangles according to certain rules in later subdivision steps.

When a triangle is subdivided, a new triangle with the corner points M, N, O is created in the center. These points are assigned the color of their parent triangle. This color is randomly lightened slightly.

def subdivide(v, p, q, r, col, level):
    if level >= 10:
        pixel_col = (min(col[0], 255), min(col[1], 255), min(col[2], 255))
        pygame.draw.polygon(surface, pixel_col, ((int(p.pos[0]), int(p.pos[1])),
                                                 (int(q.pos[0]), int(q.pos[1])),
                                                 (int(r.pos[0]), int(r.pos[1]))))
        return

    col = (randint(col[0], col[0] + 6), randint(col[1], col[1] + 6), randint(col[2], col[2] + 6))
    m = Point(((p.pos[0] + q.pos[0]) / 2, (p.pos[1] + q.pos[1]) / 2), col)
    n = Point(((q.pos[0] + r.pos[0]) / 2, (q.pos[1] + r.pos[1]) / 2), col)
    o = Point(((p.pos[0] + r.pos[0]) / 2, (p.pos[1] + r.pos[1]) / 2), col)

    subdivide(v, m, n, o, p.col if v[0] == 0 else col, level + 1)
    subdivide(v, p, o, m, p.col if v[1] == 0 else col, level + 1)
    subdivide(v, m, n, q, p.col if v[2] == 0 else col, level + 1)
    subdivide(v, o, r, n, p.col if v[3] == 0 else col, level + 1)

From the 6 new points P,Q,R,M,N,O thus obtained, the four smaller triangles ▲M,N,O; ▲P,O,M, ▲M,N,Q and ▲O,R,N are formed and further subdivided according to the same rules. The rules for assigning colors to the new triangles are in the field v passed as a parameter to the subdivide function. This field contains four entries which are either 1 or 0.

The triangle ▲M,N,O gets the color of the point P, if v[0]==0 otherwise it gets the same color as its parent triangle.
The triangle ▲P,O,M gets the color of the point P, if v[1]==0 otherwise it gets the same color as its parent triangle.
The triangle ▲M,N,Q gets the color of the point P, if v[2]==0 otherwise it gets the same color as its parent triangle.
The triangle ▲O,R,N gets the color of the point P, if v[3]==0 otherwise it gets the same color as its parent triangle.

Die ersten beiden Schritte, sowie die Eckpunktzuweisung in weiteren Schritten der Funktion subdivide für die Regel v = 1, 1, 0, 0 sind in der folgenden Grafik dargestellt:

The end result, if you continue with this rule, is a modified, colored version of the Sierpinski triangle.

The result of the color distribution rule v=1,1,0,0 is a colored version of the Sierpinski triangle.

The color rule v is a field with four entries that can be either 0 or 1. This can also be interpreted as a 4 bit number. So there are 2^4 = 16 different color rules for this construction mechanism. The complete results for all possible color rules are shown here.

Color rule v=0,0,0,0

Color rule v=1,0,0,0

Color rule v=0,1,0,0

Color rule v=1,1,0,0

Color rule v=0,0,1,0

Color rule v=1,0,1,0

Color rule v=0,1,1,0

Color rule v=1,1,1,0

Color rule v=0,0,0,1

Color rule v=1,0,0,1

Color rule v=0,1,0,1

Color rule v=1,1,0,1

Color rule v=0,0,1,1

Color rule v=1,0,1,1

Color rule v=0,1,1,1

Color rule v=1,1,1,1

This version of the fractal is implemented in the triangle_fractal.py program of the source code archive on GitHub.

Is that all?

The attentive reader might have noticed that the coloring depends not only on the field v, but also on the point order in the arguments of the subdivide function. For a triangle there are 3! = 3*2*1 = 6 different possibilities to arrange its vertices. From each triangle four new triangles are created. So there are 6*6*6 = 1296 different possibilities to subdivide the four triangles, if the point order is important and of course there are 16 different possibilities of color assignment in the algorithm. In total, not only 16, but 1296 * 16 = 20736 different fractals can be calculated with the algorithm. Many of them are admittedly monochromatic but the variety is nevertheless enormous.

In the source code archive on GitHub there is a program version called triangle_fractal_complete.py. This computed all possible fractals for this algorithm. A selection of them can be seen here:

References

Wikipedia Editors, "Sierpinski-Dreieck." auf https://de.wikipedia.org, abgerufen am 2020-05-12

The Sierpinski Triangle - Recursive Construction of Fractals