Die Hilbert-Kurve: eine Linie füllt ein Quadrat

Was du hier lernst

• Rekursion
• Turtle-Grafik
• raumfüllende Kurven
• Selbstähnlichkeit
• Farben mit colorsys
• global

Eine Linie, die ein Quadrat füllt

Eine Linie hat eine Länge, aber keine Fläche – so lernt man es in der Schule. Umso größer war die Überraschung, als Giuseppe Peano 1890 eine Kurve vorstellte, die durch jeden Punkt eines Quadrats läuft. Ein Jahr später fand David Hilbert eine einfachere Variante, die bis heute seinen Namen trägt. Wie die Koch-Kurve entsteht sie, indem man eine einfache Regel immer wieder anwendet – und wie diese lässt sie sich mit einer rekursiven Funktion und der Turtle-Grafik zeichnen.

Stufe 1: ein Hufeisen

Teile ein Quadrat in vier gleich große Felder. Die Hilbert-Kurve der Stufe 1 verbindet die Mittelpunkte dieser vier Felder mit drei Strecken: von links unten nach links oben, weiter nach rechts oben und hinunter nach rechts unten. Das sieht aus wie ein auf den Kopf gestelltes U oder ein Hufeisen.

Stufe für Stufe feiner

Für die nächste Stufe teilst du jedes der vier Felder wieder in vier. In jedes Viertel kommt eine verkleinerte Kopie der Kurve aus der vorigen Stufe. Damit die vier Kopien zu einer einzigen Linie zusammenpassen, werden die beiden unteren gedreht: Die Kopie links unten ist gespiegelt, sodass ihr Ende nach oben zeigt, die rechts unten ebenso, nur andersherum. Drei kurze Verbindungsstücke fügen die vier Teile zusammen.

Stufe 2 hat so 16 Felder, Stufe 3 hat 64, und allgemein hat Stufe n genau 4ⁿ Felder, von denen die Linie jedes genau einmal besucht. Sie kreuzt sich dabei nie und springt nie – sie ist ein einziger zusammenhängender Weg.

Die Rekursion

Genau diese Beschreibung setzt die Funktion hilbert() um:

def hilbert(t, level, angle):
    if level == 0:
        return
    t.right(angle)
    hilbert(t, level - 1, -angle)
    line(t)
    t.left(angle)
    hilbert(t, level - 1, angle)
    line(t)
    hilbert(t, level - 1, angle)
    t.left(angle)
    line(t)
    hilbert(t, level - 1, -angle)
    t.right(angle)

Die vier rekursiven Aufrufe zeichnen die vier Viertel, und die drei Aufrufe von line() sind die Verbindungsstücke dazwischen. Der Trick steckt im Parameter angle: Beim ersten und beim letzten Viertel wird er mit umgedrehtem Vorzeichen weitergegeben. Aus »rechts drehen« wird dort »links drehen« und umgekehrt – die Kopie entsteht spiegelverkehrt, genau wie oben beschrieben. Die Drehungen vor und nach jedem Teil richten die Schildkröte so aus, dass jede Kopie in der richtigen Lage gezeichnet wird.

Die Abbruchbedingung ist level == 0: Dann tut die Funktion gar nichts. Die Stufe 0 ist sozusagen ein einzelner Punkt, und alle sichtbaren Strecken entstehen als Verbindungsstücke auf den höheren Stufen.

Wie lang wird die Linie?

Bevor gezeichnet wird, rechnet das Programm aus, wie groß ein Schritt ist und wie viele Strecken es gibt:

step  = size / (2 ** level)   # Abstand zweier Feldmitten
total = 4 ** level - 1        # so viele Strecken hat die Kurve

Bei Stufe 5 hat das Quadrat 32 × 32 = 1.024 Felder, und die Linie besteht aus 1.023 Strecken von je 16 Pixeln. Zusammen sind das 16.368 Pixel – auf einem Quadrat mit 512 Pixeln Kantenlänge. Mit jeder Stufe verdoppelt sich die Länge ungefähr, während das Quadrat gleich groß bleibt. Die Schildkröte beginnt in der Mitte des Felds links unten; goto() bringt sie mit angehobenem Stift dorthin.

Der Regenbogen zeigt die Reihenfolge

Damit du siehst, in welcher Reihenfolge die Linie die Felder besucht, bekommt jede Strecke ihre eigene Farbe:

def line(t):
    # eine Strecke vorwärts – die Farbe wandert dabei durch den Regenbogen
    global drawn
    t.pencolor(colorsys.hsv_to_rgb(0.8 * drawn / total, 0.8, 0.85))
    t.forward(step)
    drawn += 1

Das Modul colorsys aus der Standardbibliothek rechnet Farben aus dem HSV-Modell in RGB um. Der erste Wert ist der Farbton: 0 ist Rot, 0,8 ist Violett, dazwischen liegen Gelb, Grün und Blau. Weil drawn von 0 bis total zählt, beginnt die Linie rot und endet violett. drawn steht außerhalb der Funktion, deshalb braucht line() die Anweisung global, um den Zähler verändern zu dürfen.

Nachbarn bleiben Nachbarn

Im fertigen Bild erkennst du eine wichtige Eigenschaft: Die Farben bilden zusammenhängende Flecken. Punkte, die auf der Linie nah beieinander liegen, liegen auch im Quadrat nah beieinander. Das erste Viertel der Linie füllt genau das linke untere Viertel des Quadrats, das erste Sechzehntel genau ein Sechzehntel.

Diese Lokalität macht die Hilbert-Kurve nützlich. Sie verwandelt zweidimensionale Positionen in eine einzige Zahl, die Position auf der Kurve, ohne dass Nachbarschaften verloren gehen. Datenbanken sortieren damit Orte, damit nahe Orte auch im Speicher nah beieinander liegen. Die Geometrie-Bibliothek S2 von Google teilt so die Erdoberfläche in Zellen ein, und Bildverfahren durchlaufen Pixel entlang einer Hilbert-Kurve, um Farbfehler gleichmäßig zu verteilen.

Der Grenzfall

Führt man die Konstruktion unendlich oft aus, kommt die Linie jedem Punkt des Quadrats beliebig nahe – im Grenzfall erreicht sie wirklich jeden Punkt. Mathematisch ist die Hilbert-Kurve eine stetige Abbildung von einer Strecke auf ein Quadrat. Damit war am Ende des 19. Jahrhunderts klar, dass sich »Dimension« nicht einfach über die Zahl der Koordinaten definieren lässt – eine der Entdeckungen, die später zur Theorie der Fraktale führten.

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.

1. 01Langsam zum Mitdenken

   Stufe 3 im Schneckentempo: Jetzt kannst du der Schildkröte folgen. Achte darauf, wie sie erst das linke untere Viertel füllt, dann das linke obere, das rechte obere und zuletzt das rechte untere – jedes Viertel ist wieder eine kleine Hilbert-Kurve.

   - level = 5     # Stufe der Kurve: das Quadrat hat 2 hoch level Felder je Seite
   + level = 3     # Stufe der Kurve: das Quadrat hat 2 hoch level Felder je Seite
   - t.speed(9)
   + t.speed(2)

   Ausprobieren

2. 02Nur das erste Viertel

   Nach einem Viertel der Strecken hebt die Schildkröte den Stift. Das Ergebnis: Das erste Viertel der Linie füllt genau das linke untere Viertel des Quadrats. Wer auf der Linie nah beieinander liegt, liegt auch im Quadrat nah beieinander.

   -     t.forward(step)
   -     drawn += 1
   +     if drawn == total // 4:
   +         t.penup()  # ab hier nur noch laufen, nicht mehr zeichnen
   +     t.forward(step)
   +     drawn += 1

   Ausprobieren

3. 03Feiner: Stufe 7

   Stufe 7 hat 128 × 128 = 16.384 Felder und 16.383 Strecken. Mit turtle.tracer(0) erscheint das Bild ohne Animation auf einmal. Die Linie wird immer länger, das Quadrat bleibt gleich groß – im Grenzfall füllt die Kurve jeden Punkt der Fläche.

   - level = 5     # Stufe der Kurve: das Quadrat hat 2 hoch level Felder je Seite
   + level = 7     # Stufe der Kurve: das Quadrat hat 2 hoch level Felder je Seite
   + turtle.tracer(0)  # ohne Animation: das Bild erscheint sofort

   Ausprobieren