Zobrazení zdroje stránky L-systém

{{Dobrý článek}}
[[Soubor:Fractal weeds.jpg|náhled|300px|Traviny vymodelované pomocí L-systémů ve 3D]]
'''L-systém''' nebo také '''[[Aristid Lindenmayer|Lindenmayerův]] systém''' je varianta [[Formální gramatika|formální gramatiky]], vyvinutá pro modelování růstu [[Rostliny|rostlin]]. L-systém popisuje [[Formální gramatika|pravidla]] pro vývoj rostliny, která se opakovaně aplikují na vznikající [[Model (abstrakce)|model]]. Tato pravidla mohou např. popisovat, za jakých podmínek se [[stonek]] rostliny rozdvojí, zda má vzniknout [[list]] nebo zda má část rostliny uhynout. Výsledný model se může např. vykreslit jako [[Digitální obraz|obrázek]] nebo se z něj vytvoří počítačový [[Počítačová 3D grafika|3D model]] rostliny. L-systémy se také dají použít pro generování různých [[křivka|křivek]], [[fraktál]]ů nebo pro modelování [[buňka|buněčných]] [[organismus|organismů]].
<ref>{{Citace monografie
| titul = A model for cellular development in morphogenetic fields
| jméno = Martin
| příjmení = Boear
| jméno2 = David
| příjmení2 = Fracchia
| jméno3 = Przemyslaw
| příjmení3 = Prusinkiewicz
| počet stran = 20
| jazyk = anglicky
| url = http://algorithmicbotany.org/papers/cellsystem.ls1992.html
| formát = PDF
}}</ref>

== Historie ==
L-systémy byly vyvinuty v roce 1968 [[Maďarsko|maďarským]] [[Biologie|biologem]] [[Aristid Lindenmayer|Aristidem Lindenmayerem]] jako matematický formalizmus pro popisování růstu řas.
<ref>{{Citace monografie
| titul = Mathematical models for cellular interactions in development
| jméno = Aristid
| příjmení = Lindenmayer
| svazek = Journal of theoretical biology Parts I and II
| vydavatel = Elsevier
| strany = 280–315
| rok = 1968
| jazyk = anglicky
}}</ref>
Symboly představovaly jednotlivé buňky a přepisovací pravidla L-systému simulovaly jejich dělení.
Později [[Polsko|polský]] [[informatik]] [[Przemyslaw Prusinkiewicz]] interpretoval symboly L-systémů pomocí [[Želví grafika|želví grafiky]] (tedy symboly představovaly grafické elementy jako např. úsečky).
Touto metodou se již dalo modelovat širší spektrum rostlin a různé fraktálové křivky.
<ref>{{Citace monografie
| titul = Graphical applications of L-systems
| jméno = Przemyslaw
| příjmení = Prusinkiewicz
| vydavatel = Department of Computer Science, University of Regina
| jazyk = anglicky
}}</ref>
Lindenmayer spolu s Prusinkiewiczem publikovali knihu ''The Algorithmic Beauty of Plants''<ref name="abop">{{Citace monografie
| titul = The Algorithmic Beauty of Plants
| jméno = Aristid
| příjmení = Lindenmayer
| jméno2 = Przemyslaw
| příjmení2 = Prusinkiewicz
| spoluautoři = a kol.
| vydavatel = Springer
| počet stran = 228
| jazyk = anglicky
| url = http://algorithmicbotany.org/papers/#abop
| rok copyrightu = 1991
| formát = PDF
}}</ref>, která se dnes dá považovat za bibli L-systémů.

Postupem času se L-systémy začaly používat i pro další věci než je modelování rostlin a fraktálů.
Například jde pomocí nich modelovat tok řek ve fraktálových horách<ref>{{Citace monografie
| titul = A fractal model of mountains and rivers
| jméno = P.
| příjmení = Prusinkiewicz
| jméno2 = M.
| příjmení2 = Hammel
| vydavatel = Canadian Information Processing Society
| jazyk = anglicky
| rok copyrightu = 1993
| strany = 174–180
}}</ref>, ulice ve virtuálních městech<ref>{{Citace monografie
| titul = Procedural modeling of cities
| jméno = Y.I.H.
| příjmení = Parish
| jméno2 = P.
| příjmení2 = Müller
| jazyk = anglicky
| rok copyrightu = 2001
| strany = 301–308
| isbn = 1-58113-374-X
| url-access = registration
| url = https://archive.org/details/siggraph2001conf00fium
}}</ref> nebo pomocí L-systémů lze popisovat podrozdělování (zjemňování) křivek<ref>{{Citace monografie
| titul = L-system description of subdivision curves
| svazek = International Journal of Shape Modeling
| jméno = Przemyslaw
| příjmení = Prusinkiewicz
| spoluautoři = a kol.
| jazyk = anglicky
| rok copyrightu = 2003
| strany = 41–59
}}</ref>. Nicméně L-systémy mohou být použity i v jiných oborech než je počítačová grafika, například lze pomocí nich generovat hudbu<ref>{{Citace elektronické monografie
 | příjmení = Hazard
 | jméno = C.
 | příjmení2 = Catherine
 | jméno2 = K.
 | příjmení3 = Johnson
 | jméno3 = D.
 | titul = Fractal Music
 | url = http://www.tursiops.cc/fm/
 | datum přístupu = 2012-03-01
 | jazyk = anglicky
 | url archivu = https://web.archive.org/web/20120222212202/http://www.tursiops.cc/fm/
 | datum archivace = 2012-02-22
 | nedostupné = ano
 }}</ref><ref>{{Citace monografie
| titul = Musical L-systems
| vydavatel = Nepublikovaná magisterská práce, Institute of Sonology, Hague
| jméno = S.
| příjmení = Manousakis
| jazyk = anglicky
| rok copyrightu = 2006
}}</ref>.

Ve [[film]]u [[Avatar (film, 2009)|Avatar]] z roku [[2009]] bylo přes 2000 [[strom]]ů, [[Rostliny|rostlin]] a [[Kapradiny|kapradin]] vymodelováno právě pomocí L-systémů.<ref>[http://www.grafika.cz/art/dv/cgfilm-avatar-runforartefacts.html Avatar a Run for the Artefact: Goliáš a David počítačové animace]</ref>

== Definice L-systému ==
Základní typ L-systému je tzv. ''D0L-systém''. ''D0'' v názvu značí, že se jedná o ''deterministický bezkontextový'' L-systém. Formálně je to trojice <math>G = (\Sigma, S, P)</math><ref name="abop" />, kde
* <math>\Sigma</math> je ''[[Abeceda (formální jazyky)|abeceda]]'', tj. [[neprázdná množina]] symbolů, <math>\Sigma^*</math> je [[množina]] všech [[Slovo (formální jazyky)|slov]] nad abecedou <math>\Sigma</math>, <math>\Sigma^+</math> je množina všech neprázdných slov nad abecedou <math>\Sigma</math>,
* <math>S \in \Sigma^+</math> je ''semínko'' (z angl. ''seed'') nebo také ''[[axiom]]'', což je konečné slovo z abecedy <math>\Sigma</math>, které definuje počáteční stav L-systému,
* <math>P \subset \Sigma \times \Sigma^*</math> je konečná množina ''přepisovacích pravidel'',
** přepisovací pravidlo se zapisuje ve tvaru <math>a \rightarrow S</math>, kde <math>a \in \Sigma</math> a <math>S \in \Sigma^*</math>, definuje tedy přepsání symbolu na slovo (které může být i prázdné),
** pro symbol <math>b \in \Sigma</math>, který se neobjevuje na levé straně žádného přepisovacího pravidla, je definována [[Identita (matematika)|identita]] (<math>b \rightarrow b</math>) (takové symboly jsou často označovány jako [[konstanta|konstanty]]).

D0L-systém je velice podobný [[deterministická bezkontextová gramatika|deterministické bezkontextové gramatice]]. Liší se například v tom, že gramatika rozlišuje [[Terminální symbol|terminální]] a [[neterminální symbol]]y, ale L-systém pro neterminály definuje identitu jako výchozí přepisovací pravidlo. Další rozdíl je v tom, že gramatika má jako semínko jeden neterminální symbol, ale L-systém povoluje neprázdné slovo (libovolný konečný [[Slovo (formální jazyky)|řetězec]] symbolů).

Každý symbol z abecedy je obvykle reprezentován jedním [[Znak (počítače)|znakem]] ([[Písmeno|písmenem]]), což značně ulehčuje a zrychluje zápis. Avšak existují i speciální symboly, které jsou zapsány více znaky. Jsou to většinou velmi specifické symboly pro interpretaci. Aby se rozlišily vícepísmenné symboly, dává se před ně nějaký speciální [[prefix]], např. [[zavináč]]. Ten pak není součástí abecedy.
<ref>{{Citace monografie
| titul = Hairs, Textures, and Shades: Improving the Realism of Plant Models Generated with L-Systems
| jméno = Martin
| příjmení = Fuhrer
| počet stran = 121
| jazyk = anglicky
| url = http://algorithmicbotany.org/papers/fuhrer.th2005.html
| rok copyrightu = 2005
| formát = PDF
}}</ref>

== Iterativní vývoj L-systému ==
L-systém se vytváří po '''[[Iterace|iteracích]]''', někdy zvaných též '''generace'''. ''N''-tá generace je definována [[Rekurze|rekurzivními]] pravidly:
* nultá iterace je samotný axiom
* ''n''-tá iterace (pro <math>n > 0</math>) vznikne paralelní aplikací přepisovacích pravidel na výsledek iterace <math>n-1</math>
Paralelní aplikace je nahrazení všech symbolů „najednou“. Paralelní přepsání se dá provést i sériově, a sice tak, že se postupně přepisují symboly zleva doprava, ale výsledek se ukládá na jiné místo (nevkládá se jako náhrada přepisovaného symbolu). Tak se docílí toho, že symboly vzniklé přepsáním se nepřepíší podruhé.

=== Příklad 1: růst řas ===
Následující příklad je Lindenmayerův původní L-systém pro modelování růstu [[Řasy|řas]] (konkrétně [[Anabaena|Anabaena catenula]]). Tato řasa má dva typy [[Buňka|buněk]], které tvoří řetízky. Každý typ se vyznačuje odlišným chováním, které probíhá ve fázích. Následující L-systém zachycuje právě toto chování.

{{L-systém
| abeceda = A B
| axiom = A
| rrp0 = A | rrr0 = AB
| rrp1 = B | rrr1 = A
}}

Jednotlivé iterace vypadají následovně:

:''i'' = 0 : <tt>A</tt>
:''i'' = 1 : <tt>AB</tt>
:''i'' = 2 : <tt>ABA</tt>
:''i'' = 3 : <tt>ABAAB</tt>
:''i'' = 4 : <tt>ABAABABA</tt>
:''i'' = 5 : <tt>ABAABABAABAAB</tt>
:''i'' = 6 : <tt>ABAABABAABAABABAABABA</tt>
:''i'' = 7 : <tt>ABAABABAABAABABAABABAABAABABAABAAB</tt>

Procentuální zastoupení A : B inklinuje k poměru 61,8034 : 38,1966 %.

=== Příklad 2: Fibonacciho posloupnost ===
Mějme následující [[Formální gramatika|gramatiku]]:

{{L-systém
| abeceda = A B
| axiom = A
| rrp0 = A | rrr0 = B
| rrp1 = B | rrr1 = AB
}}

Oproti 1. příkladu se liší pouze v prohození vzorů přepisovacích pravidel, nicméně výsledek bude odlišný.

:''i'' = 0 : <tt>A</tt>
:''i'' = 1 : <tt>B</tt>
:''i'' = 2 : <tt>AB</tt>
:''i'' = 3 : <tt>BAB</tt>
:''i'' = 4 : <tt>ABBAB</tt>
:''i'' = 5 : <tt>BABABBAB</tt>
:''i'' = 6 : <tt>ABBABBABABBAB</tt>
:''i'' = 7 : <tt>BABABBABABBABBABABBAB</tt>

Zajímavé na tomto L-systému je to, že délka výsledného řetězce v ''i''-té iteraci je rovna ''i''-tému číslu ve [[Fibonacciho posloupnost]]i (pro <math>\text{fib}(0) = 1</math> a <math>\text{fib}(1) = 1</math>):

: 1, 1, 2, 3, 5, 8, 13, 21, …

Výstupní řetězec má stejnou vlastnost, která platí pro Fibonacciho posloupnost, tj. ''i''-té číslo (<math>i>1</math>) je součtem předchozích dvou. Tedy ''i''-tá iterace tvořena spojením iterací <math>i-2</math> a <math>i-1</math>. Malou změnou druhého přepisovacího pravidla na (<tt>B&nbsp;→&nbsp;BA</tt>) bude výsledek splňovat stejné vlastnosti jako původní, jen se budou iterace spojovat „popořadě“, tedy ''i''-tá iterace bude tvořena spojením iterací <math>i-1</math> a <math>i-2</math>. Z toho vyplývá i to, že délky jednotlivých iterací budou také odpovídat číslům ve Fibonacciho posloupnosti. Tato odlišnost ve Fibonacciho posloupnosti není, protože sčítání dvou [[Číslo|čísel]] je [[Komutativita|komutativní]].

Další zajímavou vlastností řetězců v příkladech 1 a 2 je úzká souvislost se [[Zlatý řez|zlatým řezem]]. Pro <math>i>0</math> platí, že symbol na ''k''-tém místě od neměnného konce („začátek“ u př. 1, „konec“ u př. 2) je buď <tt>A</tt> nebo <tt>B</tt>, podle toho, zda nějaký celočíselný násobek zlatého řezu padne (náleží) do [[Otevřený interval|otevřeného intervalu]] <math>(k, k+1)</math>. Poměr počtu symbolů <tt>A</tt> a <tt>B</tt> tedy pro <math>i \rightarrow \infty</math> [[Konvergentní posloupnost|konverguje]] k hodnotě zlatého řezu

<math>\varphi = {1+\sqrt5 \over 2} \approx 1,618.</math>

V následující tabulce je tato vlastnost konkrétně ukázána na L-systému Fibonacciho posloupnosti.

{| class="wikitable"
|-
! k !! k-tý symbol !! interval !! nás. zl. řezu !! matematický důvod
|-
| 1 || align="center" | B || align="center" | (1, 2) || align="center" | 1 || <math>\varphi \approx 1,6181 \in (1, 2)</math>
|-
| 2 || align="center" | A || align="center" | (2, 3) || align="center" | neexistuje || <math>\varphi \approx 1,618 \notin (2, 3)</math> a <math>2\varphi \approx 3,236 \notin (2,3)</math>
|-
| 3 || align="center" | B || align="center" | (3, 4) || align="center" | 2 || <math>2\varphi \approx 3,236 \in (3,4)</math>
|-
| 4 || align="center" | B || align="center" | (4, 5) || align="center" | 3 || <math>3\varphi \approx 4,854 \in (4,5)</math>
|-
| 5 || align="center" | A || align="center" | (5, 6) || align="center" | neexistuje || <math>3\varphi \approx 4,854 \notin (5,6)</math> a <math>4\varphi \approx 6,472 \notin (5,6)</math>
|-
| 6 || align="center" | B || align="center" | (6, 7) || align="center" | 4 || <math>4\varphi \approx 6,472 \in (6,7)</math>
|}

== Interpretace symbolů ==
Jednotlivé symboly L-systému se mohou interpretovat jakkoli. U některých L-systémů je podstatný pouze počet symbolů v ''i''-té iteraci, u jiných se symboly chápou jako příkazy pro kreslení nebo dokonce mohou reprezentovat základní části rostliny (např. jako 3D modely), ze kterých se „poskládá“ výsledný model.

=== Vykreslování ve 2D ===
[[Soubor:Kturtle side view.svg|náhled|200px|Představa, jak želva něco kreslí (želví grafika)]]
Obvyklá (a jedna z nejjednodušších) je interpretace pomocí [[Želví grafika|želví grafiky]]. Tato interpretace chápe symboly jako příkazy pro ''štětec'' (želvu nesoucí štětec), který podle nich kreslí [[Úsečka|úsečky]] a vyplněné [[Mnohoúhelník|polygony]] v [[Rovina|rovině]]. Interpretace probíhá dvoufázově, nejprve se L-systém vygeneruje (''vyiteruje'') do požadované iterace a poté se výsledek interpretuje (kreslí). Pro první fázi musí být zadán počet iterací a pro druhou výchozí stav štětce (želvy). Ten v nejjednodušší variantě obsahuje ''délku kroku'' a ''úhel otočení'' štětce, ale může obsahovat i různé další údaje, jako např. barvu nebo šířku štětce. Během druhé fáze interpretace je také udržován ''stav štětce'' v rovině, tedy v jakém místě se nachází a jak je orientován. V následující tabulce je shrnuta obvyklá interpretace symbolů ve druhé fázi. Tyto příkazy dávají rozkazy štětci (želvě).

{| class="wikitable"
|-
! Symboly !! Interpretace
|-
| <tt>A</tt>-<tt>U</tt>, <tt>0</tt>-<tt>9</tt> || „Nakresli úsečku.“, úsečka je nakreslena ve směru orientace štětce (délka úsečky je ''délka kroku'')
|-
| <tt>a</tt>-<tt>u</tt> || „Pohni se vpřed (bez kreslení).“ (délka pohybu je ''délka kroku'')
|-
| <tt>V</tt>-<tt>Z</tt>, <tt>v</tt>-z || „Nedělej nic.“, obvykle se jedná o písmena ke konci abecedy, hranice není ustálena (používá se pro potřeby vývoje L-systému)
|-
| <tt>+</tt>, <tt>-</tt> || „Otoč se doleva (resp. doprava) o předem stanovený úhel.“ (o ''úhel otočení'') 
|-
| <tt><nowiki>|</nowiki></tt> || „Otoč se čelem vzad.“ (rotace o 180°)
|-
| <tt>[</tt> || „Zapamatuj si aktuální stav.“, přesněji řečeno „Ulož aktuální stav na [[Zásobník (datová struktura)|zásobník]].“ (stavem se myslí aktuální poloha a orientace v rovině)
|-
| <tt>]</tt> || „Přesuň se na naposledy zapamatovaný stav.“, přesněji řečeno „Přesuň se na pozici, kterou určuje stav na vrcholu zásobníku a ten z vrcholu odstraň“
|-
| <tt>{</tt> || „Ulož rozpracovaný polygon na zásobník a začni zaznamenávání bodů nového polygonu.“
|-
| <tt>.</tt> || „Přidej bod, na kterém stojíš do aktuálního polygonu.“
|-
| <tt>}</tt> || „Vykresli rozpracovaný polygon a načti polygon z vrcholu zásobníku jako aktuální polygon (pokud tam nějaký je).“
|}

Pokud nebude uvedeno jinak, tato interpretace je použita u všech ukázek v tomto článku.

=== Vykreslování ve 3D ===
Výše uvedená [[2D]] interpretace se dá jednoduše rozšířit do [[3D]]. ''Štětec'' se bude pohybovat v [[Prostor (geometrie)|prostoru]] místo v rovině. Stav bude podobný, tedy bude to poloha a orientace v prostoru. Pro pohyb v trojrozměrném prostoru je třeba více příkazů pro otočení, protože se dá otáčet podle 3 [[Osa|os]] (ve 2D je pouze 1 osa). V následující tabulce je seznam interpretací symbolů, které je potřeba přidat.

[[Soubor:Roll, yaw, pitch.jpg|náhled|200px|Graficky znázorněné otáčení ve 3D]]
{| class="wikitable"
|-
! Symboly !! Interpretace
|-
| <tt>+</tt>, <tt>-</tt> || „otoč se doleva (resp. doprava) o předem stanovený úhel“ (stejné jako ve 2D), pokud si představíte ''štětec'' jako [[letadlo]] a směr ''štětce'' jako směr letu letadla, pak tyto symboly představují zahýbání letadla doleva a doprava, z pohledu pilota (angl. ''yaw'' viz obr.)
|-
| <tt>^</tt>, <tt>&</tt> || „otoč se nahoru (resp. dolů) o předem stanovený úhel“, u letadla by to znamenalo stoupání a klesání (angl. ''pitch'' viz obr.)
|-
| <tt>/</tt>, <tt>\</tt> || „otoč se doleva (resp. doprava) podle osy určené mým směrem o předem stanovený úhel“, u letadla by tyto příkazy vypadaly jako „výkrut“, otáčení podél osy letu (angl. ''roll'' viz obr.)
|}

== Příklady L-systémů ==
=== Kochova vločka ===
[[Soubor:KochTurtleAnim.gif|náhled|Animace interpretace L-systému želví grafikou]]
Následující předpis vygeneruje část [[Kochova vločka|Kochovy vločky]].

{{L-systém
| abeceda = F + -
| axiom = F
| rrp0 = F | rrr0 = F+F--F+F
| uhel = 60
}}
''pozn.: výchozí poloha štětce (želvy) je vlevo dole a štětec je orientován vpravo''

:''i'' = 0: <tt>F</tt>
:[[Soubor:KochCurve0.svg|0. generace (axiom) Kochovy vločky]]

:''i'' = 1: <tt>F+F--F+F</tt>
:[[Soubor:KochCurve1.svg|1. generace Kochovy vločky]]

:''i'' = 2: <tt>F+F--F+F + F+F--F+F-- F+F--F+F + F+F--F+F</tt>
:[[Soubor:KochCurve2.svg|2. generace Kochovy vločky]]

:''i'' = 3: <tt>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</tt>
:[[Soubor:KochCurve3.svg|3. generace Kochovy vločky]]

=== Stromeček ===
L-systémy byly vytvořeny pro modelování růstu [[Rostliny|rostlin]]. Vymodelovat jednoduchý [[strom]]eček je proto velmi jednoduché.

{{L-systém
| abeceda = M S + - [ ]
| axiom = M
| rrp0 = M | rrr0 = S[+M][-M]SM
| rrp1 = S | rrr1 = SS
| uhel = 45
}}

Přepisovací pravidla by se dala popsat slovy takto:
* symbol <tt>M</tt> představuje mladou část rostliny (na obr. zeleně), symbol <tt>S</tt> starou část (hnědě)
* první přepisovací pravidlo říká, že každá mladá část <tt>M</tt> se přepíše (nahradí) za starou část <tt>S</tt>, pak dvě mladé větvičky vlevo (<tt>[+M]</tt>) a vpravo (<tt>[-M]</tt>), dále starou část <tt>S</tt> a nakonec mladou část <tt>M</tt>
* druhé říká pouze to, že každá stará část <tt>S</tt> se přepíše na dvě staré části <tt>SS</tt>, jinými slovy, délka starých částí se mezi iteracemi zdvojnásobí

Na následujícím obrázku můžete vidět prvních 6 iterací i s grafickým znázorněním přepisovacích pravidel.

[[Soubor:LsystemTree.svg|Prvních 6 iterací fraktálu stromečku]]

=== Ostrovy a jezera ===
[[Soubor:IslandsAndLakesRewriteRule.svg|náhled|200px|Graficky znázorněné přepisovací pravidlo L-systému Ostrovy a jezera]]
Další [[fraktál]] generovaný pomocí L-systémů se jmenuje ''„Ostrovy a jezera“'' (z angl. '' „Islands and lakes“''). Jeho předpis můžete také nalézt v knize ''The Algorithmic Beauty of Plants'' na str. 9.<ref name="abop" />

{{L-systém
| abeceda = F f + -
| axiom = F+F+F+F
| rrp0 = F | rrr0 = F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF
| rrp1 = f | rrr1 = ffffff
| uhel = 90
}}

Výše uvedený předpis pro jednoduchost kreslí pouze hranice [[ostrov]]ů a [[Jezero|jezer]]. Avšak pro lepší představu byl následující obrázek vygenerován rozšířeným předpisem o příkazy, které generují [[polygon]]y.

[[Soubor:IslandsAndLakesColored.svg|400px|3. iterace L-systému Ostrovy a jezera]]

=== Penroseovo dláždění ===
Pomocí složitějšího L-systému se dá generovat [[Penroseovo dláždění]].

{{L-systém
| abeceda = M N O P + - [ ] { . }
| axiom = [N]++[N]++[N]++[N]++[N]
| rrp0 = M | rrr0 = O++{.P.----N.[-O.----M.}]++
| rrp1 = N | rrr1 = +{.O.--P.[---M.--N.}]+
| rrp2 = O | rrr2 = -<nowiki/>{.M.++N.[+++O.++P.}]-
| rrp3 = P | rrr3 = --{.O.++++M.[+P.++++N.}]--N
| uhel = 36
}}
''pozn.: vykreslování úseček proběhne až po vykreslení všech polygonů (aby je polygony nepřekryly)''

<gallery>
image:PenroseTilingFilled0.svg|0. generace
image:PenroseTilingFilled1.svg|1. generace
image:PenroseTilingFilled2.svg|2. generace
image:PenroseTilingFilled3.svg|3. generace
image:PenroseTilingFilled4.svg|4. generace
</gallery>

=== Gosperova křivka ===
[[Soubor:HexaGosperCurveRewriteRule.svg|náhled|200px|Vizualizace přepisovacího pravidla Gosperovy křivky]]
Následující křivka, která je pojmenovaná po [[Amerika|americkém]] [[matematik]]ovi a [[programátor]]ovi jménem [[Bill Gosper]], splňuje definici [[Peanovy křivky#Plochu-vyplňující křivky|plochu-vyplňující křivky]] a také [[Peanovy křivky#FASS křivky|FASS křivky]].

{{L-systém
| abeceda = L R + -
| axiom = L
| rrp0 = L | rrr0 = L+R++R-L--LL-R+
| rrp1 = R | rrr1 = -L+RR++R+L--L-R
| uhel = 60
}}

Na následujícím obrázku je 5. iterace Gosperovy křivky plynule obarvena celým [[Barevné spektrum|barevným spektrem]] od červené až po fialovou. Díky tomu lze vidět, kudy a jak křivka vede.

[[Soubor:HexaGosperCurveColored.svg|5. iterace Gosperovy křivky obarvená celým barevným spektrem od červené po fialovou a zpět k červené pro lepší pozorování jejího vývoje]]

== Parametrické L-systémy ==
'''Parametrický L-systém''' (''PL-systém'') je rozšíření základního L-systému o [[Parametr funkce|parametry]] symbolu. Ke každému symbolu může být asociován libovolný konečný počet parametrů. Parametr je obvykle [[reálné číslo]], se kterým se dají dělat běžné [[Operace (matematika)|matematické operace]]. Jako parametr může být dosazen i aritmetický výraz, funkce nebo proměnná. Hodnota takového parametru se vyčíslí jako reálné číslo vždy, když je třeba.

Pro zápis parametrů se používá závorková syntaxe. Hodnoty parametru se za symbol píší do kulatých [[Závorky|závorek]]. Tyto závorky, ani žádné symboly v nich, se nepovažují jako symboly L-systému. Jednotlivé parametry uvnitř závorek se oddělují [[Čárka (interpunkce)|čárkou]]. V následující tabulce je uvedeno několik příkladů zápisu.

{| class="wikitable"
|-
! Syntaxe !! Popis
|-
| <tt>F(1)</tt> || symbol F s parametrem 1
|-
| <tt>F(0, 1, √2)</tt> || symbol F s parametry 0, 1 a √2
|-
| <tt>F(, 1)</tt> || symbol F s 1. parametrem nezadaným a 2. parametrem 1
|-
| <tt>F(x)</tt> || symbol F, který má jako 1. parametr proměnnou ''x''
|}

Zápis přepisovacího pravidla parametrického L-systému vypadá např. takto:

<tt>A(t) → B(t/2) C(5) D E(1/t, 8)</tt>.

Slovní popis: „Symbol <tt>A</tt> s parametrem ''t'' (jehož hodnota se vyčíslí jako reálné číslo) se přepíše na symbol <tt>B</tt> s parametrem <math>t/2</math>, symbol <tt>C</tt> s parametrem <math>5</math>, symbol <tt>D</tt> bez parametru a symbol <tt>E</tt> s parametry <math>1/t</math> a 8.“

=== Interpretace ===
Parametry symbolů slouží zejména pro snadné předávání číselných hodnot pro interpretaci a pro řízení vývoje L-systému. Při interpretaci symbolů [[Želví grafika|želví grafikou]], která se používá v tomto článku, se 1. parametr symbolů chápe následovně:

{| class="wikitable"
|-
! Symboly !! Interpretace, kde 1. parametr má hodnotu ''X''
|-
| <tt>A</tt>-<tt>U</tt>,<tt>0</tt>-<tt>9</tt> || „nakresli úsečku ve směru natočení o délce ''X''“
|-
| <tt>a</tt>-<tt>u</tt> || „pohni se ve směru natočení bez kreslení o ''X''“
|-
| <tt>+</tt>, <tt>-</tt> || „otoč se doleva (resp. doprava) o ''X''“
|}

Pokud u výše uvedených symbolů není 1. parametr zadán, použije se výchozí hodnota (jako u D0L-systémů), pokud nejsou zadány ostatní parametry, mají ''nedefinovanou'' hodnotu (např. [[NaN]]). Příklady:

{| class="wikitable"
|-
! Zápis !! Interpretace
|-
| <tt>F(1, 2)</tt> || „nakresli úsečku ve směru natočení o délce 1“
|-
| <tt>+(80)</tt> || „otoč se doleva (resp. doprava) o 80°“
|-
| <tt>F</tt> resp. <tt>F()</tt> || „nakresli úsečku ve směru natočení o výchozí délce“
|-
| <tt>+(,0)</tt> || „otoč se doleva (resp. doprava) o výchozí úhel zadaný L-systémem“
|}

=== Příklady ===
[[Soubor:H-tree-rooted.svg|náhled|200px|10. iterace H-stromu s parametry R = 1/√2 a U = 90]]
Jako jednoduchý příklad parametrického L-systému poslouží [[fraktál]] jménem [[H-strom]]. Říká se mu tak proto, že pro vhodně zvolené hodnoty ''proměnných'' vypadá jako písmena ''H'' tvořená z písmen ''H'', tvořená z písmen ''H''…

{{L-systém
| nazev = H-strom
| abeceda = F H + - [ ]
| axiom = F(200)
| rrp0 = F(l) | rrr0 = H(l) [+F(l * ''R'')] [-F(l * ''R'')]
| uhel = ''U''
}}

''R'' a ''U'' jsou ''proměnné'' L-systému (nejsou to symboly abecedy, ani nemají nic společného s parametrickými L-systémy). Pro jejich různé hodnoty bude výsledek vypadat odlišně. Obvyklými hodnotami jsou ''R'' = 1/√2 a ''U'' = 90. Zajímavé je, že s těmito hodnotami tvoří H-strom [[Peanovy křivky#Plochu-vyplňující křivky|plochu-vyplňující]] L-systém (a je dokonce v kategorii ''[[Peanovy křivky#FASS křivky|FASS]]''). Mírně odlišný výsledek vznikne s hodnotami ''R'' = 0,69 a ''U'' = 85, na následujícím obrázku je jeho 10. iterace. Pro hodnoty proměnných ''R'' = 1/√2 a ''U'' = 45 vznikne [[Pythagorův strom]].

[[Soubor:H-tree-85.svg|H-strom s parametry R = 0,99 a U = 85]]

Praktičtější ukázkou parametrických L-systémů je následující předpis ze str. 123<ref name="abop" /> a jedná se o velmi jednoduchý L-systém modelující [[růst]] [[list]]u rostliny. Čím vyšší iterace, tím vyspělejší list. Tento předpis má i své nevýhody, růst se nikdy nezastaví a pro iterace větší než 20 není použitelný. Pro ovlivnění rychlosti růstu a jeho zastavení by se dal použít složitější předpis.

{{L-systém
| nazev = List rostliny
| abeceda = F S x y z [ ] { . }
| axiom = [&#124;S(''K''/2)] [x] [y]
| rrp0 = x | rrr0 = [+x{.].z.}
| rrp1 = y | rrr1 = [-y{.].z.}
| rrp2 = z | rrr2 = zF(''K'')
| rrp3 = S(len) | rrr3 = F(len) +(1) S(len)
| uhel = 10
}}
''pozn.: symboly <tt>x</tt>, <tt>y</tt>, <tt>z</tt> nedělají nic, symboly <tt>F</tt>, <tt>S</tt> kreslí úsečku, viz [[#Interpretace symbolů|interpretace symbolů]]''

''K'' je konstanta představující délku kroku. Je použita jen kvůli tomu, aby stonek (tvořený symboly <tt>S</tt>) nebyl příliš dlouhý (roste 2× pomaleji než list), může se zvolit např. 1. Na obrázku níže je 5. až 21. iterace L-systému listu.

[[Soubor:L-system-Leaf-grow.svg|500px|5. až 21. iterace L-systému modelující růst listu]]

=== Podmíněná přepisovací pravidla ===
Parametry symbolů se také dají použít k podmínění přepsání symbolu. K tomu slouží '''podmíněná přepisovací pravidla'''. Podmíněné přepisovací pravidlo je rozšířené běžné přepisovací pravidlo o podmínku. Přepisování pak probíhá tak, že se uvedená podmínka vyhodnotí, a když je pravdivá, přepisovací pravidlo se použije. Pokud pravdivá není, hledá se další vhodné přepisovací pravidlo. Pořadí ověřování přepisovacích pravidel musí být dáno (aby se zachoval determinismus), např. od dříve uvedených pravidel k později uvedeným. Pokud symbol není přepsán žádným přepisovacím pravidlem, platí pro něj [[Identita (matematika)|identita]] jako výchozí přepisovací pravidlo (je tedy zkopírován do další iterace).

[[Soubor:RoseLeaf-Lsystem.svg|náhled|200px|25. iterace L-systému modelující list růže]]
Ukázkou podmíněného přepisování je list [[růže]] ze str. 126.<ref name="abop" />

{{L-systém
| nazev = List růže
| abeceda = g x y [ ] { . }
| axiom = [{x(0,0).}] [{x(0,1).}
| rrp0 = x(t,d) | rrr0 = . g(5, 1.15, -1) . [+y(t) g(3, 1.19, t) .}] [+y(t) {.] x(t+1, d) | rrc0 = d = 0
| rrp1 = x(t,d) | rrr1 = . g(5, 1.15, -1) . [-y(t) g(3, 1.19, t) .}] [-y(t) {.] x(t+1, d) | rrc1 = d = 1
| rrp2 = y(t) | rrr2 = g(1.3, 1.25, -1) y(t-1) | rrc2 = t > 0
| rrp3 = g(s,r,t) | rrr3 = g(s*r, r, t – 1) | rrc3 = t > 1
| rrp4 = g(s,r,t) | rrr4 = g(s*r, r, -1) | rrc4 = t = -1
| uhel = 60
}}

== Stochastické L-systémy ==
[[Deterministický algoritmus|Deterministické]] L-systémy se vyznačují tím, že je jednoznačně definováno, jak vypadá ''n''-tá iterace a při opakovaném výpočtu je vždy stejná. Při modelování rostlin je však žádoucí, aby se na modelu promítl nějaký prvek náhody (stochastismu). Proto se používají '''[[Stochastický|stochastické]] L-systémy''' (''0L-systémy''), které v sobě mají určitý prvek [[Náhoda|náhody]], díky kterému je výsledek vždy trochu jiný. Pak se dá pomocí jednoho stochastického L-systému modelující např. strom vymodelovat celý les, který vypadá přirozeně, protože každý strom je trochu jiný.

=== Randomizace při interpretaci ===
Nejjednoduššího stochastismu se dosáhne randomizací („znáhodnění“) změny ''úhlu otočení'' a ''délky kroku''. Kvůli tomu není nutné zasahovat do přepisovacího systému, ten zůstane nezměněn. Změna se projeví až při interpretaci symbolů. Jako příklad je uveden [[Pythagorův strom]] s randomizací úhlu a délky kroku o ±30%.

{{L-systém
| nazev = Randomizovaný Pythagorův strom 1
| abeceda = F L + -
| axiom = F(50)
| rrp0 = F(t) | rrr0 = L(t) [+F(t / √2)] -F(t / √2)
| uhel = 45
| randKroku = 30
| randUhlu = 30
}}

Výsledek vykreslení bude díky stochastismu pokaždé trochu jiný, na následujícím obrázku je 9 interpretací 6. generace, uprostřed je L-systém bez randomizace.

[[Soubor:RandomizedPythagorasLsystem.svg|500px|9 interpretací 6. generace stochastického L-systému (uprostřed bez randomizace)]]

=== Náhodný výběr přepisovacího pravidla ===
Pokročilejšího stochastismu se u L-systémů dosahuje náhodným výběrem mezi více přepisovacími pravidly. Každé takové pravidlo má určitou váhu, která určuje, s jakou [[pravděpodobnost]]í se vybere. Tato váha je uvedena u každého pravidla, které je [[Náhoda|náhodné]]. Pravděpodobnost vybrání konkrétního pravidla je určena hodnotou váhy onoho pravidla vydělené součtem vah všech pravidel, které připadají v úvahu pro přepsání konkrétního symbolu. Pokud váhy nejsou uvedeny, ale jedná se o stochastický L-systém, všechna pravidla mají váhu (a pravděpodobnost vybrání) stejnou.

{{L-systém
| nazev = Randomizovaný Pythagorův strom 2
| abeceda = F L + -
| axiom = F(50)
| rrp0 = F(t) | rrr0 = L(t) [+F(t / √2)] -F(t / √2) | rry0 = 2
| rrp1 = F(t) | rrr1 = L(t) +F(t / √2) | rry1 = 1
| rrp2 = F(t) | rrr2 = L(t) -F(t / √2) | rry2 = 1
| uhel = 45
| randKroku = 30
| randUhlu = 30
}}
''pozn.: pravděpodobnostní váhy jsou uvedeny nad šipkami u přepisovacích pravidel''

8 různých výsledků je na obrázku níže (9. uprostřed bez stochastismu).

[[Soubor:PythagorasStochasticLsystem.svg|500px|9 interpretací 6. generace stochastického L-systému (uprostřed bez randomizace)]]

== Kontextové L-systémy ==
Kontextové L-systémy mohou obsahovat přepisovací pravidla, která specifikují, jaký musí být kontext přepisovaného symbolu, aby se pravidlo použilo. Kontextem se myslí symboly před a za přepisovaným symbolem. Tím se napodobuje mechanismus, kterým rostliny řídí svůj vývoj. Ty si dokáží vyměňovat [[informace]] mezi sousedícími [[buňka]]mi ve formě [[Živina|živin]] nebo [[hormon]]ů<ref name="abop" />. Kontextovým mechanismem se také dá simulovat napadení rostliny [[Parazitismus|parazitem]].
<ref>{{Citace monografie
| titul = L-systems: from the theory to visual models of plants
| jméno = Przemyslaw
| příjmení = Prusinkiewicz
| spoluautoři = a kol.
| počet stran = 32
| strany = 21–22
| vydavatel = CSIRO Publishing
| místo = Calgary, Alberta, Canada
| jazyk = anglicky
| url = http://algorithmicbotany.org/papers/l-sys.csiro96.html
| formát = PDF
}}</ref>

Kontextový L-systém je velice blízký [[Kontextová gramatika|kontextové gramatice]], tedy každý přepisovaný symbol má levý a pravý kontext, který je pro přepsání nutný. kontextové přepisovací pravidlo má následující zápis:

:<tt>lc</tt> < <tt>S</tt> > <tt>pc</tt> → <tt>nahrada</tt>, kde
* <tt>lc</tt> je levý kontext, tedy výčet symbolů, které musí být bezprostředně vlevo od přepisovaného symbolu <tt>S</tt>,
* <tt>S</tt> je přepisovaný symbol,
* <tt>pc</tt> je pravý kontext, tedy výčet symbolů, které musí být bezprostředně vpravo od přepisovaného symbolu <tt>S</tt>,
* <tt>nahrada</tt> jsou symboly, za které se <tt>S</tt> přepíše.

=== 1L-systémy ===
Označení ''1L-systém'' se používá pro kontextový L-systém, který má kontextová přepisovací pravidla buď s levým nebo s pravým kontextem (nikoli s oběma najednou). Tyto L-systémy mohou obsahovat i bezkontextová pravidla. Při vyhodnocování mají však přednost kontextová.

{{L-systém
| abeceda = a A
| axiom = Aaaaaa
| rrp0 = a | levýKontext0 = A | rrr0 = A
| rrp1 = A | rrr1 = a
}}

Výsledek bude po iteracích vypadat následovně:
:''i'' = 0 : <tt>Aaaaaa</tt>
:''i'' = 1 : <tt>aAaaaa</tt>
:''i'' = 2 : <tt>aaAaaa</tt>
:''i'' = 3 : <tt>aaaAaa</tt>
:''i'' = 4 : <tt>aaaaAa</tt> atd.

Této technice se říká ''propagace signálu'' a používá se pro modelování pokročilých modelů rostlin.<ref name="abop" />

=== 2L-systémy ===
''2L-systémy'' obsahují i kontextová přepisovací pravidla, která mají oba kontexty. Krom nich mohou obsahovat vše co ''1L-systémy''.

== L-systémy reagující na prostředí ==
Základní L-systém se dá také rozšířit o speciální symboly, které se použijí pro obousměrnou komunikaci s prostředím. Prostředí je obvykle nějaká [[datová struktura]], která je schopna odpovídat na dotazy typu „Jak moc je v tomto místě volno“ a dokáže přijímat příkazy typu „Na tomto místě je objekt velikosti ''x''“. Pak se pomocí těchto L-systému dá vymodelovat rostlina, která se vyvíjí lépe tam, kde má více „místa“ nebo kde je výživnější půda. Pokud v přírodě rostou dva stromy blízko sebe, budou mít více větví na straně odvrácené od sousedního stromu a naopak málo větví bude směřovat do koruny sousedního. Toto chování se dá popsat právě pomocí L-systémů s prostředím.
<ref>{{Citace monografie
| titul = Visual Models of Plants Interacting with Their Environment
| jméno = Radomir
| příjmení = Mech
| jméno2 = Przemyslaw
| příjmení2 = Prusinkiewicz
| jazyk = anglicky
| url = http://algorithmicbotany.org/papers/enviro.sig96.html
| formát = PDF
}}</ref>

== Aplikace generující L-systémy ==
=== Fractint ===
[[Fractint]]<ref>Domácí stránka freeware generátoru fraktálů Fractint: [http://www.fractint.org]</ref> je [[freeware]] generátor fraktálů pro [[DOS]] ([[Microsoft Windows|Windows]]) a [[Linux]]. Program podporuje pouze základní typ L-systémů (tj. D0L-systémy). Výstup programu je možné uložit do souborů [[BMP]] a [[GIF]]

=== Inkscape ===
[[Inkscape]] je [[Otevřený software|open source]] [[vektorový grafický editor]] používající [[Scalable Vector Graphics|SVG]] jako svůj nativní formát. Obsahuje skript pro generování základního typu L-systémů (tj. D0L-systémů). Jeho výhoda je však ta, že výsledek je vektorový a dá se s ním v programu dále pracovat.

=== Plugin pro Blender ===
[[Blender]] je [[Otevřený software|open-source]] program pro modelování a vykreslování [[3D]] [[počítačová grafika|počítačové grafiky]], do kterého se dá stáhnout [[plugin]]<ref>Domácí stránka pluginu pro generování L-systémů v Blenderu: [http://lsystem.liquidweb.co.nz/] {{Wayback|url=http://lsystem.liquidweb.co.nz/ |date=20110415080335 }}</ref>, který generuje rostliny pomocí L-systémů. Odlišností tohoto pluginu od ostatních programů je ta, že grafik nezadává předpis L-systému, ale pouze vizuálně nastavuje parametry výsledného modelu rostliny.

<!--
== Implementace ==
Následující [[Zdrojový kód|kód]] je jednoduchá [[implementace]] paralelního přepisování L-systému. Zajímavé na něm je to, že nemá 2 fáze, jak bylo popsáno v úvodu k interpretaci, ale prochází L-systém „do hloubky“. Symboly si ukládá na [[Zásobník (datová struktura)|zásobník]] a přepisuje tak dlouho symbol na vrcholu zásobníku, dokud není v dostatečné generaci (nebo už nelze přepsat). Pak jej interpretuje (uloží do výstupního řetězce). Je proto schopen vygenerovat i obrovské výstupy (kdyby se výstup neukládal do paměti, ale např. rovnou vykresloval do bitmapy). Ukázka je v [[Programovací jazyk|jazyce]] [[C Sharp|C#]].

<syntaxhighlight lang="csharp">
static string rewrite(string axiom, Dictionary<char, string> rewriteRules, int iterations) {
	const char genEnd = '\x00'; // speciální znak pro detekci konce generace v zásobníku
	StringBuilder result = new StringBuilder();	// pro výstup

	Stack<char> stack = new Stack<char>(axiom.Length * 4);
	stack.Push(genEnd); // pro snadné testování ukončující podmínky
	for (int i = axiom.Length - 1; i >= 0; i--)
		stack.Push(axiom[i]); // naplnění zásobníku axiomem (1. znak axiomu bude na vrcholu zás.)

	int generation = 0;	// počítadlo aktuální generace
	while (true) { // hlavní smyčka
		char symbol = stack.Pop();

		if (symbol == genEnd) {
			if (--generation < 0)
				break; // konec
			continue;
		}

		if (generation < iterations) {
			string replacment;
			if (rewriteRules.TryGetValue(symbol, out replacment)) { // symbol jde přepsat
				generation++;
				stack.Push(genEnd);	// pro detekci konce této generace
				for (int i = replacment.Length - 1; i >= 0; i--)
					stack.Push(replacment[i]);	// přepsání
				continue; // poračuji přepisování
			}
		}
		// symbol už nelze přepsat (ať už z důvodu toho že jsme došli do max. generace
		// nebo protože pro něj není přepisovací pravidlo ⇒ interpretace
		result.Append(symbol);	// místo interpretace uložím symbol na výstup
	}

	return result.ToString();
}
</syntaxhighlight>
-->

== Reference ==
<references />

== Související články ==
* [[Fraktál]]
* [[Formální gramatika]]
* [[Počítačová grafika]]

== Externí odkazy ==
* {{Commonscat}}
* Seriál o L-systémech na serveru root.cz: [http://www.root.cz/clanky/l-systemy-prirodni-objekty-i-umele-artefakty/ L-systémy: přírodní objekty i umělé artefakty]
* Část diplomové práce Pavla Tišnovského: [http://www.fit.vutbr.cz/~tisnovpa/publikace/diplomka/doc/node20.html L-systémy]{{Nedostupný zdroj}}
* {{en}} [http://algorithmicbotany.org/papers/ Algorithmic botany] – stránka [[Univerzita Calgary|Univerzity Calgary]] kde [[Przemyslaw Prusinkiewicz|Dr. Przemyslaw Prusinkiewicz]] spolu s jeho studenty a kolegy publikuje své práce
{{Autoritní data}}

[[Kategorie:Formální jazyky]]
[[Kategorie:Fraktály]]
[[Kategorie:Morfologie rostlin]]