15.2 Iterated Fractals

This self-similar behavior can be replicated through recursion: repeating a process over and over.

Example 1

Suppose that we start with a filled-in triangle. We connect the midpoints of each side and remove the middle triangle. We then repeat this process.

If we repeat this process, the shape that emerges is called the Sierpinski gasket. Notice that it exhibits self-similarity – any piece of the gasket will look identical to the whole. In fact, we can say that the Sierpinski gasket contains three copies of itself, each half as tall and wide as the original. Of course, each of those copies also contains three copies of itself.

import numpy as np
import matplotlib.pyplot as plt

DEPTH = 5          # EDIT: try 0, 1, 2, 3, ... up to 7, and re-run each time

def sierpinski(tri, depth):
    # At each step, replace the triangle with three half-size copies of itself.
    if depth == 0:
        return [tri]
    a, b, c = tri
    ab, bc, ca = (a + b) / 2, (b + c) / 2, (c + a) / 2
    out = []
    for corner in ((a, ab, ca), (ab, b, bc), (ca, bc, c)):
        out += sierpinski(np.array(corner), depth - 1)
    return out

start = np.array([[0.0, 0.0], [1.0, 0.0], [0.5, np.sqrt(3) / 2]])
triangles = sierpinski(start, DEPTH)

fig, ax = plt.subplots(figsize=(6.2, 5.4))
for t in triangles:
    ax.fill(t[:, 0], t[:, 1], color="#1f4e79", linewidth=0)
ax.set_aspect("equal")
ax.axis("off")
ax.set_title(f"Sierpinski gasket, step {DEPTH}", fontsize=13)
plt.show()

print(f"{'step':>5}{'triangles left':>16}{'= 3^step':>10}{'area kept':>12}{'removed so far':>16}")
for k in range(DEPTH + 1):
    area = 0.75 ** k
    print(f"{k:>5}{3 ** k:>16,}{'3^' + str(k):>10}{area:>12.5f}{1 - area:>15.2%}")
print(f"\nat step {DEPTH} the picture is {len(triangles):,} solid triangles, each "
      f"1/{2 ** DEPTH} as wide as the original")
print("each step keeps 3 of 4 sub-triangles, so the area is multiplied by 3/4 every time")
print("push DEPTH up and the area heads to 0, but the picture never becomes empty")

We can construct other fractals using a similar approach. To formalize this a bit, we’re going to introduce the idea of initiators and generators.

This process is easiest to understand through example.

Example 2

Use the initiator and generator shown to create the iterated fractal.

Show solution

This tells us to, at each step, replace each line segment with the spiked shape shown in the generator. Notice that the generator itself is made up of 4 copies of the initiator. In step 1, the single line segment in the initiator is replaced with the generator. For step 2, each of the four line segments of step 1 is replaced with a scaled copy of the generator:

This process is repeated to form Step 3. Again, each line segment is replaced with a scaled copy of the generator.

Notice that since Step 0 only had 1 line segment, Step 1 only required one copy of Step 0.

Since Step 1 had 4 line segments, Step 2 required 4 copies of the generator.

Step 2 then had 16 line segments, so Step 3 required 16 copies of the generator.

Step 4, then, would require $16 \times 4 = 64$ copies of the generator.

The shape resulting from iterating this process is called the Koch curve, named for Helge von Koch who first explored it in 1904.

import numpy as np
import matplotlib.pyplot as plt

DEPTH = 4          # EDIT: 0, 1, 2, 3, 4, 5 ... then re-run
SNOWFLAKE = False  # EDIT: True glues three Koch curves into a snowflake

ROT = np.array([[0.5, -np.sqrt(3) / 2], [np.sqrt(3) / 2, 0.5]])   # 60 degree turn

def koch(points, depth):
    # The generator: every segment becomes four segments with a spike in the middle.
    for _ in range(depth):
        new = [points[0]]
        for p, q in zip(points[:-1], points[1:]):
            d = (q - p) / 3
            new += [p + d, p + d + ROT @ d, p + 2 * d, q]
        points = np.array(new)
    return points

if SNOWFLAKE:
    corners = np.array([[0.0, 0.0], [1.0, 0.0], [0.5, np.sqrt(3) / 2], [0.0, 0.0]])
    pieces = [koch(np.array([corners[i], corners[i + 1]]), DEPTH) for i in range(3)]
    curve = np.vstack(pieces)
else:
    curve = koch(np.array([[0.0, 0.0], [1.0, 0.0]]), DEPTH)

fig, ax = plt.subplots(figsize=(7.2, 4.0))
ax.plot(curve[:, 0], curve[:, 1], lw=1.1, color="#0b6e4f")
ax.set_aspect("equal")
ax.axis("off")
ax.set_title(f"Koch {'snowflake' if SNOWFLAKE else 'curve'}, step {DEPTH}", fontsize=13)
plt.show()

print(f"{'step':>5}{'segments':>12}{'= 4^step':>11}{'each is':>12}{'total length':>15}")
for k in range(DEPTH + 1):
    print(f"{k:>5}{4 ** k:>12,}{'4^' + str(k):>11}{'1/' + str(3 ** k):>12}"
          f"{(4 / 3) ** k:>15.4f}")
print("\nevery step multiplies the length by 4/3, so the curve gets longer without limit")
print(f"but it never leaves the box it started in - at step {DEPTH} it is "
      f"{(4 / 3) ** DEPTH:.3f} units long inside a segment of length 1")

Notice that the Sierpinski gasket can also be described using the initiator-generator approach

Initiator and generator for the Sierpinski gasket, labelled below. The initiator is a solid black triangle. The generator is three half-size solid triangles arranged in the same triangular outline, with the middle upside-down triangle left white.

Using iteration processes like those above can create a variety of beautiful images evocative of nature[2][3].

Two computer generated fractal images side by side: a photorealistic rendering of a broad wind-swept tree whose foliage is built from repeated branching, and a green Barnsley fern in which every frond is a smaller copy of the whole frond.

More natural shapes can be created by adding in randomness to the steps.

The landscape below was created using fractals, then colored and textured.

A computer generated landscape built by randomized fractal subdivision and then coloured and textured: rolling green and brown foothills in the foreground rising to a range of hazy blue peaks under a pale sky.

[1] http://www.flickr.com/photos/visualarts/5436068969/

[2] en.Wikipedia.org/wiki/File:Fr...e_b_-_2%29.jpg

[3] en.Wikipedia.org/wiki/File:Ba...-_4_states.PNG

[4] en.Wikipedia.org/wiki/File:Fr...lLandscape.jpg

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.