Choć niektóre fraktale wydają się bardzo skomplikowane, ich konstrukcję można opisać w dość prosty sposób dzięki funkcjom IFSIFSIFS. Przyjrzyjmy się bliżej dwóm przykładom takich fraktali.
Smok Heighwaya
Z historią tego fraktala związanych jest wiele nazwisk. Pracowali nad nim naukowcy z NASA: John Heighway, Bruce Banks i William Harter, a opisany i spopularyzowany zastał przez Martina Gardnera w roku 1967. Był także przedmiotem badań Chandlera Davisa oraz Donalda Knutha (znanego z algorytmu Knutha-Morrisa‑Pratta), którzy odkryli wiele jego cech.
Generowanie tego fraktala opiera się na wykorzystaniu dwóch par funkcji, zgodnie z którymi obliczamy współrzędne kolejnych punktów. Te pary funkcji to:
Funkcji tych należy użyć w sposób losowy w równych proporcjach. Jest to metoda Monte Carlometoda Monte CarloMonte Carlo, polegająca na losowaniu dostatecznej liczby danych w taki sposób, że po ich zestawieniu otrzymujemy pewne przybliżenie modelowanego zjawiska. Punktem startowym jest punkt .
Każdy wygenerowany w ten sposób punkt rysujemy w układzie współrzędnych – kształt, który otrzymamy, jest nazywany smokiem Heighwaya. Im więcej punktów wygenerujemy, tym dokładniejszy będzie uzyskany kształt.
Wszystkie przedstawione kroki możemy zapisać za pomocą następującego pseudokodu:
Linia 1. prawy ukośnik prawy ukośnik punkt startowy.
Linia 2. x znak równości 0 przecinek 0.
Linia 3. y znak równości 0 przecinek 0.
Linia 5. prawy ukośnik prawy ukośnik liczba generowanych punktów.
Linia 6. n znak równości 10000.
Linia 8. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka n minus 1 wykonuj dwukropek.
Linia 9. prawy ukośnik prawy ukośnik kopia zmiennej x.
Linia 10. x0 znak równości x.
Linia 12. g znak równości losuj liczbę z otwórz nawias kwadratowy 0 przecinek 1 zamknij nawias kwadratowy.
Linia 14. jeżeli g znak równości znak równości 0 wykonaj dwukropek.
Linia 15. x znak równości 0 przecinek 5 asterysk x minus 0 przecinek 5 asterysk y.
Linia 16. y znak równości 0 przecinek 5 asterysk x0 plus 0 przecinek 5 asterysk y.
Linia 17. w przeciwnym razie wykonaj dwukropek.
Linia 18. x znak równości minus 0 przecinek 5 asterysk x minus 0 przecinek 5 asterysk y plus 1.
Linia 19. y znak równości 0 przecinek 5 asterysk x0 minus 0 przecinek 5 asterysk y.
Linia 21. rysuj punkt otwórz nawias okrągły x przecinek y zamknij nawias okrągły.
// punkt startowy
x = 0,0
y = 0,0
// liczba generowanych punktów
n = 10000
dla i = 0, 1, 2 ... n - 1 wykonuj:
// kopia zmiennej x
x0 = x
g = losuj liczbę z [0, 1]
jeżeli g == 0 wykonaj:
x = 0,5 * x - 0,5 * y
y = 0,5 * x0 + 0,5 * y
w przeciwnym razie wykonaj:
x = - 0,5 * x - 0,5 * y + 1
y = 0,5 * x0 - 0,5 * y
rysuj punkt (x, y)
Zwróćmy uwagę na fakt, że potrzebna jest nam kopia zmiennych x, aby podczas generowania zmiennej y (w linijce 19.) nie użyć nowej wartości nadanej zmiennej x.
R10tWEZwGAvSA
Ilustracja przedstawia zakrzywioną linię, która tworzona jest na podstawie kwadratu, ale nigdy go nie zamyka, jedynie przechodzi przez 4 rogi, tak aby następnie przejść do następnego fragmentu. W ten sposób tworzona wypełnia przestrzeń.
Smok Heighwaya
Źródło: William Sikkema, licencja: CC BY-SA 4.0.
Paproć Barnsleya
Odkrywcą tego fraktala jest Michael Barnsley, który opisał go w książce FractalsEverywhere. Publikacja ta stanowi obszerne kompendium wiedzy na temat fraktali, szczególnie jednak traktuje o generowaniu fraktali z wykorzystaniem funkcji IFS. Autor przedstawił w niej też smoka Heighwaya.
Stworzona przez Barnsleya definicja paproci opiera się na czterech przekształceniach afinicznych. Ponieważ jednak posługiwał się on skomplikowaną terminologią matematyczną (związaną z rachunkiem macierzy, funkcjami wielu zmiennych, liczbami zespolonymi oraz krzywymi hiperbolicznymi), przedstawiony przez nas sposób generowania paproci Barnsleya nie jest oryginalnym zapisem stosowanym przez autora.
Podobnie jak miało to miejsce w przypadku smoka Heighwaya, generowanie tego fraktala opiera się na wykorzystaniu pewnej liczby par funkcji, które należy stosować losowo w określonych proporcjach. W tym wypadku mamy cztery pary funkcji:
Funkcji tych należy użyć losowo według następujących proporcji:
Punktem startowym jest punkt .
Pseudokod, którym posłużymy się podczas pisania programu generującego paproć Barnsleya, może wyglądać następująco:
Linia 1. prawy ukośnik prawy ukośnik punkt startowy.
Linia 2. x znak równości 0 kropka 0.
Linia 3. y znak równości 0 kropka 0.
Linia 5. prawy ukośnik prawy ukośnik liczba generowanych punktów.
Linia 6. n znak równości 10000.
Linia 8. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka n minus 1 wykonuj dwukropek.
Linia 9. prawy ukośnik prawy ukośnik kopia zmiennej x.
Linia 10. x0 znak równości x.
Linia 12. g znak równości losuj liczbę z otwórz nawias kwadratowy 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 zamknij nawias kwadratowy.
Linia 14. jeżeli q otwórz nawias ostrokątny 1 wykonaj dwukropek.
Linia 15. x znak równości 0 średnik.
Linia 16. y znak równości 0 kropka 16 asterysk y średnik.
Linia 17. w przeciwnym razie jeżeli q otwórz nawias ostrokątny 86 wykonaj dwukropek.
Linia 18. x znak równości 0 kropka 85 asterysk x plus 0 kropka 04 asterysk y średnik.
Linia 19. y znak równości minus 0 kropka 04 asterysk x0 plus 0 kropka 85 asterysk y plus 1 kropka 6 średnik.
Linia 20. w przeciwnym razie jeżeli q otwórz nawias ostrokątny 93 wykonaj dwukropek.
Linia 21. x znak równości 0 kropka 2 asterysk x minus 0 kropka 26 asterysk y średnik.
Linia 22. y znak równości 0 kropka 23 asterysk x0 plus 0 kropka 22 asterysk y plus 1 kropka 6 średnik.
Linia 23. w przeciwnym razie wykonaj dwukropek.
Linia 24. x znak równości minus 0 kropka 15 asterysk x plus 0 kropka 28 asterysk y średnik.
Linia 25. y znak równości 0 kropka 26 asterysk x plus 0 kropka 24 asterysk y plus 0 kropka 44 średnik.
Linia 27. rysuj punkt otwórz nawias okrągły x przecinek y zamknij nawias okrągły.
// punkt startowy
x = 0.0
y = 0.0
// liczba generowanych punktów
n = 10000
dla i = 0, 1, 2 ... n-1 wykonuj:
// kopia zmiennej x
x0 = x
g = losuj liczbę z [0, 1, ..., 99]
jeżeli q < 1 wykonaj:
x = 0;
y = 0.16 * y;
w przeciwnym razie jeżeli q < 86 wykonaj:
x = 0.85 * x + 0.04 * y;
y = -0.04 * x0 + 0.85 * y + 1.6;
w przeciwnym razie jeżeli q < 93 wykonaj:
x = 0.2 * x - 0.26 * y;
y = 0.23 * x0 + 0.22 * y + 1.6;
w przeciwnym razie wykonaj:
x = -0.15 * x + 0.28 * y;
y = 0.26 * x + 0.24 * y + 0.44;
rysuj punkt (x, y)
W wyniku tworzenia paproci Barnsleya według pseudokodu możemy uzyskać na przykład taki kształt:
R18GjGseEJBIv
Ilustracja przedstwia liść paproci, którego każdy mniejszy listek to kolejny liść paproci, jedynie mniejszy. Liść zakrzywia się w prawo.
Źródło: Laug, licencja: CC BY-SA 4.0.
Słownik
IFS
IFS
(z ang. iterated function system – system funkcji iterowanych) funkcje, które pozwalają generować konstrukcje samopodobne
metoda Monte Carlo
metoda Monte Carlo
metoda modelowania zjawisk fizycznych lub matematycznych za pomocą losowania danych w określony sposób tak, aby ich zestawienie produkowało przybliżenie oczekiwanego rezultatu