Theoretische Informatik

Lindenmayer-Systeme: Fraktale

 aufwärts

Wir haben Lindenmayer-Systeme (L-Systeme) dazu verwendet, raumfüllende Kurven zu zeichnen. 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.

Weitere Turtle-Grafik-Operationen

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 Wieder­herstellen 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:Pfeil nach rechts [–F[–FX]+FX]+F[–FX]+FX
Pfeil nach rechts FF
s=X

erzeugt einen H-Baum. Wiederum entsprechen die Zeichen F, + und – den Turtle-Grafik-Operationen Vorwärts­bewegung, Linkswendung und Rechts­wendung. Die Zeichen [ und ] entsprechen den Stack-Operationen push und pop. Das Zeichen X hat keine geometrische Inter­pretation, es steuert den Ersetzungs­vorgang.

Visualisierung

Die folgende Visualisierung zeigt die Ergebnisse der ersten vier Generationen des L-Systems, inter­pretiert als H-Bäume.

(Java-Applet zur Darstellung von H-Bäumen)

Sierpinski-Dreieck

Das D0L-System D = (A, P, s) mit

A = { F, G, +, – }
P:Pfeil nach rechts F+G–F–G+F
Pfeil nach rechts GG
s=F+G+G

erzeugt ein Sierpinski-Dreieck (nach W. Sierpinskizur Person). Hier entsprechen die Zeichen F und G beide der Turtle-Grafik-Operation Vorwärts­bewegung; die Zeichen + und – entsprechen einer Linkswendung und einer Rechts­wendung.

Visualisierung

Die folgende Visualisierung zeigt die Ergebnisse der ersten sieben Generationen des L-Systems, inter­pretiert als Sierpinski-Dreiecke.

(Java-Applet zur Darstellung von Sierpinski-Dreiecken)

Drachen-Kurve

Das D0L-System D = (A, P, s) mit

A = { X, Y, F, +, – }
P:Pfeil nach rechts Y+FX
Pfeil nach rechts YF–X
s=X

erzeugt eine Variante der Drachen-Kurve. Wiederum entsprechen die Zeichen F, + und – den Turtle-Grafik-Operationen Vorwärts­bewegung, Linkswendung und Rechts­wendung. Die Zeichen X und Y dienen der Steuerung der Struktur der Kurve.

Visualisierung

Die folgende Visualisierung zeigt die Ergebnisse der ersten 11 Generationen des L-Systems, inter­pretiert als Drachen-Kurven.

(Java-Applet zur Darstellung von Drachen-Kurven)

Grashalm

Das D0L-System D = (A, P, s) mit

A = { F, X, +, –, [, ] }
P:Pfeil nach rechts F+[[X]–X]–F[–FX]+X
Pfeil nach rechts FF
s=X

erzeugt einen Grashalm. Hierbei entsprechen die Zeichen F, + und – den Turtle-Grafik-Operationen Vorwärts­bewegung, Linkswendung um 25° und Rechts­wendung 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 wieder­hergestellt.

Visualisierung

Die folgende Visualisierung zeigt die Ergebnisse der ersten fünf Generationen des L-Systems, inter­pretiert als Grashalme.

(Java-Applet zur Darstellung von Grashalmen)

Literatur

[Sal 73]A.K. Salomaa: Formal Languages. Academic Press (1973)
[PL 90]http://algorithmicbotany.org/papers/abop/abop.pdf
[Web 1]http://en.wikipedia.org/wiki/L-system  

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 20.12.2012   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik