L-systémy: přírodní objekty i umělé artefakty

Obsah

1. Úvodní informace o L-systémech
2. Gramatiky a přepisovací pravidla
3. Úprava gramatik pro L-systémy
4. Želví grafika
5. Nejznámější fraktální útvary vzniklé pomocí L-systémů
6. Cantorova množina
7. Křivka Helge von Kocha
8. Sněhová vločka Helge von Kocha
9. Obsah dalšího pokračování tohoto seriálu

1. Úvodní informace o L-systémech

L-systémy, v minulosti též známé pod názvem Lindenmayerovy systémy, jsou skupinou fraktálů definovaných ve své nejjednodušší podobě pomocí regulárních nebo bezkontextových přepisovacích gramatik. Název této skupiny fraktálů, na jejichž výzkumu má největší podíl Aristid Lindenmayer a Przemyslaw Prusinkiewicz, pochází ze zkráceniny anglického sousloví LOGO-like turtle. LOGO je velmi zajímavý programovací jazyk vycházející z funkcionálního programovacího jazyka LISP (syntaxe je však „přezávorkovanému“ LISPu vzdálená), ve kterém se, kromě snadného zpracování datových struktur, dají s využitím jednoduchých příkazů pomocí takzvané želvy kreslit různé obrazce složené z úseček. S tímto zajímavým a ve světě oblíbeným programovacím jazykem se ostatně na Rootu ještě podrobněji seznámíme v samostatném výukovém seriálu.

Podstatou tvorby těch nejjednodušších a nejpoužívanějších L-systémů je přepisování řetězců podle určitých pravidel, která jsou buď předem zadaná množinou přepisovacích pravidel (gramatiky), nebo se mění v průběhu generování fraktálního obrazce, například na základě zpětné vazby či na podněty okolního prostředí (gravitace, dopadající světlo apod.) Přepisování některých symbolů řetězce je většinou pevně dané, ale může být také určeno na základě generátoru náhodných čísel (stochastické L-systémy). Každý symbol v řetězci má přiřazen jistý geometrický význam, například transformaci či generování/na­kreslení objektu. V případě použití želví grafiky se jedná o příkazy pro posun a natočení želvy.

Zajímavé obrazce se začnou tvořit, jestliže v programu určeném pro LOGO použijeme iteraci, resp. rekurzi, což odpovídá iteraci v gramatice, tj. stavu, kdy na pravé straně přepisovacího pravidla je nonterminální symbol shodný se symbolem na levé straně téhož pravidla (o terminálních a nonterminálních symbolech bude řeč ve druhé kapitole). S pomocí L-systémů lze generovat fraktální objekty, které se podobají rostlinám, stromům a dalším přírodním útvarům. Poslední aplikace také směřují k využití těchto fraktálů při generování 3D modelů technologických artefaktů a dokonce i textur.

Z toho, jak se fraktál pomocí L-systémů generuje, je zřejmé, že se jedná o deterministický postup (pokud se při aplikaci přepisovacích pravidel nepoužije generátor náhodných čísel) a výsledný fraktál je tedy též deterministický. Těmto velmi pravidelným a mnohdy i symetrickým fraktálům se také někdy říká graftály. V dalších kapitolách se budeme zabývat právě deterministickými L-systémy, stochastickým systémům se budeme věnovat v některém z dalších částí tohoto seriálu.

Obrázek 1: Ukázka L-systému vytvořeného v ploše

2. Gramatiky a přepisovací pravidla

Naše povídání o L-systémech by nebylo úplné, pokud bychom si alespoň stručně nepopsali význam gramatik, přepisovacích pravidel a terminálních i nonterminálních symbolů. Gramatiky mají v teoretické informatice velký význam, zejména při studiu umělých jazyků (například programovacích). Gramatiku je možné popsat uspořádanou čtveřicí:

G=[N,Σ,P,S]

kde:

• N je konečná abeceda nonterminálních symbolů
• Σ je konečná abeceda terminálních symbolů
• P je konečná množina přepisovacích pravidel tvaru A → B
• S je axiom: neprázdná posloupnost symbolů S _Є (N u Σ)⁺

Přepisovací pravidla jsou tvaru S→aBC, B→XY, C→a, C→D (dokonce i XYZ=DB), kde velkými písmeny jsou označeny nonterminální symboly, písmeny malými zase symboly terminální (ty se již dále nerozepisují). Podle tvaru přepisovacích pravidel rozlišujeme gramatiky regulární, bezkontextové, kontextové a obecné (Chomského hierarchie). Regulární gramatiky jsou z této skupiny nejjednodušší (popisují množinu nejméně „složitých“ jazyků), avšak velmi často používané, protože jazyky z této množiny lze snadno popsat i rozpoznat, například velmi oblíbeným regulárním výrazem. L-systémy jsou většinou popsány právě regulárními gramatikami, i když poněkud upravenými, což si blíže popíšeme v následující kapitole.

Obrázek 2: L-systém zde posloužil pro tvorbu trojrozměrného mo­delu

3. Úprava gramatik pro deterministické L-systémy

V L-systémech je použita zjednodušená forma gramatik, ve kterých splývají terminální a nonterminální symboly. Deterministický bezkontextový L-systém je tvořen uspořádanou trojicí:

G=[V,P,S]

kde:

• V je konečná abeceda symbolů (zde nerozlišujeme symboly terminální a nonterminální)
• P je konečná množina pravidel tvaru A → B; A_ЄV; B_ЄV^*
• S je axiom: neprázdná posloupnost symbolů S _Є V⁺

Jak již bylo řečeno v předchozích odstavcích, u L-systémů se dělení na terminální a nonterminální symboly většinou formálně nezavádí, zejména proto, že počet derivací (přepisů) je libovolný a po proběhnutí zadaného počtu derivací se původně nonterminální symboly změní na symboly terminální, tj. symboly interpretovatelné želvou (viz další odstavce zabývající se želví grafikou). Determinismus tohoto L-systému pramení z podmínky, že v množině P nesmějí existovat dvě pravidla se stejnou levou stranou. Při přepisování tedy vždy přesně víme, které pravidlo pro přepis vybrat. Existují i další třídy gramatik, jejichž zpracování je však složitější, proto se při práci s L-systémy tyto gramatiky nepoužívají a místo nich se aplikují jiné (méně „vědecké“) metody; například se jedná o parametrizo­vatelné L-systémy, jejichž přepis do gramatik (přepisovacích pravidel) je sice teoreticky možný, ale v praxi těžko realizovatelný (byly by použity kontextové gramatiky).

Derivace (označovaná také matematickým symbolem →) řetězce A_ЄV^* znamená paralelní přepsání všech symbolů X_ЄA řetězce V z pravé strany pravidel z množiny P.

Například první dvě derivace L-systému G:

G=[{A,F,–,+}, {A → F – – F – – F,F → F + F – – F + F,+ → +,– → -},A]

se startovním symbolem A mají podobu:

A → F – – F – – F → F + F – – F + F – – F + F – – F + F – – F + F – – F + F

(mezery mezi symboly jsou uvedeny pouze pro přehlednost, ve skutečnosti se ve výsledném řetězci nevyskytují) Poslední uvedená posloupnost symbolů získaná v poslední derivaci se ve druhém kroku geometricky interpretuje. K tomu se používá takzvaná želví grafika (turtle graphics), ve které želva reprezentuje pomyslné kreslící zařízení, pomocí kterého se vytváří obrazce složené z úseček.

Obrázek 3: Další trojrozměrný model vytvořený pomocí L-systémů

4. Želví grafika

Takzvaná želví grafika (turtle graphics) tvoří základní nástroj použitý při vytváření deterministických L-systémů, jedná se i o nedílnou součást programovacího jazyka LOGO. Nyní si řekneme základní informace o želví grafice. Základem je takzvaná želva, která je definována svým stavem a tabulkou akcí, které může provádět – z hlediska OOP se tedy jedná o klasicky pojatý objekt, kde stavu želvy odpovídá obsah datových složek objektu a tabulka akcí odpovídá metodám, kterými se mění datové složky a provádí další činnosti.

Stav želvy se skládá ze dvou prvků: z polohy želvy a z její orientace. Želva čte sekvenčně zadaný řetězec (získaný v případě L-systémů několikerým přepsáním startovacího symbolu S) a pomocí tabulky akcí interpretuje jednotlivé symboly jako příkazy. Pro úplné zadání tedy musíme přiřadit každému symbolu jeho význam. Nejjednodušší forma L-systému interpretovaného želvou v ploše může používat následující symboly:

V následujících pokračováních tohoto seriálu si ukážeme, jak je možné výše zmíněnou tabulku rozšířit o další smysluplné symboly, které mohou sloužit například pro zapamatování pozice a orientace želvy, změnu barvy či šířky kreslené čáry atd. Také přechod z plochy do prostoru musí být řešen rozšířením této tabulky o několik symbolů. Prozatím si však vystačíme s výše uvedenou pěticí symbolů.

Želva se nachází na kreslicí ploše a pomocí výše uvedených symbolů (příkazů) se může otáčet okolo své osy doprava a doleva, přesouvat se dopředu bez kreslení nebo se přesouvat dopředu i dozadu spolu s kreslením, tj. mezi počáteční a koncovou pozicí želvy je nakreslena úsečka (želva se vždy pohybuje ve směru či proti směru své orientace). Vhodnou kombinací všech příkazů je možné vykreslovat i zdánlivě kulaté tvary (posun o malý krok spolu s nepatrným natočením), což je ukázáno na dalším obrázku. Za povšimnutí stojí, že želva pro svůj posun nepotřebuje znát svoji absolutní polohu, je tedy nezávislá na souřadném systému.

Obrázek 4: Screenshot grafického okna interpreteru LOGA – UCB Logo (želva je po vytvoření screenshotu zvýrazněna červenou barvou)

5. Nejznámější fraktální útvary vzniklé pomocí L-systémů

Pomocí L-systémů je možné jednoduše popsat mnoho známých fraktálních tvarů a objektů. V dalších podkapitolách jsou slovně i pomocí obrázků představeny fraktály, které měly po svém zveřejnění velký význam na vzniku a chápání fraktální geometrie jako samostatné vědní disciplíny. V dobách, kdy byly tyto tvary objeveny, je mnoho i velmi vzdělaných lidí považovalo za matematická monstra a odmítalo se jimi dále teoreticky i prakticky zabývat. Že se ze strany těchto lidí jednalo o velký omyl, se ukázalo až na začátku osmdesátých let minulého století s prudkým rozvojem fraktální geometrie – ony „monstrózní“ tvary totiž představovaly zjednodušené a minimalistické topologické podoby složitých přírodních útvarů a fyzikálních jevů.

6. Cantorova množina

Cantorova množina je pojmenována po matematikovi ruského původu, jehož celé jméno zní Georg Ferdinand Ludwig Philipp Cantor. Tento pravděpodobně nejjednodušší fraktál může být iterativně zkonstruován následujícím způsobem:

1. Konstrukce začíná s úsečkou, která má jednotkovou délku. Tato úsečka se většinou kreslí ve vodorovné poloze, na konstrukci fraktálu však nemá orientace úsečky žádný vliv.
2. Úsečka se rozdělí na tři stejně dlouhé části. Prostřední část (třetina) se vyjme, takže nám ve druhé iteraci vzniknou dvě úsečky, z nichž každá má třetinovou délku oproti úsečce původní.
3. Rozdělování úseček a odstraňování jejich prostředních částí pokračuje iterativně dále a v limitě, tj. po provedení nekonečně mnoha iterací, získáme množinu bodů (úseček s nulovou délkou), které nejsou navzájem propojeny, protože mezi každou dvojicí sousedních bodů se nachází „díra“ (také s nulovou délkou) vzniklá postupným vyjímáním prostřední třetiny úseček.
4. Po provedení předchozích třech bodů dostaneme fraktální obrazec, který však tvoří pouze část celé Cantorovy množiny. Aby vznikl skutečný fraktál, musíme vytvořený obrazec vzít a nekonečněkrát ho zkopírovat na přímce odpovídající orientaci původní úsečky. Vzdálenost mezi sousedními kopiemi obrazce je rovna dvěma, přičemž původní úsečka je jednotková. Tento krok je pro zachování symetrie měřítka nutný (jak na to upozornil již před cca 25 lety B. Mandelbrot), i když na něj v některé literatuře není myšleno.

Cantorovu množinu je možné popsat pomocí následující gramatiky G_Cantor:

G_Cantor=[V,P,S]
V={F,G}
P={F→FGF, G→GGG}
 S=F

Význam Cantorovy množiny

Cantorova množina je významná hned ze tří hledisek:

1. Z historického hlediska je důležité, že Cantor s pomocí své množiny (a také Cantorovy funkce) upozornil na některé do té doby ignorované aspekty algebry a geometrie. Přibližně ve stejné době prezentoval Weierstrass svoji slavnou funkci, která je sice spojitá, ale nediferencovatelná. Obě práce měly významný vliv na další vývoj matematiky a fyziky, která se v období kolem roku 1870 nacházela v krizi, která vyústila v celkovou změnu myšlení.
2. Současně se jedná o nejjednodušší fraktální objekt, na kterém se snadno vysvětlují základní pojmy fraktální geometrie, zejména význam soběpodobnosti a nezávislosti na změně měřítka (prakticky nic jednoduššího než množinu bodů ležících na úsečce není možné vymyslet). I výpočet fraktální dimenze Cantorovy množiny je poměrně jednoduchý. Také konstrukce Cantorovy množiny – alespoň pro prvních několik iterací – nevyžaduje prakticky žádné složité pomůcky, pouze pravítko a tužku. To neplatí například u Mandelbrotovy množiny, na jejíž výpočet je počítač nutností.
3. Cantorovu množinu můžeme nalézt v mnoha složitějších dynamických systémech s fraktální charakteristikou. Například při vertikálním řezu bifurkačního diagramu (viz úvodní části tohoto seriálu) získáme Cantorovu množinu. Totéž platí pro řez nespojitou Juliovou množinou atd. V některých případech, včetně předchozích částí tohoto seriálu, se místo s termínem Cantorova množina setkáme s Cantorovým prachem (Cantor dust).

Obrázek 5: Způsob vzniku Cantorovy množiny

Cantorova množina ve VIMu

Pro vytvoření obrázku Cantorovy množiny není zapotřebí tvořit složitý program, postačí nám pouze textový editor nabízející funkci „Hledej a nahraď“. V této podkapitole ukážu konstrukci Cantorovy množiny v textovém editoru VIM, je však možné použít i jiný libovolný (tj. horší :-) textový editor. Cantorovu množinu budeme vykreslovat pomocí podtržítka, tj. znaku _. Vytvoříme tedy textový soubor s jediným řádkem:

_

Poté budeme aplikovat výše uvedená přepisovací pravidla F→FGF, G→GGG a to tak, že příkaz F značí kreslení úsečky, tj. v textovém editoru podtržítka a příkaz G posun o jednu pozici doprava, tj. bez vykreslení úsečky. Pravidla se tedy ve VIMu převedou na dvojici nahrazovacích příkazů:

:s/ /   /g
:s/_/_ _/g

Po několikerém opakování výše uvedené dvojice příkazů začíná v textovém editoru vznikat obraz Cantorovy množiny tak, jak ukazují následující řádky (v editoru je však vždy zobrazen a nahrazován pouze jeden řádek, není však problém vytvořit jeho kopii pomocí příkazů yyp):

(1 iterace): _
(2 iterace): _ _
(3 iterace): _ _   _ _
(4 iterace): _ _   _ _         _ _   _ _
(5 iterace): _ _   _ _         _ _   _ _                           _ _   _ _         _ _   _ _

7. Křivka Helge von Kocha

Velmi známým fraktálem konstruovaným pomocí L-systémů, je křivka a sněhová vločka Helge von Kocha. Popišme si nejdříve křivku Helge von Kocha, sněhová vločka vzniká pouhou změnou počátečních podmínek. Vytváření křivky Helge von Kocha spočívá v provedení následujících kro­ků:

1. Nejprve se, podobně jako v případě Cantorovy množiny, vykreslí úsečka s jednotkovou délkou.
2. Ve druhém kroku se úsečka rozdělí na třetiny, a to opět stejným způsobem jako v případě Cantorovy množiny. Prostřední třetina se vyjme a na jejím místě se sestrojí dvě ramena rovnoramenného trojúhelníku. Vznikne tedy obrazec, který se skládá z lomené úsečky (polyčáry), jejíž délka je rovna 4/3 délky původní úsečky, tj. celková délka se o třetinu prodlouží.
3. Na vzniklý obrazec se opakovaně aplikuje pravidlo uvedené v předchozím bodě, tj. každá úsečka je rozdělena na třetiny, prostřední třetina se vyjme a nahradí se dvojicí ramen rovnoramenného trojúhelníka.

Obrázek 6: První iterace křivky Helge von Kocha

Obrázek 7: Druhá iterace křivky Helge von Kocha

Obrázek 8: Třetí iterace křivky Helge von Kocha

Obrázek 9: Čtvrtá iterace křivky Helge von Kocha

Obrázek 10: Pátá iterace křivky Helge von Kocha

Při trojnásobném zjemnění se délka křivky Helge von Kocha zvětší čtyřikrát, proto Hausdorffova (fraktální) dimenze není celočíselná. Pro N=4 se tedy měřítko musí zmenšit na třetinu:

s=1/3
N=4

Hausdorffova dimenze křivky Helge von Kocha se vypočítá jako:

D=log N/log (1/s)=log 4/log 3=1,2618595

Křivka Helge von Kocha má i další zajímavé matematické a geometrické vlastnosti. Mezi ně patří to, že sice je v celém svém rozsahu spojitá, ale v žádném bodě nemá derivaci. Každý bod na křivce je totiž po nekonečně mnoha transformacích průnikem dvou nekonečně malých úseček, které tvoří strany trojúhelníka, který je taktéž nekonečně malý. Tato křivka je také nekonečně dlouhá, i když zabírá konečný (z obou stran omezený) prostor, jak je ostatně patrné z obrázků.

Křivku Helge von Kocha je možné popsat pomocí následující gramatiky G_KochCurve:

G_KochCurve=[V,P,S]
V={F,+,–}
P={F→F=F+F–F+F}
 S=F

přičemž úhel otáčení želvy je nastaven na 60°

8. Sněhová vločka Helge von Kocha

Sněhová vločka Helge von Kocha je vytvořena pomocí gramatiky G_KochFlake, ve které je změněna pouze počáteční podmínka, tj. v první iteraci se nevykreslí pouhá úsečka, ale trojúhelník:

G_KochFlake=[V,P,S]
V={F,+,–}
P={F→F=F+F–F+F}
S=F–F–F

Obrázek 11: První iterace sněhové vločky Helge von Kocha

Obrázek 12: Druhá iterace sněhové vločky Helge von Kocha

Obrázek 13: Třetí iterace sněhové vločky Helge von Kocha

Obrázek 14: Čtvrtá iterace sněhové vločky Helge von Kocha

Obrázek 15: Pátá iterace sněhové vločky Helge von Kocha

9. Obsah dalšího pokračování tohoto seriálu

V následujícím pokračování tohoto seriálu si kromě dalších známých fraktálních útvarů vytvořených pomocí L-systémů ukážeme, jakým způsobem je možné po zavedení dvou terminálních symbolů (jedná se o symboly zapisované většinou pomocí znaků „[“ a „]“) generovat tvary, které obsahují větvení. V literatuře se L-systémy rozšířené o tyto terminální symboly nazývají závorkové L-systémy (bracketed L-systems). Typickým objektem, který je možné tímto způsobem vytvořit, je keř či strom. Dále si popíšeme význam dalších terminálních symbolů určených pro změnu délky, šířky popř. barvy generované úsečky. Samozřejmě nezapomeneme ani na demonstrační příklady.