Mathematische Bilder erstellen mit Context Free

In der Blogreihe „Wie erstellt man mathematische Bilder?“ stellen wir Werkzeuge vor, mit denen man einfach hochwertige mathematische Bilder erstellen kann. Dieser Artikel befasst sich mit dem Programm Context Free und zeigt, wie man damit Objekte visualisieren kann, die über gewisse Ersetzungsregeln definiert sind.

Kontextfreie Grammatiken und Fraktale

Context Free ist ein Programm, mit dem man Objekte zeichnen kann, die sich über gewisse Regelersetzungen beschreiben lassen. Der Begriff „kontextfreie Grammatik“ stammt aus dem Gebiet der Computerlinguistik. Dabei spielen Ersetzungsregeln der Form A → BC eine Rolle, die ein existierendes „Wort“ in ein anderes „Wort“ überführen. Kontextfrei bedeutet dabei, dass die Umgebung (der Kontext) des ersetzten Symbols nicht beachtet wird und sich in den Regeln nicht wiederfindet.

Ein Beispiel für ein mathematisches Objekt, das in ganz natürlicher Weise über solche Ersetzungsregeln erzeugt werden kann, ist das Sierpinski-Dreieck. Man beginnt mit einem Dreieck und ersetzt dieses dann durch drei ähnliche Dreiecke, die aber jeweils nur ein Viertel so groß sind:

Dann wendet man Rekursion an, also wiederholt die Regel für jedes der kleinen Dreiecke. Wenn man dieses Ersetzungsverfahren „unendlich oft“ durchführt, erhält man das Sierpinski-Dreieck:

Context Free Art

Kennt man ein Objekt, das durch solche Ersetzungsregeln definiert ist, und möchte davon eine grafische Darstellung erzeugen, kann man nun das Programm Context Free nutzen. Die Autoren des Programms haben die sogenannte „Context Free Design Grammar“ (CFDG) definiert, in der sich bestimmte Regeln ausdrücken lassen, aus denen dann ein Bild generiert werden kann.

Installation und Verwendung

Das Programm lässt sich von der Download-Seite der Projekts für Windows und Mac OS X als installierbares Programmpaket, für Linux als Quellcode zum Selbstkompilieren herunterladen. Unter Windows und Mac OS X existiert für das Programm eine grafische Benutzeroberfläche, in der links der CFDG-Code eingegeben und rechts das Ergebnis betrachtet werden kann (siehe nebenstehender Screenshot). Unter Linux existiert nur ein Kommandozeilenprogramm namens cfdg, das den Namen der mit einem beliebigen Texteditor erstellten CFDG-Datei und der zu erstellenden Bilddatei als Parameter erwartet.

Auf der Projekt-Website findet sich zum Einstieg eine kurze Einführung in CFDG und eine Liste von Tutorials.

Beispiel 1: Sierpinski-Dreieck

Wir wollen eine Darstellung des Sierpinski-Dreiecks mit Context Free berechnen. Dabei muss jedoch Folgendes beachtet werden: CFDG verwendet nicht wirklich „Ersetzungsregeln“ im Sinne von „entferne das Alte und zeichne dann das Neue“, sondern eher „Erweiterungsregeln“, also „zeichne das Alte und zeichne dann auch noch das Neue“.

Um das Sierpinski-Dreieck mit Context Free zu zeichnen, definieren wir genau eine Regel fract, die zunächst ein Dreieck zeichnet und sich dann drei Mal selbst aufruft. Dabei wird für die Unteraufrufe jeweils ein verschobener Ursprung (der Mittelpunkt des neuen Dreiecks; Parameter x bzw. y) und eine andere Skalierung (halbe Kantenlänge; Parameter s) verwendet. Außerdem wird für die Unteraufrufe die Farbe ein wenig heller gemacht (Parameter b), da man sonst am Ende eben nur ein schwarzes Dreieck sehen würde. Der Code dafür hat folgende Gestalt:

startshape fract

rule fract {
  TRIANGLE { }
  fract {         y .288   s .5  b .1}
  fract { x -.25  y -.144  s .5  b .1}
  fract { x  .25  y -.144  s .5  b .1}
}
</pre>#### text-block ####
text:
In der grafischen Benutzeroberfläche kann man diesen Code links eingeben und dann über das Menü Render → Render oder die Tastenkombination Strg+R ausführen lassen. Das dann im rechten Bereich angezeigte Bild lässt sich über das Menü Render → Save Image oder die Tastenkombination Strg+I als Datei speichern. Verwendet man die Kommandozeilenversion, speichert man den obigen Code in einer Datei ab, z.B. sierpinski.cfdg, und lässt Context Free mit dem Befehl cfdg sierpinski.cfdg sierpinski.png direkt in eine Bilddatei rendern. In beiden Fällen sollte folgendes Bild zu sehen sein:

Eine wichtige Komponente beim Zeichnen dieses Bildes ist, die Rekursion bei einer bestimmten Rekursionstiefe abzubrechen. Wir erinnern uns: Das Sierpinski-Dreieck ist das Resultat einer unendlich oft angewendeten Ersetzungsregel. Auf dem Computer ist das natürlich so nicht möglich, denn wir wollen ja möglichst noch zu Lebzeiten das fertige Bild betrachten können. Context Free bestimmt also von alleine den Zeitpunkt, zu dem die Rekursion abgebrochen werden kann, weil sich das Bild nicht mehr verändert.

Beispiel 2: Fibonacci-Spirale

Die Fibonacci-Spirale (siehe auch den Blog zu den Fibonacci-Zahlen) bzw. das umschließende System aus Quadraten ist ein weiteres Beispiel für ein Objekt, das über kontextfreie Regeln zu definieren ist.

Wir schreiben eine Funktion fib, die

1. ein Quadrat der Seitenlänge 1 zeichnet und
2. sich im Anschluss mit verschobener Position und Skalierung selbst aufruft;

vergleiche dazu auch die nebenstehende Schemazeichnung. Um als Endergebnis nicht nur ein schwarzes Rechteck zu sehen, erhöhen wir außerdem in jedem Schritt die Helligkeit, wie oben.

Der entsprechende Code

startshape fib

rule fib {
  SQUARE { }
// mit phi = goldener Schnitt (1.618...):
  fib { x -0.80901699437494745  // -0.5*(1+1/phi)
        y  0.1909830056250526   // (1-1/phi)/2
        s  0.61803398874989479  // 1/phi
        r  90    // drehen um 90°
        b  .1 }  // Helligkeit erhöhen
}
</pre>#### text-block ####
text:
erzeugt folgendes Bild:

Man kann natürlich auch etwas mehr Farbe ins Bild bringen und statt der Helligkeit z.B. in jedem Schritt den Farbton (H im HSB-Farbmodell) verändern. Der angepasste und aus Lesbarkeitsgründen umformatierte Quellcode

startshape fib

rule fib {
  SQUARE { !b 1   !sat 1 }   // Helligkeit=1, Sättigung=1
fib { x -0.8090169943749  y 0.190983005625
        s 0.6180339887498  r 90
        h  20 }  // Farbton ändern
}
</pre>#### text-block ####
text:
erzeugt die deutlich farbenfrohere Version:

Zufallswege mit Context Free

Brown’sche Bewegung und Zufallswege

Wahlweise aus dem Biologieunterricht oder einer Stochastikvorlesung dürfte Vielen der Begriff der brown'schen Bewegung bekannt sein. Diese Bewegung kann z.B. bei Teilchen in einer Lösung beobachtet werden. Diese bewegen sich in eine rein zufällige Richtung und dabei auch noch „ohne Gedächtnis“, d.h. die Position in der Zukunft hängt nur von der aktuellen Position ab, nicht von der Vergangenheit, also des bereits zurückgelegten Weges. (In der Stochastik nennt man dies die Markov-Eigenschaft.)

Die einfachste Methode, eine zweidimensionale brown'sche Bewegung (also in der Ebene) zu simulieren, sind sogenannte Zufallsbewegungen (Random Walks) auf einem quadratischen Gitter. Man geht dabei in jedem Schritt zufällig einen Gitterpunkt nach links, rechts, oben oder unten, was sich im Computer leicht umsetzen lässt. Man kann zeigen, dass sich für kleiner werdende Gitterweite diese Zufallswege immer mehr dem echten Verhalten einer brown'schen Bewegung annähern.

Umsetzung in CFDG

Die Eigenschaft von Zufallswegen, kein Gedächtnis zu haben, lässt erahnen, dass sie sich über kontextfreie Regeln ausdrücken lassen. Wir wollen einen solchen Zufallsweg mit Context Free visualisieren, wobei die Farbe anzeigt, wie weit wir schon gegangen sind. Zunächst müssen wir in der Lage sein, zufällig eine Richtung auszuwählen. Dabei nutzen wir aus, dass wenn es in Context Free mehrere Regeln mit dem gleichen Namen gibt, eine dieser Regeln gleichverteilt zufällig ausgewählt wird. Da wir vier Richtungen haben, schreiben wir vier Regeln mit dem Namen walk, die

1. eine Linie in eine bestimmte Richtung zeichnen und
2. sich dann selbst mit Verschiebung in diese Richtung aufrufen.

Die Regel, die den Schritt nach rechts beschreibt, hat die folgende Form:

rule walk {  // rechts
  SQUARE  { size 1 .1 }  // Rechteck mit Breite 1 und Höhe 0.1
  walk { x 1   h .0005| }  // gehe 1 nach rechts und ändere Farbe
}

Die Regeln für die anderen drei Richtungen sehen analog aus:

rule walk {  // links
  SQUARE  { size -1 .1 }
  walk { x -1   h .0005| }
}
rule walk {  // oben
  SQUARE  { size .1 1 }
  walk { y 1   h .0005| }
}
rule walk {  // unten
  SQUARE  { size .1 -1 }
  walk { y -1   h .0005| }
}

Aus diesen vier Richtungen wird nun zufällig eine ausgewählt. Damit die Rekursion nicht ewig weiterläuft, brauchen wir noch eine Regel, die mit einer gewissen Wahrscheinlichkeit aufgerufen wird und den Zufallsweg beendet. Dafür können wir eine weitere Regel mit dem Namen walk definieren und direkt nach dem Namen die Wahrscheinlichkeit angeben, dass diese Regel ausgewählt wird (je höher die Wahrscheinlichkeit, desto früher endet der Weg). Am Ende des Pfades wollen wir einen Kreis zeichnen. Der Code hat die folgende Gestalt:

rule walk 0.002 {  // Wahrscheinlichkeit 0.2%
  CIRCLE  { b 1 }
}

Nun müssen wir die Startregel definieren. Wir könnten walk selbst als Startregel definieren, hätten dann aber keine Chance, vorher noch etwas zu tun oder die Startfarbe festzulegen. Daher definieren wir eine eigene Regel start, die erst einen roten Kreis zeichnet und dann walk mit der Startfarbe rot aufruft. Schließlich setzen wir noch die Hintergrundfarbe auf schwarz, damit die Farben kräftiger wirken.

startshape start

rule start {
  CIRCLE  {
    sat 1   b 1   |h 120   // Farbe: rot
  }
  walk {
    sat 1   b 1   |h 120
  }
}
background { b -1 }
</pre>#### text-block ####
text:
Der komplette Code ist als Download verfügbar. Führt man diesen Code in Context Free aus, ergibt sich ein Bild wie das folgende:

Probieren Sie doch selbst einmal die Arbeit mit Context Free aus! Sie können sich von der Bildergalerie auf der Context-Free-Website inspirieren lassen – wir freuen uns auf Ihr Feedback und Ihre Bildeinreichungen!