Lekce 6 - IFS fraktály

V minulé lekci, Mandelbrotova a Juliova množina, jsme probrali Mandelbrotovu a Juliovu množinu, jejich popis a uvedli si zdrojový kód ke generování těchto známých fraktálů.

Na rozdíl fraktálů diskutovaných v předchozích dvou odděleních se nejedná o polynomické fraktály. Zatímco polynomické fraktály jsou definovány jednou rovnicí (pravidlem), IFS mohou vznikat na základě více pravidel. Přesto se jedná mnohdy o velice jednoduché útvary. Jejich konstrukce, která se provádí stochastickou cestou, se dá obecně popsat tak, že na nějaký počáteční bod aplikujeme transformační pravidla w₁,w₂, … w_ns určitou pravděpodobností. Součet pravděpodobností se rovná 1. Po jedné iteraci získáme nový počáteční bod či jejich soustavu a iterativně na nich aplikujeme onen soubor pravidel. Tento způsob se někdy nazývá chaotická hra. Pro dosažení kýženého výsledku musíme provést několik tisíc iterací, ale u některých fraktálů vidíme hrubý obrys výsledku už od prvních iterací. Příkladem může být Cantorovo mračno.

Cantorovo mračno (diskontinuum)

Jedná se patrně o nejjednodušší fraktál vůbec a asi pro vás nebude těžké uhádnout, že je to iterační funkční systém. Vychází z úsečky. Na ni iterativně aplikujeme jen jedno pravidlo - rozdělíme úsečku na tři části a vyjmeme tu prostřední.

Cantorovo mračno po několika iteracích

Díky Cantorovu mračnu prý B. Mandelbrot odstranil šum na telekomunikačních linkách firmy IBM. Tehdy patrně ještě netušil že D_H=log(2)/log­(3)=0.6309.

Sierpinského trojúhelník

Toto je pro změnu jakýsi reprezentant všech IFS fraktálů. Výchozí bod zde představuje trojúhelník (nejlépe rovnostranný či ramenný). Může se vytvářet několika způsoby, nejnázornější je následující:

Máme tedy trojúhelník a rozdělíme jej na 4 stejné části (podle středních příček). Prostřední části vyjmeme. Toto pravidlo aplikujeme na zbylé 3 trojúhelníky, pak na zbylých 9, 27, 81 (co přijde asi pak?). Výhoda této metody je jak už jsem uvedl v názornosti (už od začátku vidíme stále se zpřesňující torzo výsledku), ale bohužel se nejedná o chaotickou hru. Jak na ní? U trojúhelníku máme pochopitelně tři vrcholy ABC a ještě potřebujeme náhodně zvolený bod Z na obvodu trojúhelníka. Od tohoto bodu vedeme pomyslnou úsečku k náhodně zvolenému vrcholu. Úsečku nezakreslujeme, ale v jejím středu zakreslíme bod Z1. Od něho znovu vedeme úsečku k náhodnému vrcholu a opět zakreslíme jen její střed. Po několika tisících iteracích se nám začne z bodů skládat výsledek:

Sierpinského trojúhelník

Jeden můj kamarád vlastnící programovatelnou kalkulačku úspěšně implementoval chaotickou hru. Na tom není nic divného, ale podobný výsledek dostal i tehdy, když bod vykreslil na třetině, čtvrtině, pětině... úsečky. Podobný obrázek dostal dokonce i tehdy, když vykreslil bod úplně mimo úsečku (ale podle neměnných pravidel)! Počáteční bod nemusel dokonce ležet ani na obvodu trojúhelníka, mohl se nacházet úplně mimo! Pak se prvních pár bodů sice vykreslilo jinde, ale pak systém rychle konvergoval. Podobné experimenty dokazují, že ač je tento postup hrou na chaos, je neobyčejně stabilní, i když do něj kopeme kanadama. Dále se nabízí možnost aplikovat chaotickou hru na čtverec či n-úhelníky.

Mezi Pascalovým a Sierpinského trojúhelníkem si vnímavější jedinci povšimnou až znepokojující podobnosti:

D_H = log(3) / log(2) = 1.5850

Sierpinského kobereček

Sierpinsky se neomezil jenom na trojúhelník, ale experimentoval i s jinými útvary. V tomto případě se čtvercem. Způsob generování tohoto fraktálu je také velice jednoduchý. Jako počáteční bod si zvolíme čtverec. Na každé jeho straně vyznačíme jejich třetiny. Protilehlé body spojíme. Uprostřed původního čtverce tak vznikne nový čtverec - délka jeho strany se rovná třetině délky strany původního čtverce a nachází se uprostřed původní čtvercové plochy. Vyjmeme jej, zůstane nám tedy 8 těchto třetinových čtverců. Na ty aplikujeme stejné pravidlo.

Sierpinského kobereček, D_H= log(8) / log(3) = 1.8928

Kapradí

IFS fraktály se neomezují jen na jednoduché geometrické útvary. IFS fraktál můžete vytvořit prakticky z čeho chcete. Například z kapradí. Konečně se dostáváme k dvěma afinním transformacím. Jsou definovány jako parametrické rovnice:

• x_i + 1 = ax_i + by_i + e
• y_i + 1 = cx_i + dy_i + f

kde parametry a, b, c, d, e, f, p jsou definovány takto:

Parametr p určuje pravděpodobnost jednotlivých transformací.

Kapradí

Kochova vločka

Další dobře známý fraktál. Také vzniká pomocí velmi jednoduchých transformací. Počáteční bod tvoří rovnostranný trojúhelník. Doprostřed každé stany přidáme další rovnostranný trojúhelník a tak pořád dokola. Výsledek vidíte na obrázku:

Kochova vločka

Závěr

IFS fraktály jsou velice user-friendly skupinou fraktálů. Lehce se generují (samozřejmě existují i složité IFS), dobře vypadají a každý si může vymyslet ten svůj. V tomto textu jsou uvedeny čtyři druhy, ale lepší by bylo říci čtyři třídy fraktálů. Na většinu útvarů lze vymyslet nějakou tu afinní transformaci. Těžko ale vytvoříte IFS na základě kruhu. Jediná možnost je iterativně zmenšovat kruh, ale tím fraktál neuděláte. Z kruhu těžko vytvoříte kopie jeho samého. Dalším takovýmto nevděčným objektem jsou křivky (např. sinusoida). Tam ale toto tvrzení neplatí zcela a u některých křivek "bez rovných ploch" se vám může podařit vymyslet a aplikovat nějakou tu transformaci byť třeba složitou a nemusí být sama. Také většinu fraktálů, např. přírodních objektů, nepůjde použít jako výchozí bod pro IFS. I když výjimka potvrzuje pravidlo (a v matematice vyvrací). Nejjednodušší IFS vznikají z n (1 až nekonečno) rozměrných geometrických útvarů. Takže sedněte ke kompu, vemte nadkrychli a vytvořte IFS (nadkrychle-4D objekt s krychlovou základnou).

V další lekci, IFS fraktály, jsme si probrali teorii a vykreslili si IFS fraktály spolu s popisem algoritmu, tabulkou hodnot pro různé fraktály a zdrojovým kódem.