POWRÓT DO STRONY GŁÓWNEJ
IFS - Iterated Functions System
Copyright © 2004 Robert Nowotniak
Kod źródłowy: https://github.com/rnowotniak/ifs2004.
Wstęp
Program IFS służy do tworzenia i badania fraktali, dziwnych atraktorów i układów
dynamicznych opartych na systemie iterowanych odwzorowań.
Obrazy mogą być tworzone przy pomocy klasycznego modelu Kopiarki
Wielokrotnie Redukującej a także
algorytmu probabilistycznego, tzw. modelu sprzężonego z ruletką (układ
losowy). Przy wyborze losowym istnieje możliwość regulacji
prawdopodobieństw wyboru odwzorowań, co pozwala dostrajać układy na różne sposoby.
Program znacznie ułatwi także wyobrażenie sobie, w jaki sposób przekształcenia afiniczne
- w szczególności liniowe - działają na płaszczyznę.
Jak to działa?
Iterowany układ odwzorowań jest matematycznym modelem Kopiarki Wielokrotnie Redukującej.
Klasyczny model kopiarki działa na zasadzie sprzężenia zwrotnego przy użyciu układu soczewek,
odwzorowujących płaszczyznę i wykonujących translacje, skalowania, pochylenia, obroty i odbicia.
Pozwala to zakodować bardzo złożone, samoafiniczne obrazy przy użyciu jedynie niewielkiej liczby
współczynników.
Przekształcenie afiniczne odwzorowuje punkt płaszczyzny (x, y) na punkt (u, v) za pomocą
równań:

,
(1°)
co odpowiada macierzy odwzorowania:

.
Aby móc wyrazić złożenie przekształceń w wygodny sposób, przyjmuje się oznaczenia:

.
Dzięki temu współczynniki r i s mogą być utożsamiane
z rozciąganiem soczewki w poziomie i pionie, a φ i ψ z kątami obrotów.
Po podstawieniu otrzymujemy równoważną macierz:

.
Program pozwala posługiwać się obydwiema tymi notacjami w łatwy sposób:
Działanie polegające na sumowaniu obrazów uzyskanych z poszczególnych
soczewek jest nazywane operatorem Hutchinsona, a wielokrotne
przekształcanie jest iterowaniem tego operatora.
Uzyskany ciąg obrazów dąży w granicy do obrazu, będącego atraktorem
danego układu odwzorowań.
 |
Drzewo uzyskane za pomocą sześciu układów równań KWR.
Czy to nie zadziwiające, jak bardzo jest podobne w swojej budowie do naturalnego drzewa?
|
Algorytm IFSP jest modelem urządzenia, łączącego determinizm z losowością.
Wybór odwzorowania, któremu zostanie poddany rezultat poprzedniego kroku
sprzężenia zwrotnego jest tu zupełnie losowy. Szczególnym i najprostszym
przykładem takiego układu, opartego na chaosie, jest algorytm nazwany
przez M. Barnsleya "grą w chaos", prowadzący do uzyskania trójkąta Sierpińskiego.
Ogromną zaletą algorytmu probabilistycznego IFSP jest znacznie mniejsza złożoność obliczeniowa,
bo jedynie O(n), gdzie rozmiarem danych jest liczba punktów, poddawanych iterowaniu.
Złożoność obliczeniowa w klasycznym przypadku IFS jest funkcją wykładniczą o podstawie równej
ilości soczewek. W układach o bardzo małej liczbie soczewek (np. smok Hartera-Heighwaya)
warto stosować model klasyczny nawet przy dość dużej liczbie powtórzeń.
Natomiast model sprzężony z ruletką daje dobre rezultaty zwłaszcza po
dobraniu odpowiednich prawdopodobieństw wyboru odwzorowań. Soczewki
o dużych powierzchniach powinny być wybierane znacznie częściej niż
wąskie patyczki.
Obraz uzyskany w modelu losowym jest też często trochę zaciemniony małą
ilością punktów w niespodziewanych miejscach, jednak ostatecznie uwidacznia się pewien atraktor,
o ile nie jest to układ niestabilny.
Stąd lepiej nie stosować go w przypadku fraktali, w których jest to
istotne (np. kurz Cantora).
|
W tym układzie jako obrazu wejściowego użyłem bitmapy ze zbiorem Mandelbrota.
Po 6 cyklach widać, że uzyskany fraktal to krzywa Kocha.
|
Otrzymywanie stałego obrazu końcowego dla danego układu soczewek, niezależnie od
danych podanych na wejściu przed pierwszym cyklem wynika z zasady Banacha o odwzorowaniu
zwężającym. W tym przypadku punktami przestrzeni, na którą działa operator Hutchinsona są obrazy uzyskiwane
w kolejnych cyklach, metryką jest natomiast odległość Hausdorffa między tymi obrazami.
Operator działa zwężająco w zależności od tego, w jakiej skali kopiuje soczewka,
która pomniejsza obraz w najmniejszym stopniu.
Ponieważ odwzorowanie zwężające ma zawsze jeden punkt stały,
końcowy obraz nie zależy od punktu (obrazu) początkowego, co pokazuje powyższy
przykład.
W szczególności taki sam atraktor uzyskuje się w sytuacji, gdy obraz początkowy składa się
z pojedynczego punktu, na tym fakcie opiera się algorytm losowy.
Nakładanie bitmap przekształconych według podanej macierzy odbywa się w programie
przez wyznaczenie macierzy przekształcenia odwrotnego. Każdy punkt docelowej
bitmapy jest sprawdzany, czy nie jest on obrazem jakiegoś punktu należącego
do bitmapy źródłowej w danym przekształceniu. Współrzędne takiego punktu znajduję
za pomocą rozwiązania układu (1°) względem niewiadomych x i y,
co daje:

.
Program może też użyć rekurencyjnego algorytmu znajdowania obrazu w n-tym cyklu.
W ten sposób uzyskuje się stos macierzy przekształceń afinicznych.
Tylko w najgłębszym poziomie rekurencji (równym żądanej ilości powtórzeń) wykonuje się
rysowanie przy użyciu aktualnie obowiązującego przekształcenia. W innym przypadku dla
każdej soczewki funkcja wywołuje samą siebie, ustalając nową obowiązującą macierz przekształcenia
przez złożenie aktualnego przekształcenia z przekształceniem danej soczewki.
Zakładając, że mamy przekształcenia afiniczne
f1:(x,y)→(u1,v1) i
f2:(u1,v1)→(u2,v2):

,
złożeniem tych przekształceń jest
f3=f2(f1):(x,y)→(u2,v2):
Przykłady fraktali
- Smok Hartera-Heighwaya
a | b | c | d | e | f |
0.5 | 0.5 | -0.27 | -0.5 | 0.5 | 0 |
-0.5 | 0.5 | 0.14 | -0.5 | -0.5 | 0 |
- Inny znany smok
a | b | c | d | e | f |
0.824 | 0.281 | -1.88 | -0.212 | 0.86 | -0.11 |
0.088 | 0.521 | 0.78 | -0.463 | -0.377 | 8.09 |
- Trójkąt Sierpińskiego
a | b | c | d | e | f |
0.5 | 0 | -0.25 | 0 | 0.5 | -0.25 |
0.5 | 0 | 0.25 | 0 | 0.5 | -0.25 |
0.5 | 0 | 0 | 0 | 0.5 | 0.25 |
- Dywan Sierpińskiego
a | b | c | d | e | f |
0.333 | 0 | -0.333 | 0 | 0.333 | 0.333 |
0.333 | 0 | 0 | 0 | 0.333 | 0.333 |
0.333 | 0 | 0.333 | 0 | 0.333 | 0.333 |
0.333 | 0 | 0.333 | 0 | 0.333 | 0 |
0.333 | 0 | 0.333 | 0 | 0.333 | -0.333 |
0.333 | 0 | 0 | 0 | 0.333 | -0.333 |
0.333 | 0 | -0.333 | 0 | 0.333 | -0.333 |
0.333 | 0 | -0.333 | 0 | 0.333 | 0 |
- Pięciokąt Sierpińskiego
a | b | c | d | e | f |
0.38 | 0 | 0.235 | 0 | 0.38 | -0.323 |
0.38 | 0 | -0.235 | 0 | 0.38 | -0.323 |
0.38 | 0 | 0 | 0 | 0.38 | 0.4 |
0.38 | 0 | 0.38 | 0 | 0.38 | 0.123 |
0.38 | 0 | -0.38 | 0 | 0.38 | 0.123 |
- Labirynt Cantora
a | b | c | d | e | f |
0.333 | -0 | 0 | 0 | 0.333 | 0.3333 |
0 | -0.333 | -0.3333 | 1 | 0 | 0 |
0 | 0.333 | 0.333 | -1 | 0 | 0 |
- Kurz Cantora
a | b | c | d | e | f |
0.333 | 0 | -0.333 | 0 | 0 | 0 |
0.333 | 0 | 0.333 | 0 | 0 | 0 |
- Kurz Cantora 2D
a | b | c | d | e | f |
0.333 | 0 | 0.333 | 0 | 0.333 | 0.333 |
0.333 | 0 | -0.333 | 0 | 0.333 | 0.333 |
0.333 | 0 | 0.333 | 0 | 0.333 | -0.333 |
0.333 | 0 | -0.333 | 0 | 0.333 | -0.333 |
- Krzywa Kocha
a | b | c | d | e | f |
0.3333 | 0 | -0.3333 | 0 | 0.3333 | 0 |
0.1665 | -0.288386 | -0.083333 | 0.288386 | 0.1665 | 0.14433 |
0.1665 | 0.288386 | 0.083333 | -0.288386 | 0.1665 | 0.14433 |
0.333 | 0 | 0.333 | 0 | 0.3333 | 0 |
- Drzewo
a | b | c | d | e | f |
0.05 | 0 | -0.06 | 0 | 0.4 | -0.47 |
-0.05 | 0 | -0.06 | 0 | -0.4 | -0.47 |
0.03 | -0.14 | -0.16 | 0 | 0.26 | -0.01 |
-0.03 | 0.14 | -0.16 | 0 | -0.26 | -0.01 |
0.56 | 0.44 | 0.3 | -0.37 | 0.51 | 0.15 |
0.19 | 0.07 | -0.2 | -0.1 | 0.15 | 0.28 |
-0.33 | -0.34 | -0.54 | -0.33 | 0.34 | 0.39 |
- Kolejne drzewko...
a | b | c | d | e | f |
0.01 | -0 | 0 | 0 | 0.45 | 0 |
-0.01 | 0 | 0 | 0 | -0.45 | 0.4 |
0.42 | -0.42 | 0 | 0.42 | 0.42 | 0.4 |
0.42 | 0.42 | 0 | -0.42 | 0.42 | 0.4 |
- ...i jeszcze jedno
a | b | c | d | e | f |
0.195 | -0.48 | 0.443 | 0.34 | 0.443 | 0.245 |
0.462 | 0.414 | 0.251 | -0.252 | 0.361 | 0.569 |
-0.058 | -0.07 | 0.59 | 0.453 | -0.111 | 0.096 |
-0.035 | 0.07 | 0.488 | -0.469 | -0.022 | 0.506 |
-0.637 | 0 | 0.856 | 0 | 0.501 | 0.2513 |
- Bliźniacza Choinka
a | b | c | d | e | f |
0 | -0.5 | -0.25 | 0.5 | 0 | -0.25 |
0 | 0.5 | 0.25 | -0.5 | 0 | -0.25 |
0.5 | 0 | 0 | 0 | 0.5 | 0.25 |
- Kryształek lodu
a | b | c | d | e | f |
0.255 | 0 | 0.3726 | 0 | 0.255 | 0.6714 |
0.255 | 0 | 0.1146 | 0 | 0.255 | 0.2232 |
0.255 | 0 | 0.6306 | 0 | 0.255 | 0.2232 |
0.37 | -0.642 | 0.6356 | 0.642 | 0.37 | -0.00061 |
- Spirala spiral
a | b | c | d | e | f |
0.787879 | -0.424242 | 1.75865 | 0.242424 | 0.859848 | 1.40806 |
-0.121212 | 0.257576 | -6.72165 | 0.151515 | 0.05303 | 1.37724 |
0.181818 | -0.136364 | 6.08611 | 0.090909 | 0.181818 | 1.56804 |
- Paprotka Barnsleya
a | b | c | d | e | f |
0 | 0 | 0 | 0.2 | 0.16 | -0.04 |
0.2 | -0.26 | 0 | 0.23 | 0.22 | 0.1 |
-0.15 | 0.28 | 0 | 0.26 | 0.24 | 0.1 |
0.85 | 0.04 | 0 | -0.04 | 0.84 | 0.1 |
- Piórko
a | b | c | d | e | f |
0.7 | 0.109682 | 0.05 | -0.109504 | 0.893292 | 0.1 |
0.058474 | -0.573783 | -0.18 | 0.191261 | 0.175423 | -0.21 |
0.011 | 0 | 0 | 0 | 0.3 | -0.35 |
-0.067485 | 0.579556 | 0.21 | 0.292311 | 0.155291 | -0.21 |
- Gałązka
a | b | c | d | e | f |
0.4 | -0.2 | 0.13 | 0 | -0.4 | -0.05 |
0.431604 | 0.353533 | 0.2 | 0.416795 | -0.421324 | 0.15 |
0.470197 | 0 | -0.26 | 0.096513 | 0 | -0.053 |
Pobierz
Kod źródłowy dostępny jest w repozytorium: https://github.com/rnowotniak/ifs2004.
Licencja
Niniejszy program jest wolnym oprogramowaniem; możesz go rozprowadzać dalej
i/lub modyfikować na warunkach Powszechnej Licencji Publicznej
GNU,
wydanej przez Fundację Wolnego Oprogramowania - według wersji 2-giej tej
Licencji lub którejś z późniejszych wersji.
Obrazki na tej stronie zostały zrobione za pomocą mojego programu.
Bibliografia
- H.-O.Peitgen, H.Jurgens, D.Saupe - Granice chaosu. Fraktale (tom I i II)
- Jacek Kudrewicz - Fraktale
- Tomasz Martyn - Fraktale i obiektowe algorytmy ich wizualizacji
- Roger Penrose - Nowy umysł cesarza
POWRÓT DO STRONY GŁÓWNEJ