IFS - Iterated Functions System

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 f₁:(x,y)→(u₁,v₁) i f₂:(u₁,v₁)→(u₂,v₂):

    ,    

złożeniem tych przekształceń jest f₃=f₂(f₁):(x,y)→(u₂,v₂):

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

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