powrót do strony głównej >>

Fraktale: Systemy Lindenmayera

Copyright © 2005   Robert Nowotniak

Systemy Lindenmayera są drugim rodzajem fraktali (po układach iterowanych odwzorowań), które szczególnie mnie zaciekawiły. Między innymi z powodu ich związku z lingwistyką matematyczną. Istotę L-Systemów dobrze oddaje cytat z ,,Automata, Languages, Development'':

The development of an organism [...] may be considered as the execution of a ,,developmental program'' present in the fertilized egg. The cellularity of higher organisms and their DNA components force us to consider developing organism as dynamic collections of appropriately programmed finite automata. A central task of developmental biology is to discover the underlying algorithm from the course of development.
-- A. Lindenmayer, G. Rozenberg
Applet w Javie
Mój applet

Jeżeli Twoja przeglądarka obsługuje Javę, możesz skorzystać z mojego appletu, który prezentuje wiele fraktali opartych na systemach Lindenmayera i pozwala dowolnie z nimi eksperymentować.



Wersja wielowątkowa
Aplet wielowątkowy

Wielowątkowość pozwala w naturalny sposób modelować współbieżny podział komórek w żywym organiźmie. Ta wersja apletu działa właśnie w ten sposób, wykorzystując synchronizację pomiędzy wątkami za pomocą semaforów.

L-Systemy są ściśle związane z zagadnieniami lingwistyki matematycznej. Zasadniczą różnicą pomiędzy formalizmem bezkontekstowych gramatyk generacyjnych Chomsky'ego a systemem Lindenmayera jest sposób podstawiania produkcji. W gramatykach Chomsky'ego symbole są zastępowane sekwencyjnie, podczas gdy w L-Systemach wszystkie symbole w danym napisie są zastępowane jednocześnie. Odzwierciedla to współbieżny podział komórek w żywym organiźmie. Z tego względu istnieją języki generowane przez bezkontekstowe L-Systemy, które nie mogą być wygenerowane przez bezkontekstowe gramatyki Chomsky'ego.

Interpreter łańcucha symboli, uzyskanego przez cykl podstawień, opiera się na wprowadzonej przez S.Paperta idei grafiki żółwia.

W wielu publikacjach dotyczących L-Systemów i ich analogii do dzieł przyrody jest przywoływany rozwój komórek sinicy z gatunku Anabaena Catenula. Ich podział można bardzo prosto opisać za pomocą dwóch reguł produkcji. Występują tu dwa rodzaje komórek: A () i B (). Długość obydwu rodzajów komórek zwiększa się w stałym tempie. Po przekroczeniu pewnej długości komórka A dzieli się na dwie części: mniejszą - kopię samej siebie i większą - komórkę typu B. Komórka B dzieli się na część większą - komórkę typu A, i mniejszą - kopię samej siebie. A3→A1B2, B3→A2B1.















Rozwój komórek glonu Anabaena Catenula. (Kod w PHP)


W moim programie zbiór rozpoznawanych symboli przedstawia poniższa tabela. Jest to mocno uproszczona wersja tablicy symboli podanej w The Algorithmic Beauty of Plants. Istnieje wiele mniej lub bardziej rozbudowanych modyfikacji tego języka w zależności od konkretnego programu badajacego L-Systemy. Stosowane są różne oznaczenia na zmianę kąta o dowolną wartość lub koloru na dowolny spośród palety (np. C<n> lub C+<n>)


Tabela symboli L-Systemów
F krok naprzód, rysuj
f krok naprzód, bez rysowania
+ obrót w lewo
- obrót w prawo
[ stan na stos
] użyj stanu zdjętego ze stosu
< poprzedni kolor
> następny kolor
* pomnożenie długości kroku przez czynnik standardowy
/ podzielenie długości kroku przez czynnik standardowy
( [*
) *]

Przykładowe L-Systemy

Poniżej znajduje się kilkadziesiąt L-Systemów, których parametry znalazłem głównie w sieci. Wszystkie te L-Systemy są zawarte w moim programie. Przełączenia kolorów dobierałem według wyczucia. Jak się okazuje, jest to zupełnie proste po kilku doświadczeniach. Ważne jest, aby po zmianie koloru i wejścia w gałąź (czyli podstawieniu produkcji), powrócić do koloru początkowego.

Gramatyki probabilistyczne – i losowe chwasty

Ciekawe rezultaty można uzyskać, wprowadzając element losowy do L-Systemu. Uzyskamy wówczas niedeterministyczny układ, którego rezultatem mogą być takie rośliny jak na rysunku obok.


  F → F[+F]F[-F]F     P(F) = 1/3
  F → F[+F]F     P(F) = 1/3
  F → F[-F]F     P(F) = 1/3


Zastosowanie losowego kąta w L-Systemie. Reguły produkcji:
   F → FF
   G → F[β1G][β2G]F[β3G]+G,
gdzie:
   0°≤β1≤+60°,            0°≤β2≤-70°,            0°≤β3≤-60°

Drzewa i rośliny

Dąb

Drzewka na poniższej serii obrazów to L-System o pięciu różnych wartościach współczynnika standardowego.

L-System a układ iterowanych odwzorowań

Poniższe dwa obrazy zostały wygenerowane moimi dwoma różnymi programami. Drzewo po lewej stronie poniżej zostało wygenerowane przez L-System, natomiast drzewo po prawej – przez układ czterech soczewek KWR. Obydwa mechanizmy równie mocno świadczą o fraktalnej geometrii przyrody.

Grot Sierpińskiego

Kolejna konstrukcja, którą można uzyskać przez KWR, dużo bardziej znana w tamtej postaci.

Smoki

Drugi z poniższych smoków jest bardzo podobny do smoka Hartera-Heighwaya.

Inne

Krzywa Peano – krzywa wypełniająca przestrzeń

Do zrobienia

Oto zagadnienia związane z L-Systemami, którymi chciałbym się jeszcze zająć, a których tu nie opisałem:

Pliki

Pliki do pobrania
Nazwa Data Opis
LSystem.java 2005-07-21 kod źródłowy klasy w Javie implementującej L-System. Jest to część mojego programu. Nie ma tu żadnych elementów interfejsu użytkownika.
lsystems.tgz 2005-07-21 Kod w Javie mojego programu do badania L-Systemów

Linki


Copyright © Robert Nowotniak
20 lipca 2005