powrót do strony głównej >>

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.

Dołożyłem starań, by informacje na tej stronie były prawdziwe, ale interesuję się tym amatorsko, więc mogę być częściowo lub całkowicie niepoprawnym.

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

Copyright © Robert Nowotniak
31 sierpnia 2004