L-System - L-system

L-System-Bäume bilden realistische Modelle natürlicher Muster

Ein L-System oder Lindenmayer-System ist ein paralleles Umschreibsystem und eine Art formale Grammatik . Ein L-System besteht aus einem Alphabet von Symbolen, die verwendet werden können, um Zeichenketten zu erstellen , einer Sammlung von Produktionsregeln , die jedes Symbol in eine größere Zeichenkette erweitern, einer anfänglichen " Axiom "-Zeichenkette, von der aus mit der Konstruktion begonnen wird, und einem Mechanismus für Übersetzen der erzeugten Strings in geometrische Strukturen. L-Systeme wurden 1968 von Aristid Lindenmayer , einem ungarischen theoretischen Biologen und Botaniker an der Universität Utrecht, eingeführt und entwickelt . Lindenmayer verwendete L-Systeme, um das Verhalten von Pflanzenzellen zu beschreiben und die Wachstumsprozesse der Pflanzenentwicklung zu modellieren . L-Systeme wurden auch verwendet, um die Morphologie einer Vielzahl von Organismen zu modellieren und können verwendet werden, um selbstähnliche Fraktale zu erzeugen .

Ursprünge

'Unkraut', erzeugt mit einem L-System in 3D.

Als Biologe arbeitete Lindenmayer mit Hefe und filamentöse Pilze und die Wachstumsmuster der verschiedenen Arten von untersuchten Bakterien , wie beispielsweise die Cyanobakterien Anabaena catenula . Ursprünglich wurden die L-Systeme entwickelt, um die Entwicklung solcher einfacher vielzelliger Organismen formal zu beschreiben und die Nachbarschaftsbeziehungen zwischen Pflanzenzellen zu veranschaulichen. Später wurde dieses System erweitert, um höhere Pflanzen und komplexe Verzweigungsstrukturen zu beschreiben.

L-System-Struktur

Die rekursive Natur der L-System - Regeln führt zu Selbstähnlichkeit und damit fraktale -ähnliche Formen sind einfach , mit einem L-System zu beschreiben. Pflanzenmodelle und natürlich wirkende organische Formen sind leicht zu definieren, da durch die Erhöhung des Rekursionsniveaus die Form langsam „wächst“ und komplexer wird. Auch bei der Erzeugung von künstlichem Leben sind Lindenmayer-Systeme beliebt .

Die Grammatiken des L-Systems sind der Semi-Thue -Grammatik sehr ähnlich (siehe Chomsky-Hierarchie ). L-Systeme sind heute allgemein als parametrische L-Systeme bekannt, definiert als Tupel

G = ( V , ω, P ),

wo

  • V (das Alphabet ) ist ein Satz von Symbolen, der sowohl Elemente enthält, die ersetzt werden können ( Variablen ) als auch solche, die nicht ersetzt werden können ("Konstanten" oder "Klemmen")
  • ω ( Start , Axiom oder Initiator ) ist eine Zeichenkette aus V , die den Anfangszustand des Systems definiert
  • P ist ein Satz von Produktionsregeln oder Produktionen , die definieren, wie Variablen durch Kombinationen von Konstanten und anderen Variablen ersetzt werden können. Eine Produktion besteht aus zwei Saiten, dem Vorgänger und dem Nachfolger . Für jedes Symbol A, das Mitglied der Menge V ist, das nicht auf der linken Seite einer Produktion in P vorkommt, wird die Identitätsproduktion A → A angenommen; diese Symbole werden Konstanten oder Terminals genannt . (Siehe Gesetz der Identität ).

Die Regeln der L-Systemgrammatik werden ausgehend vom Anfangszustand iterativ angewendet. Pro Iteration werden so viele Regeln wie möglich gleichzeitig angewendet. Die Tatsache, dass jede Iteration möglichst viele Regeln verwendet, unterscheidet ein L-System von einer formalen Sprache, die durch eine formale Grammatik generiert wird , die nur eine Regel pro Iteration anwendet. Wenn die Produktionsregeln jeweils nur einzeln angewendet würden, würde man ganz einfach eine Sprache anstelle eines L-Systems generieren. Somit sind L-Systeme strikte Teilmengen von Sprachen.

Ein L-System ist kontextfrei, wenn sich jede Produktionsregel nur auf ein einzelnes Symbol und nicht auf seine Nachbarn bezieht. Kontextfreie L-Systeme werden somit durch eine kontextfreie Grammatik spezifiziert . Wenn eine Regel nicht nur von einem einzelnen Symbol, sondern auch von seinen Nachbarn abhängt, spricht man von einem kontextsensitiven L-System.

Wenn es für jedes Symbol genau eine Produktion gibt, dann wird das L-System als deterministisch bezeichnet (ein deterministisches kontextfreies L-System wird im Volksmund als D0L-System bezeichnet ). Wenn es mehrere gibt und jedes mit einer bestimmten Wahrscheinlichkeit während jeder Iteration ausgewählt wird, dann handelt es sich um ein stochastisches L-System.

Die Verwendung von L-Systemen zur Erzeugung von grafischen Bildern erfordert, dass sich die Symbole im Modell auf Elemente einer Zeichnung auf dem Computerbildschirm beziehen. Zum Beispiel der Programm Fractint Anwendungen Schildkröte Grafiken (ähnlich wie in der Programmiersprache Logo ) zu erzeugen , Bildschirmbildern. Es interpretiert jede Konstante in einem L-System-Modell als Turtle-Befehl.

Beispiele für L-Systeme

Beispiel 1: Algen

Lindenmayers Original L-System zur Modellierung des Algenwachstums.

Variablen  : AB
Konstanten  : keine
Axiom  : A
Regeln  : (A → AB), (B → A)

die produziert:

n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

Beispiel 1: Algen, erklärt 

n=0:               A             start (axiom/initiator)
                  / \
n=1:             A   B           the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
                /|     \
n=2:           A B      A        former string AB with all rules applied, A spawned into AB again, former B turned into A
             / | |       | \
n=3:         A B A       A B     note all A's producing a copy of themselves in the first place, then a B, which turns ...
           / | | | \     | \ \
n=4:       A B A A B     A B A   ... into an A one generation later, starting to spawn/repeat/recurse then

Das Ergebnis ist die Folge von Fibonacci-Wörtern . Wenn wir die Länge jeder Saite zählen, erhalten wir die berühmte Fibonacci-Zahlenfolge (wobei die erste 1 aufgrund unserer Wahl des Axioms übersprungen wird):

1 2 3 5 8 13 21 34 55 89 ...

Wenn wir die erste 1 nicht überspringen möchten, können wir Axiom B verwenden . Das würde den B- Knoten vor den obersten Knoten ( A ) des obigen Graphen platzieren.

Wenn wir für jeden String die k- te Position vom linken Ende des Strings zählen, wird der Wert dadurch bestimmt, ob ein Vielfaches des Goldenen Schnitts in das Intervall fällt . Das Verhältnis von A zu B konvergiert ebenfalls gegen den goldenen Mittelwert.

Dieses Beispiel liefert das gleiche Ergebnis (in Bezug auf die Länge jedes Strings, nicht die Folge von A s und B s), wenn die Regel ( A → AB ) durch ( A → BA ) ersetzt wird, außer dass die Strings gespiegelt werden.

Diese Sequenz ist eine lokal katenative Sequenz, weil , wo die n- te Generation ist.

Beispiel 2: Fraktaler (binärer) Baum

  • Variablen  : 0, 1
  • Konstanten : „[“, „]“
  • Axiom  : 0
  • Regeln  : (1 → 11), (0 → 1[0]0)

Die Form wird erstellt, indem das Axiom rekursiv durch die Produktionsregeln geführt wird. Jedes Zeichen der Eingabezeichenfolge wird anhand der Regelliste überprüft, um zu bestimmen, durch welches Zeichen oder welche Zeichenfolge es in der Ausgabezeichenfolge ersetzt werden soll. In diesem Beispiel wird eine '1' in der Eingabezeichenfolge zu '11' in der Ausgabezeichenfolge, während '[' gleich bleibt. Wenden wir dies auf das Axiom von '0' an, erhalten wir:

Axiom: 0
1. Rekursion: 1[0]0
2. Rekursion: 11[1[0]0]1[0]0
3. Rekursion: 1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
…

Wir können sehen, dass diese Zeichenfolge schnell an Größe und Komplexität zunimmt. Diese Zeichenfolge kann mithilfe von Turtle-Grafiken als Bild gezeichnet werden , wobei jedem Symbol eine grafische Operation zugewiesen wird, die die Turtle ausführen soll. Im obigen Beispiel kann der Schildkröte beispielsweise die folgenden Anweisungen gegeben werden:

  • 0: Zeichne ein Liniensegment, das in einem Blatt endet
  • 1: Zeichnen Sie ein Liniensegment
  • [: Position und Winkel drücken, um 45 Grad nach links drehen
  • ]: Pop-Position und -Winkel, um 45 Grad nach rechts drehen

Push und Pop beziehen sich auf einen LIFO- Stack (eine technische Grammatik hätte separate Symbole für "Drückposition" und "links abbiegen"). Wenn die Turtle-Interpretation auf ein '[' trifft, werden die aktuelle Position und der Winkel gespeichert und dann wiederhergestellt, wenn die Interpretation auf ein ']' trifft. Wenn mehrere Werte "gepusht" wurden, stellt ein "Pop" die zuletzt gespeicherten Werte wieder her. Wenden wir die oben aufgeführten grafischen Regeln auf die frühere Rekursion an, erhalten wir:

  • Axiom

  • Erste Rekursion

  • Zweite Rekursion

  • Dritte Rekursion

  • Vierte Rekursion

  • Siebte Rekursion, zehnmal verkleinert

Beispiel 3: Cantor-Set

Cantor-Set in sieben Iterationen.svg
Variablen  : AB
Konstanten  : keine
start  : Eine {Anfangszeichenfolge}
Regeln  : (A → ABA), (B → BBB)

Lassen Sie A "vorwärts ziehen" und B "vorwärts bewegen" bedeuten.

Dies erzeugt die berühmte Cantor-Fraktalmenge auf einer echten Geraden R .

Beispiel 4: Kochkurve

Eine Variante der Koch-Kurve, die nur rechte Winkel verwendet.

Variablen  : F
Konstanten  : + −
Anfang  : F
Regeln  : (F → F+F−F−F+F)

Dabei bedeutet F „nach vorne ziehen“, + bedeutet „90° nach links drehen“ und − bedeutet „90° nach rechts drehen“ (siehe Turtle-Grafik ).

n = 0:
F
Koch-Quadrat - 0 Iterationen
n = 1:
F+F−F−F+F
Koch-Quadrat - 1 Iterationen
n = 2:
F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F
Koch-Platz - 2 Iterationen
n = 3:
F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F+
F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F−
F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F−
F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F+
F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F
Koch-Platz - 3 Iterationen

Beispiel 5: Sierpinski-Dreieck

Das Sierpinski-Dreieck, gezeichnet mit einem L-System.

Variablen  : FG
Konstanten  : + −
Anfang  : F−G−G
Regeln  : (F → F−G+F+G−F), (G → GG)
Winkel  : 120°

Hier bedeutet F "vorwärts ziehen", G "vorwärts ziehen", + bedeutet "winkelig nach links abbiegen" und - bedeutet "winkelig nach rechts abbiegen".

  • n = 2

  • n = 4

  • n = 6

Es ist auch möglich, das Sierpinski-Dreieck mit einem Sierpiński-Pfeilspitzenkurven- L-System anzunähern .

Variablen  : AB
Konstanten  : + −
Anfang  : A
Regeln  : (A → B−A−B), (B → A+B+A)
Winkel  : 60°

Hier bedeuten A und B beide „nach vorne ziehen“, + bedeutet „im Winkel nach links abbiegen“ und − bedeutet „im Winkel nach rechts abbiegen“ (siehe Turtle-Grafik ).

Serpinski Lsystem.svg
Entwicklung für n = 2, n = 4, n = 6, n = 8

Beispiel 6: Drachenkurve

Die Drachenkurve wurde mit einem L-System gezeichnet.

Variablen  : FG
Konstanten  : + −
Anfang  : F
Regeln  : (F → F+G), (G → FG)
Winkel  : 90°

Hier bedeuten F und G beide "nach vorne ziehen", + bedeutet "im Winkel nach links abbiegen" und - bedeutet "im Winkel nach rechts abbiegen".

Drachenkurve L-system.svg
Drachenkurve für n = 10

Beispiel 7: Fraktale Pflanze

Siehe auch: Barnsley Farn
Variablen  : XF
Konstanten  : + − [ ]
Anfang  : X
Regeln  : (X → F+[[X]-X]-F[-FX]+X), (F → FF)
Winkel  : 25°

Dabei bedeutet F „vorwärts ziehen“, − bedeutet „um 25° rechts abbiegen“ und + bedeutet „um 25° links abbiegen“. X entspricht keiner Zeichenaktion und wird verwendet, um die Entwicklung der Kurve zu steuern. Die eckige Klammer "[" entspricht dem Speichern der aktuellen Werte für Position und Winkel, die beim Ausführen des entsprechenden "]" wiederhergestellt werden.

Fraktale Pflanze für n = 6

Variationen

Es wurden eine Reihe von Ausführungen zu dieser grundlegenden L-System-Technik entwickelt, die in Verbindung miteinander verwendet werden können. Dazu gehören stochastische Grammatiken , kontextsensitive Grammatiken und parametrische Grammatiken.

Stochastische Grammatiken

Das bisher besprochene Grammatikmodell war deterministisch – das heißt, für jedes beliebige Symbol im Alphabet der Grammatik gab es genau eine Produktionsregel, die immer gewählt wird und immer dieselbe Konvertierung durchführt. Eine Alternative besteht darin, mehr als eine Produktionsregel für ein Symbol anzugeben, wobei jeder eine Wahrscheinlichkeit des Auftretens zugewiesen wird. In der Grammatik von Beispiel 2 könnten wir beispielsweise die Regel zum Umschreiben von "0" ändern von:

0 → 1[0]0

zu einer Wahrscheinlichkeitsregel:

0 (0.5) → 1[0]0
0 (0,5) → 0

Wenn bei dieser Produktion eine "0" während des Umschreibens von Zeichenketten angetroffen wird, besteht eine Wahrscheinlichkeit von 50 %, dass sie sich wie zuvor beschrieben verhält, und eine Wahrscheinlichkeit von 50 %, dass sie sich während der Produktion nicht ändert. Wenn eine stochastische Grammatik in einem evolutionären Kontext verwendet wird, ist es ratsam, einen zufälligen Seed in den Genotyp einzubauen , damit die stochastischen Eigenschaften des Bildes zwischen den Generationen konstant bleiben.

Kontextsensitive Grammatiken

Eine kontextsensitive Produktionsregel betrachtet nicht nur das Symbol, das sie ändert, sondern auch die Symbole in der Zeichenfolge, die davor und danach erscheinen. Zum Beispiel die Produktionsregel:

b < a > c → aa

wandelt "a" in "aa" um, aber nur, wenn das "a" zwischen einem "b" und einem "c" in der Eingabezeichenfolge auftritt:

…bac…

Wie bei stochastischen Produktionen gibt es mehrere Produktionen, um Symbole in unterschiedlichen Kontexten zu handhaben. Wenn für einen gegebenen Kontext keine Produktionsregel gefunden werden kann, wird die Identitätsproduktion angenommen und das Symbol ändert sich bei der Transformation nicht. Wenn kontextsensitive und kontextfreie Produktionen innerhalb derselben Grammatik existieren, wird davon ausgegangen, dass die kontextsensitive Produktion Vorrang hat, wenn sie anwendbar ist.

Parametrische Grammatiken

In einer parametrischen Grammatik ist jedem Symbol im Alphabet eine Parameterliste zugeordnet. Ein mit seiner Parameterliste gekoppeltes Symbol wird als Modul bezeichnet, und ein String in einer parametrischen Grammatik ist eine Reihe von Modulen. Eine Beispielzeichenfolge könnte sein:

a(0,1)[b(0,0)]a(1,2)

Die Parameter können sowohl von den Zeichenfunktionen als auch von den Produktionsregeln verwendet werden. Die Produktionsregeln können die Parameter auf zwei Arten verwenden: erstens in einer bedingten Anweisung, die bestimmt, ob die Regel angewendet wird, und zweitens kann die Produktionsregel die tatsächlichen Parameter ändern. Schauen Sie sich zum Beispiel an:

a(x,y) : x == 0 → a(1, y+1)b(2,3)

Der Modul a(x,y) wird nach dieser Produktionsregel transformiert, wenn die Bedingung x=0 erfüllt ist. Zum Beispiel würde a(0,2) einer Transformation unterzogen werden und a(1,2) nicht.

Im Transformationsteil der Produktionsregel können die Parameter sowie ganze Module beeinflusst werden. Im obigen Beispiel wird dem String das Modul b(x,y) mit den Anfangsparametern (2,3) hinzugefügt. Außerdem werden die Parameter des bereits vorhandenen Moduls transformiert. Unter der obigen Produktionsregel,

a(0,2)

Wird

a(1,3)b(2,3)

da der "x"-Parameter von a(x,y) explizit in eine "1" umgewandelt wird und der "y"-Parameter von a um eins erhöht wird.

Parametrische Grammatiken ermöglichen die Bestimmung von Linienlängen und Verzweigungswinkeln durch die Grammatik und nicht durch die Methoden der Turtle-Interpretation. Auch wenn das Alter als Parameter für ein Modul angegeben wird, können sich die Regeln in Abhängigkeit vom Alter eines Anlagensegments ändern, sodass Animationen des gesamten Lebenszyklus des Baums erstellt werden können.

Bidirektionale Grammatiken

Das bidirektionale Modell trennt explizit das symbolische Umschreibungssystem von der Formzuweisung. Zum Beispiel ist der String-Neuschreibprozess in Beispiel 2 (Fraktalbaum) unabhängig davon, wie grafische Operationen den Symbolen zugewiesen werden. Mit anderen Worten, eine unendliche Anzahl von Zeichenverfahren ist auf ein gegebenes Umschreibsystem anwendbar.

Das bidirektionale Modell besteht aus 1) einem Vorwärtsprozess, der den Ableitungsbaum mit Produktionsregeln konstruiert, und 2) einem Rückwärtsprozess, der den Baum mit Formen schrittweise realisiert (von den Blättern bis zur Wurzel). Jeder Schritt der inversen Ableitung beinhaltet wesentliche geometrisch-topologische Überlegungen. Mit diesem bidirektionalen Rahmen werden Entwurfsbeschränkungen und -ziele in der grammatikalischen Übersetzung codiert. In Architekturdesignanwendungen bietet die bidirektionale Grammatik eine konsistente innere Konnektivität und eine umfassende räumliche Hierarchie.

Offene Probleme

Es gibt viele offene Probleme, die Studien von L-Systemen betreffen. Zum Beispiel:

  • Charakterisierung aller deterministischen kontextfreien L-Systeme, die lokal katenativ sind . (Eine vollständige Lösung ist nur für den Fall bekannt, dass es nur zwei Variablen gibt).
  • Finden Sie bei einer gegebenen Struktur ein L-System, das diese Struktur erzeugen kann.

Arten von L-Systemen

L-Systeme auf der realen Linie R :

Bekannte L-Systeme auf einer Ebene R 2 sind:

Siehe auch

Anmerkungen

Bücher

Externe Links

  1. ^ Pradal, Christophe; Fournier, Christian; Valduriez, Patrick; Cohen-Boulakia, Sarah (2015). OpenAlea: Wissenschaftliche Workflows, die Datenanalyse und Simulation kombinieren (PDF) . Proceedings of the 27th International Conference on Scientific and Statistical Database Management - SSDBM '15 . P. 1. doi : 10.1145/2791347.2791365 . ISBN 9781450337090. S2CID  14246115 .
  2. ^ Boudon, Frederic; Pradal, Christophe; Cokelaer, Thomas; Prusinkiewicz, Przemyslaw; Godin, Christophe (2012). "L-Py: Ein L-System-Simulations-Framework zur Modellierung der Entwicklung von Anlagenarchitekturen basierend auf einer dynamischen Sprache" . Grenzen in der Pflanzenwissenschaft . 3 : 76. doi : 10.3389/fpls.2012.00076 . PMC  3362793 . PMID  22670147 .