Omega Red

Omega Red's garbage heap

Information wants to be free.


News
About
Articles
Fractals
Life
C/C++
Asm
Files
Links
Shorts
Fun
Photos
Ponurnik


Polish
English





Fraktale

English version soon

[Gra w chaos] [Fraktale IFS] [L-systemy] [Baseny przyciągania] [Zbiory Julii] [Zbiór Mandelbrota]

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.

Istnieje kilka typów samopodobieństwa - mniejsze części mogą być idealną kopią całości, jak na przykład w trójkącie Sierpińskiego,
[Trójkąt Sierpińskiego]
mogą być też tylko podobne, lecz nie takie same, jak w słynnym zbiorze Mandelbrota:
[Zbiór Mandelbrota]

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

Jest to uproszczony wariant drugiego typu fraktali (patrz fraktale IFS ). Procedura ich rysowania jest banalnie prosta:
  1. Weź płaszczyznę.
  2. Narysuj na niej N punktów początkowych.
  3. Wybierz jakiś punkt odniesienia.
  4. Wylosuj liczbę R (w zakresie od 1 do N).
  5. Narysuj punkt w połowie odcinka łączącego początkowy punkt numer R i dotychczasowy punkt odniesienia. Właśnie narysowany punkt będzie nowym punktem odniesienia. (Trochę dużo tych punktów :-)
  6. Wróć do kroku 4.
Po nieskończenie wielu krokach :-) otrzymamy efekt końcowy. Oczywiście w praktyce zatrzymujemy się po jakiejś sensownej liczbie punktów... Przykład: 3 punkty początkowe ustawione w kształcie trójkąta dadzą w efekcie trójkąt Sierpińskiego (patrz wyżej).

Software:
  • Mój własny programik (chaos_g.exe / .pas). Obsługa: podajesz liczbę punktów początkowych, a potem ich współrzędne. Program zacznie rysować fraktal, dowolny klawisz = wyjście i zapisanie obrazka na dysk (fractal.bmp).

  • 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:

    1. Ustalamy zbiór przekształceń, którymi będziemy "działać" na płaszczyznę.
    2. Rysujemy na płaszczyźnie dowolny obraz początkowy.
    3. Przekształcamy obraz zgodnie z parametrami naszych odwzorowań (wynik będzie złożeniem wyników poszczególnych transformacji).
    4. Na powstały obraz znów działamy naszymi przekształceniami, i tak dalej...
    5. Kompletny fraktal powstaje oczywiście po nieskończonej ilości takich powtórzeń (iteracji - stąd nazwa: IFS = Iterated Function System, czyli Układ Odwzorowań Iterowanych). Tradycyjnie jednak, musimy przerwać po którejś tam iteracji...
    Najciekawsze jest to, że niezależnie od wybranego obrazu początkowego, efekt końcowy będzie identyczny!

    Software:

  • Fractint. Typ - ifs. Parametry fraktali zawarte są w pliku "FRACTINT.IFS", ale to już zupełnie inna historia...
  • Mój program (ifs.exe / .pas).
  • TOMIFS - z książki "Fraktale i obiektowe algorytmy ich wizualizacji".

  • 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:

    [Drzewko] [Smok] [Krzywa Hilberta]

    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:

    1. Iść do przodu o standardowy krok zostawiając lub nie zostawiając za sobą śladu.
    2. Obrócić się w prawo lub lewo o dany kąt.
    3. ...i to jak na razie wszystko, co potrafi.
    Krok i kąt obrotu są wstępnie określone.

    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:

    1. F = idź do przodu malując po drodze linię.
    2. f = idź do przodu nie malując po drodze linii.
    3. - = obróć się w lewo.
    4. + = obróć się w prawo.

    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):

    [Przykład]
    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:
    [Łamana Kocha 1]
    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 :-)
    [Łamana Kocha 2]

    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:
    [Krzywa 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:

    • [ oznaczający zapisanie stanu żółwia (kierunek, krok, kąt) na stosie. Użyteczne przy definiowaniu rozgałęzionych "roślinek".
    • ] czyli zdjęcie stanu ze stosu.
    • obrót o losowy (w pewnych granicach) kąt.
    • Można też w kolejnych krokach zmieniać nie tylko krok, ale i kąt obrotu.
    • ...ale to na razie tyle.

    Software:

  • Fractint... Typ - lsystem, a dalej jeszcze można wybierać. Definicje tych fraktali są zawarte w pliku "FRACTINT.L"

  • 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: x3 = 1. Jakie są jego rozwiązania? Oczywiście: x1 = 1. Ale to nie wszystko... Jeśli rozważymy też rozwiązania zespolone, znajdziemy jeszcze dwa: x2 = -0.5 + i*root2(3)/2 oraz x3 = -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:

  • Wybierz jakąś liczbę początkową x0.
  • Powtarzaj: xn+1 = xn - f (xn) / f '(xn) (f ' to pochodna funkcji f)
  • OCZYWIŚCIE dokładne rozwiązanie otrzymamy po nieskończonej ilości kroków... Ale zazwyczaj ta metoda dosyć szybko dostarcza wystarczająco dokładnych liczb.
  • 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 x3-1 = 0:

    [Przykładowy obraz obszarów przyciągania]

    Software:

  • Fractint... Typ - newtbasin lub newton (różne metody kolorowania).
  • Mój program (newton.exe / .pas) - rysuje właśnie powyższy obrazek (powiedzmy...:)
  • TOMFRAC - z książki "Fraktale i obiektowe algorytmy ich wizualizacji".

  • 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...

    [Julia 1] [Julia 2] [Julia 3] [Julia 4]

    No i algorytm:

  • Weź jakąś liczbę zespoloną C. Ona określa wygląd zbioru.
  • Weź jakąś część płaszczyzny.
  • Tak jak przy 'basenach', każdy punkt (x,y) traktuj jako liczbę zespoloną Z0 = x + y*i
  • Powtarzaj: Zn+1 = Zn2 + C
  • Jeśli punkt ucieka do nieskończoności, pomaluj go na biało. Jeśli nigdy nie ucieknie, pomaluj go na czarno. Zbiór Julii to granica między punktami-więźniami, a punktami uciekającymi do nieskończoności.
  • Taaak... Chyba czas co nieco wyjaśnić :-)

    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 |Zn| > 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:

  • Fractint... Typ - julia lub julia_inverse (ulepszona metoda IFS)
  • Mój program (julia.exe / .pas).
  • TOMFRAC - z książki "Fraktale i obiektowe algorytmy ich wizualizacji".

  • 6. Zbiór Mandelbrota

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

    [Mandel 1] [Mandel 2] [Mandel 3] [Mandel 4]

    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:

  • Weź jakąś część płaszczyzny.
  • Każdy punkt (x,y) traktuj jako liczbę zespoloną C = x + y*i
  • Z0 = 0
  • Powtarzaj: Zn+1 = Zn2 + C (Ten sam wzór!)
  • Jeśli punkt ucieka do nieskończoności, pomaluj go na biało. Jeśli nigdy nie ucieknie, pomaluj go na czarno. Zbiór Mandelbrota to zbiór wszystkich punktów-więźniów powyższego procesu.
  • 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 Z0 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...

    [Czad 1] [Czad 2] [Czad 3] [Czad 4]

    Software:

  • Fractint... Typ - mandel. Ponadto większość innych typów jest różnymi hybrydami zbiorów Julii i Mandelbrota...
  • Mój program (mandel.exe / .pas / .c).
  • TOMFRAC - z książki "Fraktale i obiektowe algorytmy ich wizualizacji".



  • [News][About][Articles][Fractals][Life][C/C++][Asm][Files][Links][Shorts][Fun][Photos][Ponurnik]

    Copyright by Omega Red 2003,2004