Theoretische Informatik

Lindenmayer-Systeme: Raumfüllende Kurven

 aufwärts

Ein bedeutendes Anwendungs­gebiet von L-Systemen ist die Erzeugung von selbst­ähnlichen geo­metrischen Objekten. Selbst­ähnlich bedeutet hier, dass das Objekt in ähnlicher Form Teil seiner selbst ist.

Hierzu werden die Alphabet­zeichen des L-Systems als geometrische Operationen oder Objekte inter­pretiert. Jedes Vorkommen eines Alphabet­zeichens im erzeugten Wort des L-Systems entspricht einer geo­metrischen Operation oder einem geo­metrischen Objekt in einer bestimmten Lage im Raum.

Als erstes betrachten wir die Erzeugung von raum­füllenden Kurven; dies sind Linien, die eine Fläche oder einen Raum beliebig dicht ausfüllen.

Turtle-Grafik

Eine Möglichkeit der geo­metrischen Inter­pretation der Alphabet­zeichen sind sogenannte Turtle-Grafik-Operationen. Die Vorstellung ist hier, dass ein Roboter auf der Zeichenebene hin- und herfährt und dabei Linien zeichnet 1). Er wird durch die folgenden vier einfachen Kommandos gesteuert:

F(x) Vorwärts­bewegung um eine bestimmte Länge x und dabei zeichnen
f(x) Vorwärts­bewegung um eine bestimmte Länge x, ohne zu zeichnen
+(α) Richtungs­änderung nach links um einen bestimmten Winkel α
–(α) Richtungs­änderung nach rechts um einen bestimmten Winkel α

Im Folgenden ordnen wir zunächst den Alphabet­zeichen F, + und – die geo­metrischen Operationen F(1), +(90°) und –(90°) zu. Somit beschreibt beispiels­weise das Wort F+F+F+F ein Quadrat der Kantenlänge 1.

Hilbert-Kurve

Eine Hilbert-Kurve (nach D. Hilbertzur Person) ist eine Linie, die eine Fläche beliebig dicht ausfüllt, je nach Anzahl der Iterationen. Wir beschreiben im Folgenden eine Hilbert-Kurve durch ein L-System, dessen Zeichen als Turtle-Grafik-Operationen inter­pretiert werden.

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

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

erzeugt Hilbert-Kurven. Hierbei entsprechen die Zeichen F, + und – den Turtle-Grafik-Operationen Vorwärts­bewegung mit Zeichnen, Linkswendung und Rechts­wendung. Die Zeichen X und Y haben keine geometrische Inter­pretation, sie steuern den Ersetzungs­vorgang an den Ecken der Kurve.

Bild 1: Erste und zweite Generation des L-Systems und zugehörige Hilbert-Kurven
Bild 1: Erste und zweite Generation des L-Systems und zugehörige Hilbert-Kurven
Visualisierung

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

(Java-Applet zur Darstellung von Hilbert-Kurven)

Peano-Kurve

Eine andere raumfüllende Kurve ist die Peano-Kurve (nach G. Peanozur Person).

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

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

erzeugt eine Peano-Kurve. Wiederum entsprechen die Zeichen F, + und – den Turtle-Grafik-Operationen Vorwärts­bewegung mit Zeichnen, Linkswendung und Rechts­wendung, und die Zeichen X und Y haben keine geometrische Inter­pretation, sie steuern den Ersetzungs­vorgang.

Visualisierung

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

(Java-Applet zur Darstellung von Peano-Kurven)

Literatur

[Sal 73]A.K. Salomaa: Formal Languages. Academic Press (1973)
[PL 90]http://algorithmicbotany.org/papers/abop/abop.pdf

1)  Als es noch keine Roboter gab, nahm man eine Schildkröte (engl.: turtle), die man mithilfe eines Salatblatts in die gewünschte Richtung lockte.

 

Weiter mit:  [Fraktale]   oder   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