Wyprodukujemy dziś paproć Barnsleya. Zbiór Cantora, który omawiałem w poprzedniej notce, choć klasyczny nie jest wizualnie zbyt interesujący. Paproć to co innego – trochę zadziwia. Zbiór Cantora to zbiór na linii prostej. Fraktal mniej niż jedno-wymiarowy. Paproć Barnsleya to fraktal płaski. Jaki ma wymiar? To zależy od detali, bo odmian paproci jest wiele. W każdym razie więcej niż 1 a mniej niż 2. W kolejnych notkach nauczymy się te wymiary szacować.
Zasada produkcji paproci (jak i innych podobnych fraktali) jest prosta i podobna do zasady produkcji zbioru Cantora. Mamy kilka transformacji działających na punkty płaszczyzny. Ważne by te transformacje były ze sobą nieprzemienne. Transformacje te winny być zwężające (skracające) – to znaczy każda z nich winna zmniejszać odległość pomiędzy punktami. Wybieramy jakiś punkt płaszczyzny i losowo działamy na ten punkt naszymi transformacjami. Przyglądamy się otrzymywanym w ten sposób punktom. Najlepiej zobaczyć to na przykładzie, i takim przykładem się dziś zajmiemy. Nasze transformacje będę, w tym przypadku, transformacjami afinicznymi.
Transformacje afiniczne.
Oznaczmy przez x punkt na płaszczyźnie. Punkt można utożsamić z wektorem wodzącym tzn. z wektorem wychodzącym z początku układu współrzędnych i kończącym się w punkcie x. Punkt, czy wektor, ma dwie składowe: x = (x1,x2). Przyzwyczailiśmy się od szkoły używać współrzędnych (x,y,z). Czasem jednak wygodnie jest oznaczać je przez x1,x2,x3. Tak też będę robił.
Przekształcenie afiniczne to przekształcenie postaci x → ax + b, gdzie a jest macierzą zaś b wektorem. W przypadku płaszczyzny a jest macierzą o 2 wierszach i dwóch kolumnach. Zapisujemy ją jako
[a11 a12]
[a21 a22]
lub w jednym wierszu:
a = [[a11,a12],[a21,a22]].
Wektor b ma dwie składowe. Można myśleć o nim jako o macierzy o dwóch wierszach i jednej kolumnie:
[b1]
[b2]
Czasem, dla wygody zapisu, piszemy ten wektor cały poziomo - jeden wiersz, dwie kolumny
b = [b1,b2].
I takiego zapisu będę też używał.
Przekształcenie afiniczne x → ax + b można rozpisać na składowe. Niech x' = ax + b. Oznacza to:
x'1 = a11 x1 + a12 x2 + b1
x'2 = a21 x1 + a22 x2 + b2
Tak więc przekształcenie afiniczne ma dwa składniki: część liniową x → ax, po czym następuje przesunięcie o wektor b. Część liniowa, zadawana macierzą, obraca wokół początku układu współrzędnych oraz ściska lub rozszerza. W jednym kierunkach może ściskać, w innym rozszerzać.
Przesunięcie natomiast ani nie ściska ani nie rozszerza. Po prostu przesuwa. Najlepiej zobzczyć to na przykładzie. Niechaj więc
a = [[0.81, 0.07], [-0.04, 0.84]],
b = [0.12,0.195].
Co robi nasze przekształcenie afiniczne zadane przez te a i b? Przyjrzyjmy się temu co robi z okręgiem jednostkowym.
Krzywa czerwona to wynik działania części liniowej na początkowy okrąg niebieski. Krzywa zielona to wynik działania pełnego przekształcenia, wraz z przesunięciem. Gołym okiem trudno zobaczyć deformację okręgu spowodowaną działaniem macierzy. Jednak krzywa czerwona jest w samej rzeczy elipsą. (Jej główne osie można znaleźć znajdując wektory własne macierzy
ata, gdzieatjest macierzą transponowaną do macierzy a). Popatrzmy jeszcze co robi nasze przekształcenie z kwadratem jednostkowym. Kwadrat przechodzi w równoległobok:
Nasza przykładowa transformacja zmniejsza pola powierzchni. Mówi nam o tym wyznacznik macierzy a, który jest mniejszy od jedynki:
det(a) = a11 a22 – a12 a21 = 0.6832
Paproć Barnsleya
Wybierzemy cztery transformacje afiniczne. (a1,b1,a2,b2,a3,b3,a4,b4). Niechaj będą to (przykładowo):
a1 = [[0.81, 0.07], [-0.04, 0.84]]
b1 = [0.12, 0.195]
a2 = [[0.18, -0.25], [0.277, 0.28]]
b2 = [0.12, 0.02]
a3 = [[0.19, 0.275], [0.238, -0.14]]
b3 = [0.16, 0.12]
a4 = [[0.0235, 0.087], [0.045, 0.166]]
b4 = [0.11, 0]
Oto ilustracja wyników ich działania na kwadrat jednostkowy:
Równoległobok niebieski już znamy. Ten żółty pochodzi od transformacji drugiej, szarawy od trzeciej, ale gdzie jest wynik transformacji czwartej? Transformacja czwarta jest silnie zwężająca. Wyznacznik macierzy a4 jest równy 0.000014. Kwadrat ściągany jest niemal do odcinka. Na obrazku ten odcinek można zobaczyć w kolorze czarnym. Ten „prawie odcinek” jest dla naszej paproci niesłychanie ważny. To on będzie decydował o łodydze liścia paproci. W sieci i w literaturze można znaleźć różne wersje macierzy prowadzących do paproci. W wielu wersjach czwarta transformacja jest osobliwa, macierz a4 ma wyznacznik równy 0 – mamy naprawdę odcinek. U mnie jest bardzo przydeptany równoległobok. Z obrazka widać, że niektóre transformacje wyprowadzają poza kwadrat jednostkowy, inne nie. Jeśli jednak miast kwadratu wybierzemy prostokąt o bokach (na przykład):
[[-3.6266501650165033, -1.9157004950495053}, [-3.6266501650165033,
8.37541254125412}, [3.7172572520409966,
8.37541254125412], [3.7172572520409966, -1.9157004950495053]]
wtedy okaże się, że żadna z naszych transformacji poza ten prostokąt nie wyprowadza.
Na obrazku powyższym, obok ukośnie w prawo w górę biegnącego prawie-odcinka (wyniku działania czwartej transformacji na okalający obrazek prostokąt) widać zielona plamkę – to liść paproci. Skąd się tam wziął? Jak powstał?
Ten liść to wynik działania algorytmu – w tym przypadku algorytmu losowego. Za punkt wyjścia biorę początek układu współrzędnych, punkt x = [0,0]. Następnie losuję jedną z czterech naszych transformacji i działam na x. Dostaję inne x. To x maluję kropką na ekranie. Znów losuję, działam wylosowaną transformacją na poprzednio otrzymane x, dostaję kolejną kropkę. I tak dalej. Ile razy?
100,1000,10000, …. Nic mnie nie kosztowało zrobić to milion razy. Czym więcej – tym więcej szczegółów pojawia się na obrazku. Za wiele – może być niedobrze, bo szczegóły mogą się pozamazywać ze względu na taką a nie inną rozdzielczość ekranu komputera i precyzję obliczeń.
Oto wynik po losowym zadziałaniu milionem losowo wybieranych transformacji. Ale uwaga: każda kolejna transformacja działa na wynik poprzedniej. Paproć Barnsleya w całej okazałości:
Podobieństwo do naturalnego kształtu jest zdumiewające. Pozostaje jeszcze do wyjaśnienia co to znaczy losowo? Są różne metody. Można sobie próbować. Można losować każdą transformację z równym prawdopodobieństwem – równym 1/4, bo są cztery transformacje. Sam Barnsley – autor pomysłu – proponował by prawdopodobieństwa wybierać w zależności od wartości wyznacznika.
Gdy te wyznaczniki wynoszą d1,d2,d3,d4, wtedy należy transformacjom przypisać prawdopodobieństwa p1 = d1/d, p2 = d2/d, p3 = d3/d, p4 = d4/d, gdzie d = d1+d2+d3+d4.
Gdy wyznacznik równy jest zero – należy wybierać „bardzo małe, lecz różne od zera prawdopodobieństwo”. Ja proponuję inną regułę. Ponieważ paproć leży na płaszczyźnie, proponuję zamiast d1,d2,d3,d4 brać nie wyznaczniki a pierwiastki kwadratowe z wyznaczników. Dla tworów przestrzennych wziąłbym trzecie pierwiastki, itd. I tak narysowałem mój liść. Wybór prawdopodobieństw nie ma tu wpływu na sam kształt otrzymanego obrazka, ma jednak wpływ na rozkład gęstości punktów – na „cieniowanie”, na „miarę”. Ale o miarach będziemy dyskutować w przyszłych notkach.
