Next: Závěrečné porovnání algoritmů pro
Up: Algortimus pro generování minima
Previous: Algortimus pro generování minima
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: 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