Atraktory odwzorowań Hutchinsona

Rysunek w głównym oknie programu nie ma nic wspólnego z odwzorowaniami Hutchinsona, ma natomiast drobny związek z Hutchinsonem. Otóż John E. Hutchinson jest matematykiem australijskim, rysunek natomiast przedstawia skałę Uluru (Ayers Rock) – położoną w północnej Austalii świetą górę Aborygenów.

Definicja odwzorowania Hutchinsona i jego atraktora

Dziedziną każdego odwzorowania Hutchinsona jest rodzina $\Gamma$ wszystkich podzbiorów płaszczyzny.
Załóżmy, że odwzorowania $f_1, … ,f_k: \mathbb{R}^2\,\rightarrow\,\mathbb{R}^2$ są afiniczne. Wyznaczają one odwzorowanie Hutchinsona $H$ określone wzorem: $H(D)=f_1(A) \cup … \cup f_k(A)$ dla każdego zbioru $D \in \Gamma$.
Przykład:

$f_1(x,y) = (\frac{x}{2}, \frac{y}{2})$, jednokładność o skali $\frac{1}{2}$
$f_2(x,y) = (\frac{x}{2}, \frac{y}{2}) + (\frac{1}{2}, 0)$, złożenie jednokładności o skali $\frac{1}{2}$ i przesunięcia w prawo
$f_3(x,y) = (\frac{x}{2}, \frac{y}{2}) + (\frac{1}{4}, \sqrt{\frac{3}{4}})$, złożenie jednokładności o skali $\frac{1}{2}$ i przesunięcia w prawo do góry

Mając odwzorowanie Hutchinsona $H$ oraz zbiór $D_0 \in \Gamma$ możemy skonstruować ciąg zbiorów:
$D_1 = H(D_0), … ,D_{n+1} = H(D_n),…$
Zastąpimy rodzinę $\Gamma$ wszystkich podzbiorów płaszczyzny, rodziną $\Delta$ zwartych (tzn. domkniętych i ograniczonych) podzbiorów płaszczyzny. Jeśli zbiór $D \in \Delta$, to również zbiór $H(D) \in \Delta$.
Rodzinę $\Delta$ możemy wyposażyć w metrykę (tzw. metryka Hausdorffa), możemy zatem pytać o zbieżność ciągu zbiorów: $D_0,\,D_1=H(D_0),\,D_2=H(D_1),…$
Można pokazać, (Twierdzenie o odwzorowaniu zbliżającym), że przy pewnych założeniach o odwzorowaniach afinicznych $f_1,…,f_k$ (założenia te są spełnione przez odwzorowania z powyższego przykładu):

ciąg zbiorów $D_0, D_1=H(D_0),…$ jest zbieżny
granica $A$ powyższego ciągu nie zależy od wyboru pierwszego zbioru $D_0$
zbiór graniczny $A$ spełnia równanie $H(A)=A$

Opisany wyżej zbiór A nazywamy atraktorem odwzorowania Hutchinsona.
Dla odwzorowania Hutchinsona opisanego w przykładzie atraktorem jest równoboczny trójkąt Sierpińskiego.

Algorytm

Rysowanie atraktora odwzorowania Hutchinsona jako granicy ciągu zbiorów wymaga dużo zasobów komputera (pamięć i liczba wykonywanych operacji). W praktyce (w tym programie również) stosowany jest algorytm probabilistyczny:

Wybieramy liczby dodatnie $p_1,…,p_k$ takie, że $p_1+…+p_k=1$ (prawdopodobieństwa).
Wybieramy punkt startowy $x_0$ (najlepiej wybrać punkt $x_0$ należący do rysowanego atraktora p.6).
Wybieramy liczbę naturalną $m$.
Tworzymy rekurencyjnie ciąg punktów: $x_0,x_1,…,x_m$ – jeśli punkty $x_0,…,x_k$ są już skonstruowane, to losujemy (korzystając z wybranych prawdopodbieństw) jedno z odwzorowań afinicznych $f_i,\, x_{k+1}=f_i(x_k)$.
Korzystając z teorii ergodycznej można udowodnić:
- Otrzymany ciąg trafi (z prawdopodobieństwem 1) do atraktora. Jeśli punkt startowy $x_0$ należy do atraktora, to cały utworzony ciąg należy do atraktora – dowód tego faktu nie wymaga teorii ergodycznej.
- Utworzony ciąg (nieskończony) wypełni atraktor w sposób gęsty.

Opis programu

Przy pomocy programu można:

Rysować atraktory odwzorowań Hutchinsona opisanych w plikach Atractors.xml. Program szuka tych plików w dwóch katalogach:
1. «katalog_zawierający_program»/resources
2. «konto_użytkownika»/AppData/Local/bs/hutchinson
Projektować własne odwzorowania Hutchinsona. Te zaprojektowane odwzorowania zostaną dopisane do pliku Atractors.xml z katalogu opisanego w punkcie 2. Program zatroszczy się o zapisanie odwzorowania Hutchinsona w wymaganej formie – niestety nie zastosuje wymaganej niekiedy sekcji CDATA, użycie tej sekcji można wymusić.

Dołączony do programu plik resources/Atractors.xml zawiera opisy siedmiu atraktorów: trójkąt Sierpińskiego, drzewo, paprotka Barnsleya, kryształek, pięciokąt Sierpińskiego, smok Heighwaya i kwadrat. Programem można te opisy częściowo edytować:

można zmienić kolor domyślny
można zmienić zawartość elementu Limits, program wyliczy nowe wartości ograniczeń korzystając z liczby wpisanej do pola Liczba prób

Opisy zawarte w pliku konto_użytkownika/Atractors.xml można w pełni edytować, można je też programowo usuwać.

Budowa pliku Atractors.xml

Przykładowy plik:

<?xml version="1.0" encoding="ISO-8859-2"?>
<Atractors>
  <Atractor>
    <Title>Trójkąt Sierpińskiego</Title>
    <Limits></Limits>
    <Color>#ff0000</Color>
    <Map>
      <Matrix>0.5;0.0;0.0;0.0;0.5;0.0</Matrix>
      <Probability>0.333</Probability>
    </Map>
    <Map>
      <Matrix>0.5;0.0;0.5;0.0;0.5;0.0</Matrix>
      <Probability>0.333</Probability>
    </Map>
    <Map>
      <Matrix>0.5;0.0;0.5;0.0;0.5;0.5</Matrix>
      <Probability>0.333</Probability>
    </Map>
  </Atractor>
</Atractors>

Pewne polskie litery wymagają bardziej skomplikowanego zapisu:


    <Title><![CDATA[Śnieżynka]]></Title>

Elementów <Atractor> może być więcej.
Zapis <Limits>0.05;0.44;0;1.11 oznacza że punkty (x,y) należące do atraktora spełniają nierówności:
$\begin{cases} 0.05 \le x \le 0.44\\ 0 \le y \le 1.11\end{cases}$
Nierówności te są wykorzystywane przy skalowaniu rysunku.
Element <Matrix> opisuje jedno przekształcenie afiniczne. Zapis <Matrix>0.5;0.0;0.5;0.0;0.5;0.5</Matrix> oznacza przekształcenie
$f(x,y) = (0.5\cdot x + 0\cdot y + 0.5,\, 0\cdot x + 0.5\cdot y + 0.5)$.