L-systém: Porovnání verzí

{{Dobrý článek}}

'''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

| strany = 301–308

| isbn = 1-58113-374-X

}}</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

| datum přístupu = 2012-03-01

| jazyk = anglicky

| titul = Musical L-systems

| vydavatel = Nepublikovaná magisterská práce, Institute of Sonology, Hague

** 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]]).

 

 

<ref>{{Citace monografie

| titul = Hairs, Textures, and Shades: Improving the Realism of Plant Models Generated with L-Systems

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

 

 

 

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

 

=== Vykreslování ve 2D ===

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ě).

 

| <tt>a</tt>-<tt>u</tt> || „Pohni se vpřed (bez kreslení).“ (délka pohybu je ''délka kroku'')

|-

|-

| <tt>+</tt>, <tt>-</tt> || „Otoč se doleva (resp. doprava) o předem stanovený úhel.“ (o ''úhel otočení'')

 

=== Vykreslování ve 3D ===

 

{| class="wikitable"

|-

! Symboly !! Interpretace

|-

|-

|-

|}

 

== Příklady L-systémů ==

=== Kochova vločka ===

Následující předpis vygeneruje část [[Kochova vločka|Kochovy vločky]].

 

''pozn.: výchozí poloha štětce (želvy) je vlevo dole a štětec je orientován vpravo''

 

 

:''i'' = 1: <tt>F+F--F+F</tt>

 

:''i'' = 2: <tt>F+F--F+F + F+F--F+F-- F+F--F+F + F+F--F+F</tt>

 

:''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>

 

=== Stromeček ===

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.

 

 

=== Ostrovy a jezera ===

 

{{L-systém

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.

 

 

=== Penroseovo dláždění ===

| rrp0 = M | rrr0 = O++{.P.----N.[-O.----M.}]++

| rrp1 = N | rrr1 = +{.O.--P.[---M.--N.}]+

| rrp3 = P | rrr3 = --{.O.++++M.[+P.++++N.}]--N

| uhel = 36

 

=== Gosperova křivka ===

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]].

 

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.

 

 

== Parametrické L-systémy ==

! Symboly !! Interpretace, kde 1. parametr má hodnotu ''X''

|-

|-

|-

|}

 

! Zápis !! Interpretace

|-

|-

|-

|-

|}

 

=== Příklady ===

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''…

 

}}

 

 

 

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.

''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.

 

 

=== 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).

 

Ukázkou podmíněného přepisování je list [[růže]] ze str. 126.<ref name="abop" />

 

| 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

| rrp4 = g(s,r,t) | rrr4 = g(s*r, r, -1) | rrc4 = t = -1

| uhel = 60

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.

 

 

=== Náhodný výběr přepisovacího pravidla ===

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

 

 

== Kontextové L-systémy ==

| spoluautoři = a kol.

| počet stran = 32

| vydavatel = CSIRO Publishing

| místo = Calgary, Alberta, Canada

 

=== Plugin pro Blender ===

 

<!--

== Implementace ==

 

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

return result.ToString();

}

-->

 

== Reference ==

 

== Související články ==

 

== Externí odkazy ==

* 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]

* {{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

 

[[Kategorie:Formální jazyky]]