Omega Red's garbage heap

Fraktale

English version soon

Fraktale... co to w ogóle jest? Istnieje kilka ścisłych matematycznych definicji, ale najprościej będzie wytłumaczyć to na przykładzie. Na pewno każdy widział w życiu paproć :-) Cóż w niej jest takiego szczególnego? Przyjrzyj się jej liściu. Zauważysz, że małe listki wyrastające z dużego są do niego bardzo podobne, tyle że w mniejszej skali. I w tym właśnie tkwi sedno sprawy - samopodobieństwo - bo tak to się "fachowo" nazywa - to główna cecha fraktali.

Można wyróżnić wiele typów fraktali, teraz powiem co nieco o każdym z nich. Dla programistów i tych, którzy chcą dokładnie wiedzieć "jak to się robi" zamieściłem dodatkowe informacje w osobnych odnśnikach. Na końcu każdego działu w punkcie "Software" opisuję programy, które potrafią rysować to, co wcześniej omawiałem.

1. Gra w chaos

2. Fraktale IFS

Ten typ fraktali opiera się na tak zwanych afinicznych przekształceniach zwężających. Mówiąc w skrócie, te przekształcenia działają na płaszczyznę i są złożeniem elementarnych transformacji - skalowania (zmniejszanie), obrotów osi układu współrzędnych i przesunięcia. Fraktale IFS powstają następująco:

Software:

3. L-systemy

Ten z kolei rodzaj potrafi doskonale naśladować różne "roślinki" i inne rozgałęzione lub nie mniej lub bardziej "biologiczne" twory:

Algorytm jest jak zwykle :-) w miarę prosty. Opiera się na "grafice żółwia", z którą może niektórzy mieli okazję się zetknąć w postaci języka LOGO. Wyobraź sobie, że po ekranie chodzi sobie sterowany przez nas żółw (czemu akurat żółw - nie mam pojęcia :-) W zależności od wydawanych przez nas polecenia może on robić różne rzeczy:

Teraz wypadałoby w jakiś prosty sposób zapisać nasze polecenia dla żółwika. Zrobimy więc tak: każde polecenie będziemy oznaczać jakimś symbolem, a lista tych poleceń do jednorazowego wykonania ("program"...) będzie ciągiem takich symboli. Żeby nie być gołosłownym, lista poleceń może wygądać tak:

Teraz mały przykładzik: jeśli naszym poleceniem jest "F-Ff+F+Ff-F-" a kąt = 90 stopni, żółw (zwrócony początkowo w prawo) namaluje coś takiego (niebieski trójkąt = położenie początkowe, zielony - końcowe):


Jasne? Mam nadzieję :-)

No, to jesteśmy twardzi. Ale jak zmusić zwierzaka do rysowania fraktali zamiast prostych szlaczków? I na to jest sposób (jak na wszystko zresztą :) Wystarczy tylko powtarzać w nieskończoność... no właśnie, co?

Trzeba zastosować pewną prostą :) sztuczkę: oprócz standardowych reguł poruszających żółwia potrzebujemy jeszcze reguł podstawiania dla każdego symbolu. W każdym kroku każdy symbol w definicji fraktala (nasz "program" dla zwierza) zastępujemy ustalonym ciągiem symboli. Jasne? Pewnie nie :-) Czyli przykładzik (jak zwykle początkowo żółw jest zwrócony w prawo):

Niech definicja będzie takowa: "F-F++F-F", a kąt = 60 stopni. Co narysuje żółw? Ano to:

OK. Teraz w każdym kroku za "F" podstawimy właśnie "F-F++F-F". Jednocześnie zmniejszymy krok żółwia o 1/3. Co dostaniemy? "F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F" (kto nie wierzy, niech sprawdzi :-) A co teraz narysuje żółw? Oto jest pytanie :-)

Po prostu w miejscu każdej linii poprzedniej figury jest teraz cała figura pomniejszona trzykrotnie. Widzicie już samopodobieństwo?... Oczy-wiście, żeby powstał kompletny fraktal trzeba owo podstawianie i zmniejszanie kroku powtórzyć nieskończenie wiele razy (tak, tak, od nieskończoności się nie ucieknie :-) W granicy dostaniemy krzywą Kocha:

Łatwo (szereg geometryczny :-) policzyć, że ma ona nieskończoną długość :-)))

Tak więc umiemy już rysować fraktalne L-systemy. Podstawiać można ofcoz także za "+", "-" i "f". No i podstawienie może być dowolne... A jeśli kogoś interesują jeszcze większe możliwości... Możemy dodać kilka symboli:

Software:

4. Baseny przyciągania (?)

No tak... W tym momencie wkraczamy w świat liczb zespolonych. Jeśli nie masz pojęcia, co to jest (a chcesz wiedzieć :-) - przeczytaj powyższy wstępniak. Bez znajomości tych spraw raczej nie da się wytłumaczyć tego i dwóch kolejnych typów fraktali.

Oki. Zakładam, że w tym momencie masz już niejakie pojęcie o "zespołkach". Pora więc wyjaśnić zapewne intrygującą nazwę "baseny przyciągania". Żeby nie wnikać za bardzo, podam przykładzik (od teraz root2(x) znaczy pierwiastek kwadratowy z x, root3(x) = pierwiastek 3-go stopnia itd - niestety, zwykły HTML nie za bardzo nadaje się do zapisywania wyrażeń matematycznych, a nie ma sensu robić ich jako obrazków...):

Mamy prościutkie równanie: x³ = 1. Jakie są jego rozwiązania? Oczywiście: x₁ = 1. Ale to nie wszystko... Jeśli rozważymy też rozwiązania zespolone, znajdziemy jeszcze dwa: x₂ = -0.5 + i*root2(3)/2 oraz x₃ = -0.5 - i*root2(3)/2...

To był tylko wstępniak :-) Teraz poznamy metodę Newtona przybliżonego rozwiązywania równań. Jest ona w miarę prosta (dla komputera :-) Potrzebna będzie jeszcze umiejętność liczenia pochodnych funkcji :-))) A więc aby rozwiązać równanie f(x) = 0:

Jest tylko jeden mały szkopuł... Jeśli równanie ma więcej niż jedno rozwiązanie, to do KTÓREGO z nich będzie dążyła powyższa iteracja?... Otóż z góry NIE WIADOMO. Wiadomo tylko, że dla różnych liczb początkowych można dochodzić do różnych rozwiązań. I tu właśnie wkraczają fraktale.

Bierzemy nasze równanie (rozpatrywane w liczbach zespolonych). Wybieramy jakiś fragment płaszczyzny. Teraz każdy punkt z tego fragmentu traktujemy jako liczbę zespoloną - początkową naszego procesu iteracji i sprawdzamy, do którego z rozwiązań doszliśmy. Teraz malujemy ten punkt na kolor odpowiadający danemu rozwiązaniu. I powtarzamy iterację dla wszystkich punktów... Tu wyjaśnia się pojęcie basenów przyciągania: na wynikowym obrazku będą to jednakowo pokolorowane obszary, oznaczające te liczby początkowe, których iteracja prowadzi do tego samego rozwiązania - rozwiązanie "przyciąga" te punkty... Można myśleć, że owe obszary będą na przykład podzielone prostymi liniami, ale zazwyczaj są one fraktalami... Dla przykładu - wynik zastosowania tego algorytmu dla naszego poprzedniego równanka x³-1 = 0:

Software:

5. Zbiory Julii

A teraz zajmiemy się jedną z ciekawszych klas fraktali (a która nie jest ciekawa :-) Zbiory Julii wzięły swoją nazwę nie od jakiejś panienki, ale od francuskiego matematyka Gastona Julii (naprawdę tak się nazywał!). A jak to wygląda i jak powstaje? Za chwilę wszystko się wyjaśni, a tymczasem kilka obrazków...

No i algorytm:

Jak poznać, czy punkt ucieknie, czy nie? Raczej trudno byłoby przeprowadzić nieskończoną ilość iteracji i się przekonać. Standardowo rozwiązuje się to tak: przyjmuje się jakąś maxymalną liczbę iteracji (im więcej, tym wolniej, ale i dokładniejszy obraz). Iteruje się powyższe równanko, sprawdzając za każdym razem, czy |Z_n| > 2. Jeśli tak, punkt na pewno ucieknie. Zaś uznaje się, że punkt jest więźniem, jeśli po wykonaniu owej maxymalnej liczby iteracji jeszcze nie uciekł... Ciekawsze obrazy można uzyskać uzależniając kolor pixela od szybkości z jaką dany punkt ucieka. Najprościej zrealizować to tak, że kolor = (ilość wykonanych iteracji) mod (ilość kolorów), gdzie mod to reszta z dzielenia. Przy odpowiednio dobranej palecie można uzyskać niesamowite wyniki...

Ta metoda jest banalnie prosta, ale dosyć wolna... Szybciej można narysować zbiór Julii stosując pewną modyfikację algorytmu IFS, ale nie ma nic za darmo... Bez istotnych poprawek obrazy większości zbiorów uzyskane tą metodą będą pozbawione wielu szczegółów. Można temu zaradzić, ale o tym i w ogóle o nieliniowych IFS może innym razem...

Zawsze fascynował mnie fakt, że z tak niesamowicie prostych wzorów (tylko powtarzanych miliony razy) powstają tak niebywale skomplikowane kształty. Jest w tym coś z magii... To tak, jak matematyczny wzór na piękno... Każdy ze zbiorów Julii Jest nieskończenie złożony - dosłownie. Dowolnie duże powiększenie odsłania wciąż nowe szczegóły. A istnieje przecież nieskończenie wiele zbiorów - tyle, ile liczb zespolonych. A ponieważ liczba zespolona = punkt płaszczyzny, każdemu punktowi odpowiada jakiś zbiór... Zbiory Julii są różne - ale dają się podzielić na spójne (złożone z 'jednego kawałka') i nie (zbudowane z chmury oddzielnych punktów). Powstaje pytanie - co by było, gdyby punkty płaszczyzny odpowiadające spójnym zbiorom Julii zaznaczyć jednym kolorem? Na to pytanie odpowiedzią jest najsłynniejszy chyba fraktal - Zbiór Mandelbrota...

Software:

6. Zbiór Mandelbrota

Każdy obraz jest wart więcej, niż tysiąc słów... Oto kilka powiększeń tego Wszechświata:

W poprzednim punkcie mówiłem o zbiorach Julii i ich związkom ze zbiorem Mandelbrota. Jednak żeby go narysować, wcale nie trzeba odwoływać się do spójności itd. Otóż algorytm jest bardzo podobny do metody wizualizacji zbiorów Julii:

Podobnie jak przy zbiorach Julii można ubarwić wynik nadając punktowi kolor zależny od liczby iteracji, po których opuścił 'magiczne koło' o promieniu 2. Punkty wewnętrzne zbioru zaznacza się zazwyczaj na czarno - cała feeria barw na powyższych obrazkach pochodzi z punktów nie należących do zbioru. I choć może się wydawać, że niektóre części zbioru są oddzielone od innych, to jest to tylko niedoskonałość rysunku - w rzeczywistości zbiór Mandelbrota jest spójny. Poza tym, okazuje się, że najciekawsze obrazy zbiorów Julii dają 'zaczątki' (parametr C) wzięte z punktów leżących blisko brzegu zbioru Mandelbrota... (Jak naocznie się o tym przekonać - znajdziesz tutaj)

Żeby jeszcze bardziej urozmaicić świat fraktali, jako Z₀ w powyższym algorytmie można wziąść dowolną liczbę zespoloną (dodać perturbacje). Powstałe w wyniku hybrydowe zbiory zazwyczaj nie są symetryczne, lecz to nie znaczy, że gorsze... Zresztą, co się będziemy ograniczać! :-) Weźmy DOWOLNY wzór, DOWOLNE warunki zakończenia iteracji i DOWOLNĄ metodę kolorowania... W prawie wszystkich przypadkach otrzymamy fraktale... Nieskończoną różnorodność nieskończonych Wszechświatów...

Software:

Copyright by Omega Red 2003,2004