Koch-Kurve in Python – Schneeflocke mit Turtle-Grafik

Was du hier lernst

Rekursion
Turtle-Grafik
Fraktale
Selbstähnlichkeit
Wachstum mit Potenzen

Die Schneeflocke aus der Rekursion

Im Kapitel »SOS – Save our Screens« geht es um Bildschirmschoner, Chaos und Fraktale wie die Julia-Menge. Die Koch-Kurve ist eines der ältesten Fraktale überhaupt: Der schwedische Mathematiker Helge von Koch beschrieb sie 1904. Anders als die Julia-Menge braucht sie keine komplexen Zahlen – nur eine Strecke, eine einfache Regel und eine Funktion, die sich selbst aufruft.

Die Regel

Nimm eine Strecke und teile sie in drei gleich lange Drittel. Das mittlere Drittel ersetzt du durch die zwei Seiten eines gleichseitigen Dreiecks, das nach außen zeigt. Aus einer Strecke werden so vier Strecken, jede ein Drittel so lang wie die ursprüngliche. Mit jeder dieser vier Strecken machst du genau dasselbe, und dann wieder und wieder.

Nach einer Runde hat die Strecke einen Zacken. Nach zwei Runden hat jeder Teil einen eigenen kleinen Zacken, nach drei Runden sind es 64 Teilstücke. Die Form wiederholt sich im Kleinen immer wieder – das nennt man Selbstähnlichkeit, und sie ist das Markenzeichen aller Fraktale.

Eine Funktion, die sich selbst aufruft

Eine solche Regel lässt sich direkt als rekursive Funktion schreiben, also als Funktion, die sich selbst aufruft:

def koch(t, length, depth):
    if depth == 0:
        # Tiefe 0: einfach eine gerade Strecke
        t.forward(length)
    else:
        # sonst vier Koch-Kurven mit einem Drittel der Länge,
        # dazwischen Knicke um 60, -120 und 60 Grad
        for angle in (60, -120, 60, 0):
            koch(t, length / 3, depth - 1)
            t.left(angle)

Jede Rekursion braucht eine Abbruchbedingung. Hier ist das depth == 0: Dann zeichnet die Schildkröte einfach eine gerade Strecke. In allen anderen Fällen zeichnet die Funktion vier kleinere Koch-Kurven mit einem Drittel der Länge und einer Tiefe weniger. Weil depth bei jedem Aufruf um eins sinkt, landet jede Kette von Aufrufen irgendwann bei 0.

Zwischen den vier Teilen dreht sich die Schildkröte. left(60) knickt nach links ab und beginnt den Zacken, left(-120) – also 120 Grad nach rechts – dreht an der Spitze um, und left(60) bringt sie zurück in die ursprüngliche Richtung. Die letzte 0 sorgt nur dafür, dass die Schleife nach dem vierten Teil nicht mehr dreht.

Turtle-Grafik

Die Turtle-Grafik stammt aus der Programmiersprache Logo, mit der schon in den 1960er-Jahren Kinder programmieren lernten. Eine Schildkröte läuft über den Bildschirm und zieht dabei eine Spur. Sie versteht Befehle wie forward(100) (100 Pixel vorwärts), left(90) (90 Grad nach links drehen) oder penup() (Stift anheben). Python bringt das Modul turtle von Haus aus mit, und diese Website hat eine eigene Fassung für den Browser.

Drei Kurven ergeben die Schneeflocke

Setzt man drei Koch-Kurven an die Seiten eines gleichseitigen Dreiecks, entsteht die berühmte Koch-Schneeflocke:

def snowflake(t, length, depth):
    # drei Koch-Kurven, jeweils um 120 Grad gedreht, ergeben die Schneeflocke
    for side in range(3):
        koch(t, length, depth)
        t.right(120)

Die Schildkröte läuft das Dreieck im Uhrzeigersinn ab. Weil die Zacken immer links von ihrer Laufrichtung entstehen, zeigen sie dabei nach außen. begin_fill() und end_fill() füllen die Fläche anschließend mit Hellblau. Vorher bringt goto() die Schildkröte mit angehobenem Stift an die linke obere Ecke, damit die fertige Flocke in der Mitte der Leinwand sitzt.

Unendlich langer Rand, endliche Fläche

Jetzt wird es verblüffend. Mit jeder Runde wird aus einer Strecke der Länge 1 ein Linienzug aus vier Stücken der Länge ⅓ – zusammen also 4/3. Der Umfang der Schneeflocke wächst bei jeder Runde um ein Drittel. Das zeigt auch die Tabelle in der Konsole:

Tiefe	Strecken	Umfang in Pixeln
0	3	1.260
1	12	1.680
2	48	2.240
3	192	2.987
4	768	3.982

Führt man die Regel unendlich oft aus, wird der Umfang unendlich lang. Die Fläche dagegen bleibt endlich: Die Flocke passt ja auf den Bildschirm. Genau genommen ist sie 8/5 so groß wie das Ausgangsdreieck. Ein unendlich langer Rand um eine endliche Fläche – solche Eigenschaften machten Fraktale am Anfang des 20. Jahrhunderts zu mathematischen »Monstern«.

Zwischen Linie und Fläche

Eine Linie hat die Dimension 1, eine Fläche die Dimension 2. Die Koch-Kurve liegt dazwischen: Verkleinert man sie auf ein Drittel, braucht man vier Kopien, um das Original zu erhalten. Ihre fraktale Dimension ist deshalb log 4 / log 3 ≈ 1,26 – etwas mehr als eine Linie, aber weit weg von einer Fläche.

Wie viel Arbeit ist das?

Jede Runde vervierfacht die Zahl der Strecken: Die Schneeflocke der Tiefe n besteht aus 3 · 4ⁿ Strecken. Bei Tiefe 4 sind das 768, bei Tiefe 6 schon 12.288. Gleichzeitig schrumpft jede Strecke auf ein Drittel. Bei einem Dreieck mit 420 Pixeln Seitenlänge ist eine Strecke der Tiefe 6 nur noch 0,58 Pixel lang – feiner kann der Bildschirm gar nicht zeichnen. Mehr Tiefe kostet dann nur noch Rechenzeit, ohne dass man etwas sieht.

Auch die Rekursion selbst ist interessant: koch() ruft sich auf Tiefe 4 insgesamt 341-mal pro Seite auf, aber nie mehr als fünf Aufrufe liegen gleichzeitig übereinander. Die Tiefe der Rekursion bleibt also klein, obwohl die Zahl der Aufrufe schnell wächst.

Wie lang ist die Küste?

Die Koch-Kurve ist mehr als eine mathematische Spielerei. 1967 stellte Benoît Mandelbrot – nach ihm ist die Mandelbrot-Menge benannt – eine berühmt gewordene Frage: Wie lang ist die Küste Großbritanniens? Die Antwort hängt davon ab, wie genau man misst. Mit einem 100-Kilometer-Maßstab kommt eine kürzere Länge heraus als mit einem 1-Kilometer-Maßstab, weil der kleinere jede Bucht und jede Landzunge mitnimmt. Je feiner man misst, desto länger wird die Küste – genau wie der Rand der Schneeflocke mit jeder Tiefe wächst. Küsten, Wolken, Blitze und Farnblätter haben diese Art von Selbstähnlichkeit, und Fraktale sind deshalb bis heute ein wichtiges Werkzeug, um natürliche Formen zu beschreiben und in Computergrafiken nachzubilden.

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

01Alle Stufen übereinander

Statt nur der fertigen Flocke zeichnet die Schildkröte die Tiefen 0 bis 4 übereinander, von hell nach dunkel. So siehst du, wie jede Stufe aus der vorigen wächst: Aus jeder Strecke wird ein Zacken, aus jedem Zacken vier neue.

- t.color("#123f82", "#dbe7f6")    # Randfarbe, Füllfarbe
- t.begin_fill()
- snowflake(t, size, depth)
- t.end_fill()
+ colors = ["#cfd8e3", "#a3b8d0", "#6f92bd", "#3d6aa6", "#123f82"]
+ for level in range(depth + 1):
+     # jede Stufe vom selben Startpunkt aus neu zeichnen
+     t.penup()
+     t.goto(-size / 2, size * 0.29)
+     t.setheading(0)
+     t.pendown()
+     t.pencolor(colors[level % len(colors)])
+     snowflake(t, size, level)

02Die Kurve allein

Helge von Koch beschrieb 1904 zuerst nur eine einzelne Kurve – die Schneeflocke setzt drei davon zu einem Dreieck zusammen. Hier läuft die Schildkröte nur einmal von links nach rechts über die Leinwand.

- t.color("#123f82", "#dbe7f6")    # Randfarbe, Füllfarbe
- t.begin_fill()
- snowflake(t, size, depth)
- t.end_fill()
+ # nur eine einzige Koch-Kurve, quer über die Leinwand
+ t.penup()
+ t.goto(-270, -80)
+ t.pendown()
+ t.pencolor("#123f82")
+ koch(t, 540, depth)

03Die Anti-Schneeflocke

Dreht die Schildkröte an den Ecken nach links statt nach rechts, läuft sie das Dreieck andersherum ab. Die Zacken zeigen dann nach innen, und aus der Flocke werden drei Blasen, die nur an einzelnen Punkten zusammenhängen.
```
-         t.right(120)
+         t.left(120)
- t.goto(-size / 2, size * 0.29)   # linke obere Ecke, damit die Flocke mittig sitzt
+ t.goto(-size / 2, -size * 0.43)   # jetzt die linke untere Ecke
```
04Tiefe 6 – sofort fertig

Mit Tiefe 6 besteht der Rand aus 12.288 Strecken, jede kürzer als ein Pixel. Damit du nicht zu lange wartest, schaltet turtle.tracer(0) die Animation ab – das Bild erscheint auf einen Schlag. Noch mehr Tiefe siehst du auf dem Bildschirm nicht mehr.
```
- depth = 4     # so oft wird jede Strecke ersetzt
+ depth = 6     # so oft wird jede Strecke ersetzt
+ turtle.tracer(0)  # ohne Animation: das Bild erscheint sofort
```

Hinter den Kulissen

Dieses Beispiel steht nicht im Buch. Im Quellarchiv zum Buch liegen im Ordner kapitel12 aber zwei unveröffentlichte Experimente, kochkurve.py und hilbert.py. Sie zeichneten die Kurven mit Tkinter und bauten sie aus Ähnlichkeitsabbildungen mit komplexen Zahlen auf, die ein Hilfsmodul namens simify.py bereitstellte. Gedruckt wurden sie nie. Das Programm hier ist neu geschrieben, mit der Turtle-Grafik, die sich für Rekursion besonders anschaulich eignet.

Ein paar Dinge zur Turtle-Grafik im Browser:

Das Modul turtle ist auf dieser Website eine eigene, kleine Fassung, die auf der Leinwand zeichnet. Sie versteht die üblichen Befehle wie forward, left, goto, color, begin_fill und speed. Ein Programm, das damit läuft, läuft in der Regel auch mit dem echten turtle-Modul auf deinem Rechner.
Geschwindigkeit: Python rechnet die ganze Zeichnung in einem Rutsch aus; der Browser spielt sie danach Schritt für Schritt ab. t.speed(8) legt fest, wie viele Schritte pro Bild erscheinen. turtle.tracer(0) schaltet die Animation ganz ab. Beim echten turtle-Modul musst du danach am Ende turtle.update() aufrufen, damit das Bild erscheint.
Füllen: begin_fill() merkt sich die Punkte, an denen die Schildkröte vorbeikommt, und end_fill() füllt das entstandene Vieleck. Deshalb erscheint die Füllfarbe erst, wenn der Rand komplett ist.
Koordinaten: Die Schildkröte startet in der Mitte der Leinwand, und die y-Achse zeigt nach oben – anders als bei c4f und pygame, wo (0, 0) die linke obere Ecke ist und y nach unten wächst.