Odwzorowania Hutchinsona
Smok Heighwaya |
Odwzorowanie płaszczyzny w siebie dane wzorem (1) $f(x,\, y) = (ax + by + e,\,cx + dy + g)$ nazywamy odwzorowaniem afinicznym. Odwzorowania afiniczne zachowują prostoliniowość
i równoległość. Przesunięcia, obroty, jednokładności, rzutowania równoległe, odbicia symetryczne oraz złożenia wymienionych odwzorowań są odwzorowaniami afinicznymi.
Jeśli $A$ jest podzbiorem płaszczyzny, to wzór (1) możemy zastosować do każdego punktu tego zbioru, otrzymany w ten sposób zbiór będziemy oznaczać $f(A)$. Odwzorowania Hutchinsona $H$ otrzymujemy w następujący sposób:
|
- $f_1(x; y) = (\frac{x}{2}; \frac{y}{2})$, jednokładność o skali $0,5$
- $f_2(x; y) = (\frac{x}{2}; \frac{y}{2}) + (\frac{1}{2}; 0)$, złożenie jednokładności o skali $0,5$ i przesunięcia w prawo
- $f_1(x; y) = (\frac{x}{2}; \frac{y}{2}) + (\frac{1}{4}; \frac{\sqrt{3}}{4})$, złożenie jednokładności o skali $0,5$ i przesunięcia na ukos, w prawo i do góry
Interesujące zbiory (fraktale) można otrzymać w następujący sposób: za pomocą odwzorowania Hutchinsona tworzymy rekurencyjnie
zdefiniowany ciąg zbiorów (2): zbiór $A_0$ wybieramy dowolnie, $A_{n+1} = H(A_n)$ dla $n \gt 0$.
Za pomocą komputera możemy narysować zbiory z tego ciągu, fraktalem będzie zbiór „graniczny”, ale czy ten ciąg ma granicę i co to znaczy że ciąg zbiorów ma granicę?
Mówimy że ciąg zbiorów $A_0,\,A_1, \ldots$ jest zbieżny do zbioru $G$, jeśli ciąg „odległości” zbiorów $A_n$ od zbioru $G$ dąży do zera. Pozostaje zdefiniować odległość zbiorów.
Podana niżej definicja należy do Felixa Hausdorffa.
Jeśli $A \subset \mathbb{R}^2$ oraz $r \gt 0$, to $A_r$ oznaczać będzie „nadmuchany” zbiór $A$, tzn. sumę wszystkich kół o promieniu $r$ i środku należącym do zbioru $A$.
Z bardzo ogólnego twierdzenia zwanego Twierdzeniem Banacha o odwzorowaniu zbliżającym wynika że jeśli każde z odwzorowań afinicznych $f_i$ użytych do zbudowania odwzorowania Hutchinsona $H$ jest zbliżające, tzn. istnieje liczba $c \lt 1$ taka, że dla dowolnych punktów $P,Q \in \mathbb{R}^2$ i dla każdego odwzorowania $f_i$ zachodzi nierówność $d(f_i(P),f_i(Q)) \le c\cdot d(P,Q)$ to ciąg (2) jest zbieżny. Co więcej granica $G$ tego ciągu zbiorów nie zależy od wyboru zbioru $A_0$, oraz $H(G) = G$. Będziemy ten zbiór graniczny nazywać atraktorem odwzorowania Hutchinsona.
W praktyce do rysowania zbioru granicznego (dokładniej przybliżeń tego zbioru) stosuje się algorytm probabilistyczny: wybieramy liczby dodatnie (prawdopodobieństwa) $p_1,\, \ldots ,\,p_k$
tak by $p_1 + \ldots + p_k = 1$, wybieramy punkt startowy $P_0$, tworzymy rekurencyjnie ciąg punktów płaszczyzny – jeśli mamy już punkty $P_0,\,\ldots,\,P_n$, to losujemy
(zgodnie z prawdopodobieństwami $p_i$) jedno z odwzorowań $f_j$ i definiujemy $P_{n+1} = f_j(P_n)$.
Jeśli któryś z punktów tego ciągu należy do atraktora, to wszystkie dalsze punkty również należą do atraktora. Można udowodnić (bardzo zaawansowna matematyka), że z prawdopodobieństwem $1$
wyrazy ciągu $(P_n)_{n \in \mathbb{N}}$ trafią do atraktora i będą go wypełniać w sposób gęsty. Na opisane wyżej zjawisko nie mają wpływu wybrane prawdopodobieństwa –
mają one wpływ na szybkość wypełniania atraktora przez ciąg punktów. Aby uniknąć na rysunku punktów spoza atraktora, warto jako punkt startowy $P_0$ wybrać punkt należący do atraktora.
Taki punkt łatwo znaleźć, będzie nim dowolne rozwiązanie jednego z równań $f_i(W) = W,\,\,1 \le i \le k$.
Plik Hutchinson.zip zawiera program rysujący atraktory odwzorowań Hutchinsona.
Przykłady atraktorów odwzorowań Hutchinsona
Lewy rysunek to atraktor $A$, prawy to zbiór $H(A) = f_1(A) \cup \ldots \cup f_k(A)$ (podzbiory $f_i(A)$ narysowane są różnymi kolorami), poniżej jest rysunek z wzorami $f_i$ i użytymi prawdopodobieństwami.
Atraktor odwozrowania Hutchinsona może być zupełnie zwyczajnym zbiorem.
Rysunki zostały wykonany przy domyślnych kolorach i prawdopodobieństwach oraz zwiększonej ilości punktów ($10\, 000\, 000$ zamiast $1\, 000\, 000$).
Uruchamianie programu
Program napisany jest w Javie, do uruchomienia niezbędne jest zainstalowanie JRE (wersja ≥ 8), JRE można pobrać
stąd.
Link na stronie prowadzi do pliku zip. Ściągnięty plik zip należy rozpakować (w dowolnym katalogu), zawiera on plik Hutchinson.jar i katalog resources z ikonami, plikami pomocy i plikiem konfiguracyjnym.
W systemie Windows program można uruchomić podwójnym kliknięciem w plik jar.
Lista programów: