Theoretische Informatik
Lindenmayer-Systeme: Fraktale
Wir haben Lindenmayer-Systeme (L-Systeme) dazu verwendet, raumfüllende Kurven zu zeichnen. Im Folgenden geht es um L-System zur Darstellung fraktaler Strukturen.
Sierpinski-Dreieck
Das D0L-System D = (A, P, s) mit
| A | = | { F, G, +, – } |
| P | : | F → F+G–F–G+F |
| G → GG | ||
| s | = | F+G+G |
erzeugt ein Sierpinski-Dreieck (nach W. Sierpinski
). Hier entsprechen die Zeichen F und G beide der Turtle-Grafik-Operation Vorwärtsbewegung; die Zeichen + und – entsprechen einer Linkswendung und einer Rechtswendung. Gleichzeitig dienen die Zeichen F und G der Steuerung der Struktur der Kurve.
Visualisierung Sierpinski-Dreieck
Die folgende Visualisierung zeigt die Ergebnisse der ersten sechs Generationen des L-Systems, interpretiert als Sierpinski-Dreieck.
Nächste Generation:
Drachen-Kurve
Das erstaunlich einfache D0L-System D = (A, P, s) mit
| A | = | {F, G, +, – } |
| P | : | F → F+G |
| G → F–G | ||
| s | = | F |
erzeugt eine Variante der Drachen-Kurve. Wiederum entsprechen die Zeichen F, G, + und – den Turtle-Grafik-Operationen Vorwärtsbewegung, Linkswendung und Rechtswendung. Die Zeichen F und G dienen gleichzeitig der Steuerung der Struktur der Kurve.
Visualisierung Drachen-Kurve
Die folgende Visualisierung zeigt die Ergebnisse der ersten zwölf Generationen des L-Systems, interpretiert als Drachen-Kurven.
Nächste Generation:
Weitere Turtle-Grafik-Operationen
Im Folgenden wird eine Fläche nicht durch eine Kurve, sondern durch einen binären Baum ausgefüllt. Wegen seiner selbstähnlichen Form eines H wird der Baum als H-Baum bezeichnet.
Um einen binären Baum effizient mithilfe von Turtle-Grafik-Operationen zu zeichnen, ist es erforderlich, bei einer Verzweigung den Zustand der Turtle zu speichern, also die aktuelle Position und Richtung der Turtle. So lässt sich nach Durchlaufen des einen Zweigs dieser Zustand wieder herstellen, bevor der andere Zweig durchlaufen wird.
Zum Speichern der Zustände der Turtle wird ein Stack verwendet. Als weitere Turtle-Grafik-Operationen kommen hinzu:
| push | Speichern des aktuellen Zustands der Turtle auf dem Stack | |
| pop | Wiederherstellen des Zustands, der sich zuoberst auf dem Stack befindet, und Entfernen dieses Zustands vom Stack |
In L-Systemen verwenden wir die Zeichen [ und ] für die Stack-Operationen push und pop.
H-Baum
Das D0L-System D = (A, P, s) mit
| A | = | { X, F, +, –, [, ] } |
| P | : | X → [–F[–FX]+FX]+F[–FX]+FX |
| F → FF | ||
| s | = | X |
erzeugt einen H-Baum. Wiederum entsprechen die Zeichen F, + und – den Turtle-Grafik-Operationen Vorwärtsbewegung, Linkswendung und Rechtswendung. Die Zeichen [ und ] entsprechen den Stack-Operationen push und pop. Das Zeichen X hat keine geometrische Interpretation, es steuert den Ersetzungsvorgang.
Visualisierung H-Baum
Die folgende Visualisierung zeigt die Ergebnisse der ersten vier Generationen des L-Systems, interpretiert als H-Baum.
Nächste Generation:
Grashalm
Das D0L-System D = (A, P, s) mit
| A | = | { F, X, +, –, [, ] } |
| P | : | X → F+[[X]–X]–F[–FX]+X |
| F → FF | ||
| s | = | X |
erzeugt einen Grashalm. Hierbei entsprechen die Zeichen F, + und – den Turtle-Grafik-Operationen Vorwärtsbewegung, Linkswendung um 25° und Rechtswendung um 25°. Die Zeichen X sowie [ und ] dienen der Steuerung der Struktur der Kurve. Bei einer öffnenden eckigen Klammer wird die aktuelle Position und die aktuelle Richtung der Turtle auf einem Stack gespeichert und bei der zugehörigen schließenden eckigen Klammer wiederhergestellt.
Visualisierung Grashalm
Die folgende Visualisierung zeigt die Ergebnisse der ersten fünf Generationen des L-Systems, interpretiert als Grashalm.
Nächste Generation:
Literatur
[Sal 73] A.K. Salomaa: Formal Languages. Academic Press (1973)
Weiter mit: [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 20.12.2012 Updated: 25.03.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden