next up previous contents
Next: Závěrečné porovnání algoritmů pro Up: Algortimus pro generování minima Previous: Algortimus pro generování minima

Zápis algoritmu pro generování minima pixelů v IFS fraktálu

Zápis tohoto algoritmu bude proveden v pseudokódu, který je podobný programovacímu jazyku Pascal:

1. najdi pevné body pro všechny transformace
wk
2. vykresli pixely, které korespondují s těmito body
3. proveď inicializaci fronty s pomocí adres těchto pixelů
4. repeat
5. vezmi adresu pixelu ze začátku fronty
6. for k=1 to N do
7. proveď transformaci
wk(p)
8. tento bod zaokrouhli tak, aby korespondoval s jedním pixelem
9. if bod nebyl nikdy vykreslen then
10.vykresli tento bod
11.přidej adresu tohoto bodu na konec fronty
12.end if
13.end for k
14.until fronta není prázdná
15.end.
Velkou výhodou tohoto algoritmu je, že se každý pixel na obrazovce vykreslí pouze jednou. Také se dosáhlo toho, že pro jednou počítaný bod se nebudou provádět žádné další transformace. Z výše uvedeného vyplývá, že algoritmus v konečné době skončí, neboť i v nejhorším případě se provede vygenerování pouze všech pixelů na obrazovce. Má-li tedy obrazovka rozlišení 800x600 pixelů, provede se maximálně 800*600=480000 iterací. Proto je tento algoritmus nejefektivnější, to znamená, že generuje výsledný fraktál s minimálním počtem bodů. Také paměťové nároky nejsou velké. Vedle bitmapy potřebujeme navíc pouze frontu s adresami pixelů. Jedno místo ve frontě bude mít velikost 4 byte, což není mnoho. První nevýhodou tohoto algoritmu je nutnost pro každý počítaný pixel hledat jeho protějšek ve frontě. To zapříčiní zkomplikování výpočtů a tím i prodloužení celkové doby generování celého fraktálu. Druhou nevýhodou je, že tento algoritmus je určen pouze pro generování celého fraktálu. Chceme-li generovat pouze výřez z fraktálu, stává se tento algoritmus neefektivní, protože bude počítat i body ležící mimo obrazovku. Tuto nevýhodu má i deterministický algoritmus, kde také není možné efektivně generovat výřez z fraktálu.
next up previous contents
Next: Závěrečné porovnání algoritmů pro Up: Algortimus pro generování minima Previous: Algortimus pro generování minima
Tisnovsky Pavel
1999-05-30