Prírodou inšpirované algoritmy

Príklady

Kochova vločka - príklad fraktálu

Skôr než pristúpime k príkladom generovania fiktívnych rastlín, je vhodné objasniť niektoré kľúčové pojmy, uvedené už v úvode podkapitoly o L-systémoch. Fraktálom nazval matematik Benoit Mandelbrot geometrický útvar s týmito vlastnosťami :

• je sebepodobný,
• má neceločíselnú dimenziu,
• má síce na pohľad veľmi zložitý tvar, je ale generovaný jednoduchými pravidlami.

Sebapodobnosťou sa rozumie to, že nech daný útvar pozorujeme v akomkoľvek merítku, vykazuje stále rovnaký charakteristický tvar. Dimenzia D je v tomto prípade definovaná ako N = LD, kde N je počet kópií pôvodného útvaru pri L-násobnom zväčšení lineárneho rozmeru, napr. štvorec má dimenziu 2 ( 4 = 22 ) a kocka dimenziu 3 ( 8 = 23 ).

Medzi najznámejšie fraktály patrí krivka - tzv. Kochova vločka, navrhnutá H. Kochom: každá úsečka je nahradená lomenou čiarou, ktorá vznikne zámenou prostrednej tretiny pôvodnej úsečky dvomi stranami rovnoramenného trojuholníka :

Axiom = F--F--F ( rovnoramenný trojuholník )
α = 60°
F → F+F--F+F

V náhradnej lomenej čiare sa pôvodná úsečka F vyskytuje štyrikrát, lineárne zväčšenie je trojnásobné, teda platí 4 = 3D a dimenzia Kochovej vločky je D = 1.2618. Obvod vločky konverguje k nekonečnu (O = 3 * 4/3 * 4/3 * 4/3 * 4/3 ... ), ale jej ohraničená plocha má konečný obsah, menší ako obsah kružnice, opísanej pôvodnému trojuholníku.

Sierpinského trojuholník

vznikne odstránením stredného trojuholníku s vrcholmi v stredoch hrán pôvodného trojuholníka. V ďalších iteráciách sa odstraňujú analogicky stredy zostávajúcich trojuholníkov. Nasledujúci applet umožňuje sledovať axiómu a prvé štyri iteračné kroky. Konštrukciu možno chápať tiež ako pripojenie dvoch ďalších rovnoramenných trojuholníkov k dvom vrcholom pôvodného a následné dvojnásobné zmenšenie. Platí teda (ešte pred zmenšením) 3 = 2D a D = 1.5849625. Obsah neodstránenej plochy konverguje k nule a jej obvod konverguje k nekonečnu.

Tento fraktál sa môže generovať i pomocou 1D CA (1-rozmerný celulárny automat).

Nasledujúci applet umožňuje sledovať axiómu a prvé štyri iteračné kroky. X je pomocný, tzv. negrafický symbol, ktorý korytnačia grafika jednoducho ignoruje. Jeho náhradou sa vytvárajú v ďalších iteráciách vpísané menšie trojuholníky.

Applet sa ovláda tlačidlami

• +1 - ďalší iteračný krok
• -1 - predošlý iteračný krok
• 0 - axióm
• Generuj - vygeneruje reťazec pre i-tý iteračný krok a vykreslí jeho grafickú interpretáciu (i sa zadáva v okne Iterácia).

Použitie zásobníka pri generovaní rastlín

Doterajšie krivky bolo možné nakresliť jediným ťahom (neprerušovaným pohybom korytnačky). Pre štruktúru rastlín sú ale typické vetvenia, t.j. korytnačka sa musí vrátiť po nakreslení jednej vetvy bez kreslenia čiary. Pre takýto pohyb "naprázdno" býva definovaný symbol f. Vetvenia rastlín majú ale obyčajne rekurzívny charakter a pre tento účel je viac vhodné použiť zásobník. Do neho sa v mieste vetvenia uložia parametre korytnačky (smer, prípadne ďalšie údaje : farba, hrúbka čiary...) a z neho sa potom vyberú po nakreslení prvej vetvy a použijú sa pre začiatok kreslenia vetvy druhej. Obvykle sa pre operáciu vkladania a výberu používajú otváracia a zatváracia hranatá zátvorka.

Jednoduché "krovie" je možné generovať napríklad L-systémom :

Applet sa ovláda rovnako ako predošlý. Rozdiel je v tom že, L-systém je editovateľný (možno meniť napríklad uhol, pridať, resp ubrať úsek v jednej z vetví, ...). Tlačidlom Reset sa obnoví pôvodný L-systém.