Mandelbrotova množina

Algoritmy Grafické Mandelbrotova množina

Na Mandelbrotovu množinu narazil Benoid Mandelbrot v 70. letech minulého století, při zkoumání Juliových množin. Pokoušel se sestavit jakýsi jejich katalog. Ale rozhodně nebyl jejím objevitelem. Ve stejné době (kousek před Mandelbrotem) byl na matematické konveci představen článek od Brookse a Matelskiho, který také obsahoval obrázky Mandelbrotovy množiny. Mandelbrot ji však důkladně popsal a prvenství připadlo jemu. Někteří z vás možná zaslechli zprávy o starodávné rytině přisuzované starodávnému umělci Udo von Aachenovi, která údajně obsahovala Mandelbrotovu množinu, schovanou v obrazu. Ty ale bohužel musím zklamat - jedná se samozřejmě o hoax :)

Ale teď k tomu, co to Mandelbrotova množina vlastně je. Je to fraktál ležící v komplexní rovině a to v rozmezí [-2;-2] do [2;2] (hranatými závorkami značím komplexní číslo). Je to zřejmě nejznamější fraktál vůbec. Je vyjádřena vzorcem Z = Z2 + C, kde Z a C jsou komplexní čísla. C je konstantní a je pozicí bodu, pro který koeficient Z počítáme. Z je na začátku [0;0]. Z budeme počítat iteračně, to znamená, že budeme výpočet Z = Z2 + C provádět tak dlouho, dokud nám nedojde námi stanovený počet pokusů (například 20) nebo se splní podmínka, že zkoušený bod neleží v množině. Tato podmínka zní: |Z| > 2 (absolutní hodnota Z je větší než 2). Pokud nám dojdou pokusy a podmínka se nesplnila, vybarvíme bod černě (bod do množiny patří). Pokud dojde k tomu, že |Z| > 2, bod obarvíme. Pro začátek ho můžeme obarvit třeba bíle. Pokud by jsme chtěli hezčí obrázek, můžeme bod vybarvit například modře a odstín určit podle toho, kolik pokusů bylo potřeba k tomu, aby jsme zjistili, že v množině neleží. Této variace jsem využil já. Potom tu je ještě řada palet (vzorců), pro ještě zajímavější obarvení.

Postup při vykreslení

Vzorec Z = Z2 + C musíme aplikovat na všechny body v množině. Ta je v rozsahu X od -2 do 2 a Y také od -2 do 2. Budeme tedy potřebovat 2 do sebe vnořené cykly a 2 celočíselné proměnné X a Y, ktere nám tyto body "projedou" (dle velikosti výřezu, např 0..799 a 0..599).

Určíme si nějaký počet pokusů (iterací) na vyzkoušení, jestli právě testovaný bod do množiny patří nebo nikoli. Vytvoříme tedy proměnnou nebo konstantu maxiter, které přiřadíme 20. Dále nějaké počítadlo pokusů, které si nazveme iter. K samotnému testu bodu budeme potřebovat komplexní číslo Z, které před každým pokusem vynulujeme, komplex. číslo C (reálná a imaginární část budou proměnné X a Y, protože C je pozice bodu v množině) a dále absolutní hodnotu Z a Z2.

Absolutní hodnota komplexního čísla Absolutní hodnotu komplexního čísla spočítáme použitím Pythagorovy věty, protože absolutní hodnota je vzdálenost čísla od nuly.
Čili :

Z ^2 = Z.r2 + Z.i2
Z = odmocnina(Z.r2 + Z.i2)

S vypočítáním druhé mocniny Z je to malinko složitější. Z2 můžeme vyjádřit jako součin Z * Z, čili součin dvou komplexních čísel, pro který platí obecný vzorec :

(A + Bi) * (C + Di)
AC + BCi + ADi + BDi2             (i2 = -1)
Re = AC - BD       (reálná část násobku)
Im = BCi + ADi       (imaginární část násobku)

V našem případě jsou hodnoty:
A = Z.r
B = Z.i
C = Z.r
D = Z.i

A po dosazení:
Re = Z.r2 - Z.i2
Im = Z.i * Z.r + Z.i * Z.r = 2 * Z.i * Z.r

Takže cykly X a Y projedeme všechny body množiny. Pro každý bod vynulujeme číslo Z, do C dosadíme [X;Y] a počítadlo iterací také vynulujeme. Spočítáme si Z2 (viz výše) a do Z dosadíme [Z2 + C]. Spočítáme si absolutní hodnotu Z a pokud je větší než 2, skončíme a bod obarvíme příslušnou barvou. Pokud ne, zvýšíme iter o jedna a jedeme znovu. Pokud vyplýtváme všechny pokusy a podmínka se stále nesplní, obarvíme bod černě.

Výsledek se základním obarvením vypadá asi takto:

mandelbrotova množina

Zdrojový kód a ukázkový program

Můžete se podívat na ukázkový program Mandelbroth včetně zdrojového kódu


 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (3 hlasů) :
55555


 


Miniatura
Předchozí článek
Plechovka čili Floodfill
Miniatura
Všechny články v sekci
Grafické algoritmy

 

 

Komentáře

Avatar
dl
Neregistrovaný
Avatar
dl:

Správně by mělo být Juliova množina: http://cs.wikipedia.org/…mno%C5%BEina

 
Odpovědět 10.9.2012 18:08
Avatar
Kit
Redaktor
Avatar
Kit:

Určitě bych se zmínil o možnosti využití datového typu complex, který je obsažen v mnoha programovacích jazycích a nativně pracuje např. s absolutní hodnotou, o sčítání a násobení nemluvě.

Odpovědět 10.9.2012 18:25
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
skorepova.v
Člen
Avatar
skorepova.v:

Díky, konečně srozumitelný článek o Mandelbrothově množině. V programátorování se vůbec nevyznám, ale tenhle program se mi moc líbí. :) :)

 
Odpovědět 29.11.2012 21:25
Avatar
meell
Člen
Avatar
Odpovídá na dl
meell:

U juliovy množiny se jedná o opačný proces.. C je konstanta určující tvar množiny.. A za Z dosazujeme [x,y] grafu.. Nicméně poznámka velice podnětná odkazem.. Neboť Juliových množin je nekonečně mnoho (dokonce víc než reálných čísel) a dá se tak vytvořit libovolný fraktál tohoto typu..

 
Odpovědět 12.12.2013 16:25
Avatar
dl
Neregistrovaný
Avatar
Odpovídá na meell
dl:

Článek zcela správně píše o Mandelbrotově množině, ale zmiňuje se v první větě o "Jiliových" množinách, to je podle mně překlep .)

 
Odpovědět 12.12.2013 17:04
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na dl
David Čápka:

Díky, byl to samozřejmě překlep, opraveno.

Odpovědět 12.12.2013 17:08
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.