Fraktale
Fraktal to figura geometryczna, którą można wygenerować z rekurencyjnego powtarzania wzorca (rysunek 18.12). Figura powstaje przez rekurencyjne stosowanie wzorca dla każdego segmentu pierwotnej figury. Choć tego rodzaju figury analizowano jeszcze przed XX wiekiem, dopiero matematyk Benoit Mandelbrot w latach siedemdziesiątych XX wieku użył terminu „fraktal”, opisując sposoby tworzenia fraktali i ich praktyczne zastosowania. Fraktale Mandelbrota zapewniają modele matematyczne dla wielu złożonych form znajdowanych w naturze, np. gór, chmur lub linii brzegowych. Fraktale mają wiele zastosowań w matematyce
i nauce. Można ich użyć do lepszego zrozumienia systemów i wzorów pojawiających się w naturze (np. ekosystemów), w ludzkim organizmie (np. fałdy w mózgu) lub we wszechświecie (np. gromady galaktyk). Nie wszystkie fraktale przypominają obiekty z natury. Rysowanie fraktali to popularna forma sztuki. Fraktale mają właściwość samopodobieństwa — po podzieleniu na mniejsze części
każda z nich jest pomniejszoną kopią całości. Wiele fraktali po powiększeniu tworzy dokładną kopię oryginału — taki fraktal nazywamy ściśle samopodobnym.
Fraktale - Krzywa Kocha
Przyjrzyjmy się przykładowi ściśle samopodobnego fraktala o nazwie krzywa Kocha (rysunek 18.12). Tworzy się go poprzez usunięcie środkowej części linii i zastąpienie jej dwiema liniami, które tworzą na środku trójkąt. Pozostałe dwa fragmenty nie ulegają modyfikacji. Wzory tworzące fraktale często wymagają usunięcia całości lub części wcześniejszego obrazu fraktala. Dla tego fraktala znamy wzorzec postępowania — skupmy się więc na utworzeniu wzoru wykonującego fraktal w sposób rekurencyjny.
Rysunek 18.12. Krzywa Kocha
Zaczynamy od linii prostej (rysunek 18.12a) i stosujemy wzorzec, tworząc trójkąt z części środkowej (rysunek 18.12b). Ponownie stosujemy ten sam wzorzec dla każdej linii prostej, uzyskując wynik z rysunku 18.12c. Po każdym zastosowaniu wzorca mówimy, że fraktal osiągnął nowy poziom (głębię). Fraktale można wyświetlać na wielu poziomach — fraktal z poziomu 3 ma zastosowane trzy iteracje wzorca (rysunek 18.12d). Już po kilku iteracjach fraktal zaczyna przypominać kawałek płatka śniegu (rysunki 18.12e i 18.12f). Ponieważ jest to fraktal ściśle samopodobny, każdy fragment zawiera dokładną kopię fraktala. Na rysunku 18.12f zaznaczyliśmy fragment linią przerywaną. Gdyby go powiększyć, wyglądałby dokładnie tak samo jak cały fraktal z części poprzedniej.
Bardzo podobny fraktal, płatek Kocha, wykonuje się w ten sam sposób co krzywą Kocha, ale zaczyna od trójkąta zamiast linii. Ten sam wzorzec stosuje się dla każdego boku trójkąta, co powoduje powstanie obrazu przypominającego płatek śniegu.
(Opcjonalnie) Studium przypadku — pióro Lo
Teraz pokażemy przykład zastosowania rekurencji do rysowania fraktali, tworząc program rysujący fraktal ściśle samopodobny. Fraktal ten nosi nazwę „pióro Lo”, bo wymyślił go Sin Han Lo, znajomy z Deitel & Associates. Fraktal w pewnym momencie przypomina połówkę pióra (rysunek 18.20). Przypadek bazowy, czyli fraktal na poziomie 0, zaczyna się jako linia między dwoma punktami A i B (rysunek 18.13). Aby przejść na następny poziom, znajdujemy środek linii (punkt C). Do obliczenia punktu C używamy wzoru:
yC = (yA + yB) / 2;
Rysunek 18.13. Pióro Lo na poziomie 0
(Uwaga: x i y na lewo od każdej litery to współrzędne x i y każdego punktu. Zmienna xA oznacza współrzędną x punktu A, natomiast yC oznacza współrzędną y punktu C. Na rysunkach współrzędne x i y są podane w nawiasach po literze oznaczającej punkt).
Aby utworzyć fraktal, musimy również znaleźć punkt D, który znajduje się na lewo i wyżej od punktów A i D, tworząc trójkąt równoramienny o wierzchołkach ACD. Do obliczenia punktu D używamy wzoru:
yD = yA + (yC - yA) / 2 + (xC - xA) / 2;
Przejdziemy teraz od poziomu 0 do poziomu 1. Najpierw dodajemy punkty C i D (rysunek 18.14). Potem usuwamy oryginalną linię i dodajemy segmenty DA, DC i DB. Uzyskane linie będą się zakrzywiały pod pewnym kątem, więc fraktal zacznie przypominać pióro.
Rysunek 18.14. Określanie punktów C i D dla pióra Lo na poziomie 1
Dla następnego poziomu fraktala algorytm powtarza się dla każdej z trzech linii z poziomu 1. Dla każdej linii stosuje się ten sam wzór co wcześniej, ale punkt D jest teraz traktowany jako punkt A, a drugi koniec linii jest traktowany jako punkt B. Rysunek 18.15 zawiera linię z poziomu 0 (teraz jako linia przerywana), a także trzy linie dodane z poziomu 1. Zmodyfikowaliśmy punkty i teraz
punkt D to punkt A, a pierwotne punkty A, C i B to odpowiednio B1, B2 i B3. Wcześniejsze wzory służą do znalezienia nowych punktów C i D dla każdej linii. Dodaliśmy do punktów numerację od 1 do 3, aby wskazać, który punkt jest powiązany z którą linią. Punkty C1 i D1 reprezentują na przykład punkty C i D powstałe na podstawie punktów A i B1.
Rysunek 18.15. Pióro Lo na poziomie 1 z punktami C i D określonymi dla poziomu 2 (Uwaga: Fraktal na poziomie 0
został pokazany jako linia przerywana dla przypomnienia pierwotnej wersji)
Aby osiągnąć poziom 2, trzy linie z rysunku 18.15 są usuwane i zastępowane nowymi liniami od właśnie dodanych punktów C i D. Rysunek 18.16 przedstawia nowe linie (linie z poziomu 1 są przedstawione jako linie przerywane).
Rysunek 18.16. Pióro Lo na poziomie 2 z liniami przerywanymi ilustrującymi poziom 1
Rysunek 18.17 przedstawia wersję poziomu 2 bez linii przerywanych z poziomu 1. Gdy cały proces powtórzymy jeszcze kilka razy, fraktal zacznie przypominać połówkę pióra, co pokazuje wynik z rysunku 18.20.
Rysunek 18.17. Pióro Lo na poziomie 2
