GrafikaGyakorloFraktalok

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Mintakérdések a Számítógépes grafika és képfeldolgozás tárgy vizsgájára való felkészüléshez

Fraktálok

Mottó:

_"A brokkoli egészségesebb, mint a karfiol, mert több benne a dimenzió!"_

76. Mennyi a következő IFS attraktorának Hausdorff dimenziója:

$\left[{\begin{array}{lll}0.5&0\\0&0.5\\0&0\end{array}}\right]\left[{\begin{array}{lll}0.5&0\\0&0.5\\0&0.5\end{array}}\right]\left[{\begin{array}{lll}0.5&0\\0&0.5\\0.5&0\end{array}}\right]\left[{\begin{array}{lll}0.5&0\\0&0.5\\0.5&0.5\end{array}}\right]$

Feltételezheti, hogy az IFS-t gyártó diszkjunkt halmazokat használt a kollázs során. Adjon meg két pontot, amely biztosan része az attraktornak (indokolja a választást). Megjegyzés: nem sikerült LaTeX-kel megoldanom, hogy úgy jelenjen meg, mint az eredeti feladatsorban. A felső 2x2-es, és az alsó 1x2-es részek külön be voltak keretezve az egyes mátrixokban, mert a felső rész jelenti a mátrixot, amivel szorozzuk a vektorokat, az alsó pedig a vektort, amit hozzájuk adunk.

• Ha az ember kísérletezik kicsit a transzformációkkal, gyorsan "meg lehet sejteni", hogy a halmaz képe egy négyzet lesz, és a dimenziója 2. Ha nem, akkor csak azt kell észrevenni, hogy 4 darab transzformációnk van, amik felére zsugorítanak minden koordináta mentén (a transzformációk felső 2x2-es része az egységmátrix 0.5-szöröse). Ha d dimenziós lenne az alakzat, akkor ez $0.5^{d}$-szeresére változtatná a "területét". Viszont, mivel 4 ilyenből kirakható az egész, ezért egy ilyennek a "területe" pont a 0.25-szöröse kell legyen az egészének, tehát $0.5^{d}=0.25$, azaz d=2.
• Az egyes transzformációk fixpontjai az összetettnek is fixpontjai lesznek (vagyis elemei az alakzatnak). Az elsőé pl. a (0, 0) pont, az utolsóé az (1, 1). Az egyes transzformációk fixpontjai úgy kaphatók meg, hogy fel kell írni egy vektoregyenletet, pl. a második transzformációnál: $\left[{\begin{array}{ll}x&y\end{array}}\right]\left[{\begin{array}{ll}0.5&0\\0&0.5\end{array}}\right]+\left[{\begin{array}{ll}0&0.5\end{array}}\right]=\left[{\begin{array}{ll}x&y\end{array}}\right]$
• Wikipédia: IFS
• Wikipédia: Hausdorff dimenzió
• Wikipédia: néhány fraktál Hausdorff dimenziója

135. Írjon programot, amely egy IFS-t megjelenít.

• Az IFS-eket elvileg úgy lehetne megjeleníteni, hogy kiindulunk egy ponthalmazból, és erre ismételgetjük a transzformációkat, majd néhány iteráció után az eredményt megjelenítjük. Ha a pontok koordinátáinak listáját tárolnánk minden lépés után, akkor ennek nagyon nagy (iterációnként exponenciálisan növekvő) memóriaigénye lenne, ha pedig egy képet tárolnánk, amin be vannak jelölve azok a pontok, ahova az adott iterációban került pont, az pontatlan lenne.
• Egy jobban alkalmazható módszer: induljunk ki egy pontból, ami biztosan része az alakzatnak (pl. az egyik transzformáció fixpontjából). Minden lépésben az új pont legyen a réginek a transzformáltja, azt pedig, hogy melyik transzformációt alkalmazzuk rá, válasszuk ki véletlenszerűen. Belátható, hogy az így előállított pontsorozat közel egyenletesen le fogja fedni a fraktált.
• A függvény kap egy transzformáció-tömböt, egy képet, amire rajzolni fog, meg hogy hány iterációt végezzen. Minden lépésben választ egy transzformációt, alkalmazza az aktuális pontra, majd a kép megfelelő helyén növeli a pixel fényességét. Így azok a pixelek, amiken belül "sűrűbb" a fraktál, fényesebbek lesznek.

void ifs(const Array<Transform>& trans, Image& img, unsigned int iter) {
  Vector current=trans[0].fixpoint();
  for (unsigned int i=0; i<iter; i++) {
	 current=current.transform(trans[rand()%trans.size()]);
	 img.pixel(current.x, current.y)+=0.01;
  }
}

136. Mi a Mandelbrot halmaz? Hogyan dönthető el, hogy egy pont a halmazhoz tartozik-e vagy sem?

• A Mandelbrot-halmaz a komplex számok egy részhalmaza. Azon c komplex számok tartoznak bele, amikre a következő sorozat nem "száll el" a végtelenbe: $z_{0}=0,\;z_{n}=z_{n-1}^{2}+c$ Pl. a halmaznak eleme a 0 szám, mert ekkor nyilván a sorozat mindegyik tagja 0 lesz, viszont semelyik 2-nél nagyobb abszolútértékű szám nem, mert ekkor a sorozat tagjainak abszolút értéke monoton nőni fog.
• Egy pont halmazba tartozását a sorozat tagjainak kiszámításával lehet eldönteni: ha valamelyik lépésben 2-nél nagyobb abszolú értékű számot kapunk, akkor biztosan nem eleme, ha pedig egy, a sorozatban már szerepelt elemet, akkor biztosan eleme. Bizonyos számokról ez az eljárás nem tudja véges lépésben eldönteni, hogy a halmazba tartoznak-e.
• Megjegyzés: azokon a színes képeken, amiken a halmazt általában bemutatják, a középső (többnyire fekete) rész maga a halmaz, és a többi pont aszerint van színezve, hogy "mennyire gyorsan" száll el a végtelenbe a sorozata.
• Wikipédia: Mandelbrot halmaz

137. Adott egy EEG görbe. Írja le, hogy hogyan lehet kiszámítani a Hausdorff dimenzióját.

• A gyakorlatban a Hausdorff dimenzió nehezen számítható vagy mérhető. Léteznek viszont a dimenzióra más definíciók is, amik nem ekvivalensek egymással vagy a Hausdorff dimenzióval, de sok esetben azonos eredményt adnak. A dobozdimenzió (box counting dimension) jól használható szabálytalan, de fraktálszerű dolgok (pl. EEG görbe, földrész partvonala) dimenziójának mérésére. Lényege, hogy ráfektetünk az objektumra egy szabályos rácsot, és megnézzük, hány rácsnégyzet kell a lefedéséhez, illetve, hogy ez hogyan függ a rács méretétől. Ha a c méretű rácsnál N(c) négyzet kell a lefedéshez, akkor a dimenzió: $\lim _{c\rightarrow 0}{\frac {\log N(c)}{-\log c}}$
• Megjegyzés: valószínűleg a kérdés az órán elmondott vonalzós módszerre vonatkozott, viszont azt nem értem elég pontosan, és még nem találtam hozzá leírást, viszont matematikailag ez a módszer is korrekt.

• Wikipédia: dobozdimenzió

138. Tekintsük a következő homogén lineáris transzformációs mátrixot (a transzformálandó pontot a mátrix bal oldalára kell írni): $\left[{\begin{array}{rrr}3&0&0\\0&2&1\\0&0&0\end{array}}\right]$ Mit csinál a transzformáció?

?. Része-e a Mandelbrot halmaznak a -1 + j0 komplex szám?

71. Mekkora az alábbi Sierpinski halmaz Hausdorff dimenziója?

Ezen a helyen volt linkelve a Clipboard07.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• 3 darab, minden irányban felére zsugorított másolatából rakható ki az alakzat. Ha d dimenziós lenne, akkor a felére zsugorítás $0.5^{d}$-szeresére változtatná a "területét", és $2^{d}$ darab kis alakzatból lehetne az egészet kirakni. $2^{d}=3$ tehát a dimenziója ${\frac {\log 3}{\log 2}}\approx 1.585$
• Wikipédia: Sierpinski háromszög

139. Része-e a Mandelbrot halmaznak a $j={\sqrt {-1}}$ komplex szám?

• Előállítva a halmazhoz tartozást meghatározó sorozat első pár tagját: $z_{0}=0,\;z_{1}=j,\;z_{2}=-1+j,\;z_{3}=-j,\;z_{4}=-1+j$ és a sorozat ettől kezdve ismétlődik, mert a negyedik tag megegyezik a másodikkal. Nem fog tehát elszállni a végtelenbe, így a j a halmazhoz tartozik.

140. Mi a labilis attraktor? Hogyan lehet megjeleníteni?

141. Írjon fel egy olyan IFS-t, amelynek attraktora a (0,0), (1,1) sarkú négyzet.

• Úgy lehet egy alakzathoz őt előállító IFS-s csinálni, hogy az alakzatot a saját kicsinyített másaival kirakjuk (vagy, ha átfedés nélkül nem lehet, akkor lefedjük, de kilógnia a kicsinyített képeknek nem szabad az eredetiből). Majd, sorban felírjuk a transzformációkat, amik az eredeti alakzatot az őt lefedő kis alakzatokba transzformálják; az így felírt transzformációkból álló IFS képe a kívánt alakzat lesz.
• A konkrét esetben a 76. feladatban megadott transzformáció-készlet megfelelő: itt a négyzetet négy, fele akkora oldalhosszú négyzetből rakjuk ki.

142. Összefüggő-e a Julia halmaz a c=0+0j komplex számra? Mekkora a halmaz Hausdorff dimenziója?

• A Julia-halmaz a komplex számok egy részhalmaza. Azon $z_{0}$ komplex számok tartoznak a halmazba, amikre a $z_{n}=z_{n-1}^{2}+c$ sorozat nem száll el a végtelenbe. A c szám a halmaz paramétere, és alapvetően meghatározza a kinézetét: ha a c szám eleme a Mandelbrot-halmaznak, akkor a c-hez tartozó Julia-halmaz tartalmazza a 0 számot, és a halmaz egyetlen összefüggő tartomány. Ha c nem eleme a Mandelbrot-halmaznak, akkor a hozzá tartozó Julia-halmaz végtelen sok különálló pontból áll, és nem tartalmazza a 0-t.
• A c=0 számra a Julia-halmaznak nagyon egyszerű a szerkezete, ugyanis azokból a számokból áll, amiket, ha sokszor egymás után négyzetre emelünk, akkor nem szállnak el a végtelenbe. Ezek pedig az egynél kisebb vagy egyenlő abszolút értékű komplex számok; vagyis a halmaz c=0-ra a komplex síkon az origó körüli egységsugarú körből és annak belsejéből áll, összefüggő, dimenziója pedig 2.
• Wikipédia: Julia halmaz

-- G - 2008.12.26.