Фрактали та їх реалізація в середовищі Python

Фрактали

 

Загальні відомості про фрактали

Розгалуження трубочок трахей, листя на деревах, вени в руці, річка, що вирує і згинається, ринок цінних паперів - це все фрактали. Від представників древніх цивілізацій до Майкла Джексона, вчені, математики та артисти, як і всі інші мешканці цієї планети, були зачаровані фракталами і застосовували в своїй роботі.

Перші приклади самоподібних множин з незвичайними властивостями з'явилися в XIX столітті (наприклад, множина Контора).

Термін "фрактал" був введений Бенуа Мандельбротом в 1975 році і отримав широку популярність з виходом в 1977 році його книги "Фрактальна геометрія природи".

Програмісти і фахівці в області комп'ютерної техніки так само в захопленні від фракталів, так як фрактали нескінченної складності і краси можуть бути згенеровані простими формулами на простих домашніх комп'ютерах. Відкриття фракталів було відкриттям нової естетики мистецтва, науки і математики, а так само революцією в людському сприйнятті світу.

 

Фрактал (лат. Fractus - подрібнений, зламаний, розбитий) - складна геометрична фігура, що володіє властивістю самоподібності, тобто складена з декількох частин, кожна з яких подібна до всієї фігури цілком.

Всі фрактали подібні самим собі, тобто вони схожі на всіх рівнях.

 

Однак фрактали - не просто складні фігури, згенеровані комп'ютерами. Все, що здається випадковим і неправильним може бути фракталом. Теоретично, можна сказати, що все що існує в реальному світі є фракталом, будь то хмара або маленька молекула кисню.

Природні об'єкти, що володіють фрактальними властивостями

Передній вид на трахею і бронхи

Природні об'єкти (квазіфрактали) відрізняються від ідеальних абстрактних фракталів неповнотою і неточністю повторень структури. Більшість зустрічаються в природі фракталоподібних структур (межі хмар, лінія берега, дерева, листя рослин, корали, ...) є квазіфракталамі, оскільки на деякому малому масштабі фрактальна структура зникає. Природні структури не можуть бути ідеальними фракталами через обмеження, що накладаються розмірами живої клітини і, в кінцевому підсумку, розмірами молекул.

 

У живій природі:

        Корали

        Морські зірки і їжаки

        Морські раковини

        Квіти і рослини (брокколі, капуста)

        Крони дерев і листя рослин

        Плоди (ананас)

        Система кровообігу і бронхи людей і тварин

 

У неживій природі:

        Межі географічних об'єктів (країн, областей, міст)

        Берегові лінії

        Гірські хребти

        Сніжинки

        Хмари

        Блискавки

        Морозні візерунки на шибках

        Кристали

        Сталактити, сталагміти, геліктити.

        Радіотехніка

        Фрактальні антени

        Інформатика

        Стиснення зображень

        Візуалізація рекурсії

У попередніх розділах ми розглядали завдання, які можуть бути легко вирішені за допомогою рекурсії. Однак, знайти ментальну модель або спосіб візуалізації того, що відбувається з рекурсивної функцією, як і раніше непросто. Це робить рекурсію важкою для розуміння. Тому в цій частині ми розглянемо кілька прикладів використання рекурсії для малювання деяких цікавих зображень. В процесі "промальовування" цих картинок ви отримаєте нове розуміння рекурсивних процесів, що може бути корисним для закріплення вашого розуміння рекурсії в цілому.

 

Для наших ілюстрацій ми скористаємося графічним модулем Python під назвою turtle. Він входить в стандартний набір модулів для всіх версій Python і дуже простий в застосуванні. Метафора, що пояснює його назву (turtle (англ.) - черепаха) вкрай проста: ви можете створити черепаху, яка вміє рухатися вперед-назад, повертати направо-наліво і т.п. У неї є хвіст, який вона може піднімати або опускати. Коли черепашачий хвіст опущений і вона рухається, то він малює лінію. Щоб збільшити художню цінність черепахи, ви можете змінювати товщину хвоста і колір чорнила, в які він був пофарбований.

 

Ось простий приклад, який показує основи "черепашачого малювання". Ми використовуємо модуль turtle, щоб рекурсивно намалювати спіраль.

ActiveCode 1 показує, як це робиться. Після підключення модуля turtle створюється черепаха, разом з якою з'являється і вікно для малювання. Потім ми визначаємо функцію drawSpiral. Її базовим випадком буде момент, коли довжина лінії, яку ми хочемо намалювати (параметр len), стане меншою або рівною нулю. Якщо ж вона більше нуля, то ми даємо черепасі завдання пройти len одиниць, а потім повернути на 90 градусів. Рекурсивним кроком буде виклик drawSpiral зі зменшеною довжиною.

В кінці ActiveCode 1 ви побачите виклик функції myWin.exitonclick (). Вона управляє маленьким віконним методом, який переводить черепаху в режим очікування до тих пір, поки ви не клікнете всередині вікна. Після цього програма очистить полотно і закриється.

 

# Приклад 1

import turtle

 

myTurtle = turtle.Turtle()

myWin = turtle.Screen()

 

def drawSpiral(myTurtle, lineLen):

    myTurtle.color("red")

    myTurtle.width(2)

    if lineLen > 0:

        myTurtle.forward(lineLen)

        myTurtle.right(90)

        drawSpiral(myTurtle,lineLen-8)

 

drawSpiral(myTurtle,180)

myWin.exitonclick()

 

ActiveCode 1. Рекурсивне малювання спіралі з використанням черепахи.

 

 

 

Ось і все про "черепашачою графіку", що вам потрібно знати для малювання деяких досить вражаючих картинок. У нашій наступній програмі ми збираємося зобразити фрактальне дерево.

Фрактали - це одна з гілок математики, і вони мають з рекурсією багато спільного. Визначення фрактала полягає в тому, що незалежно від наближення він завжди містить деяку основну фігуру. Прикладами з живої природи можуть послужити берегові лінії континентів, сніжинки, гори і навіть дерева або чагарники. Фрактальна природа цих об'єктів дозволяє програмістам генерувати дуже реалістично виглядають пейзажі для комп'ютерних зображень. Та й ми в наступному прикладі будемо генерувати фрактальне дерево.

 

Щоб зрозуміти, як все це працює, корисно подумати над тим, як можна описати дерево, використовуючи термінологію фракталів. Згадайте, що ми говорили вище: фрактал - це те, що виглядає однаково на всіх рівнях збільшення. Транслюючи цю думку на дерева і чагарники, можна сказати, що навіть найменша гілочка має ту ж форму і характеристики, що й ціле дерево. Тобто можна сказати, що дерево - це стовбур від якого вправо і вліво відходять менші дерева.

 

Давайте переведемо ці думки в код на Python. Лістинг 1 демонструє, як можна використовувати нашу черепаху для генерації фрактального дерева. Подивимося на код ближче.

Добре видно, що рекурсивні виклики робляться в рядках 5 і 7. У рядку 5 відразу після нього черепаха повертає вправо на 20 градусів - це праве дерево. Потім в рядку 7 знову робиться рекурсивний виклик, але в цей раз з поворотом вліво на 40 градусів. Вибір цього числа пов'язаний з необхідністю компенсувати вже зроблений поворот на 20 градусів, а потім повернути ще на 20 вліво з метою намалювати ліве дерево. Також зверніть увагу, що при кожному рекурсивному виклику tree ми віднімаємо з параметра branchLen якусь величину. Це робиться для того, щоб рекурсивні дерева ставали все менше і менше. Ви також можете розібратися, що початковий оператор if в рядку 2 перевіряє базовий випадок: branchLen стала замалою.

 

# лістинг 1

1 def tree(branchLen, t):

2    if branchLen> 5:

3        t.forward (branchLen)

4        t.right (20)

5        tree (branchLen-15, t)

6        t.left (40)

7        tree (branchLen-10, t)

8        t.right (20)

9        t.backward (branchLen)

 

Повністю програма для прикладу з деревом показана в ActiveCode 2. До того, як ви запустите її, подумайте: як має виглядати дерево? Подивіться на рекурсивні виклики і уявіть, як воно буде розгортатися. Чи будуть його права і ліва частини малюватися симетрично і одночасно? Або спочатку вималюється права, а потім ліва половина?

 

# Приклад 2

import turtle

 

def tree(branchLen,t):

    if branchLen > 5:

        t.forward(branchLen)

        t.right(20)

        tree(branchLen-15,t)

        t.left(40)

        tree(branchLen-15,t)

        t.right(20)

        t.backward(branchLen)

 

def main():

    t = turtle.Turtle()

    myWin = turtle.Screen()

    t.left(90)

    t.up()

    t.backward(100)

    t.down()

    t.color("green")

    tree(75,t)

    myWin.exitonclick()

 

main()

 

Скриншот результату роботи програми:

 

ActiveCode 2. Рекурсивне малювання дерева (lst_complete_tree)

 

Зверніть увагу, як кожна точка розгалуження співвідноситься з рекурсивним викликом і як дерево промальовується вправо до найкоротшої гілочки.

Ви можете це побачити на малюнку 1.

А тепер подивіться, як програма працює в зворотному напрямку - до стовбура, - коли намальована вся права частина. Ви можете побачити праву половину дерева на малюнку 2. Потім малюється ліва сторона дерева, але не від самої лівої її частини. Замість цього знову промальовується права сторона лівого дерева, і так до тих пір, поки не буде створена найменша ліва гілка.

 

Малюнок 1: Початок фрактального дерева.

 

Малюнок 2: Перша половина фрактального дерева.

 Легко помітити, що дерево не виглядає особливо реалістичним, оскільки природа не настільки симетрична, як комп'ютерні програми.

 

 

Запитання

1. Хто і коли вперше ввів термін "фрактал" ?

2. Що таке фрактал ?

3.Які природні об'єкти мають фрактальні властивості ?

4. Які об'єкти в неживій пророді мають фрактальні властивості ?

5. Де використовують фрактали в науці і техніці ?

6. Який модуль мови програмування Python використовують для побудови фракталів ?

7. Як називають функції, які пов'язані з фракталами ?

 

Завдання

1. Виконати код побудови фрактального дерева

from turtle import*

lt(90)

color("green")

def fr(w):

    if w >= 1:

        pensize(w)

        fd(w * 10)

        rt(30)

        fr(w * 0.75)

        lt(60)

        fr(w * 0.75)

        rt(30)

        bk(w * 10)

        pensize(w)

speed(10)

hideturtle()

penup()

goto(0, -200)

pendown()

fr(10)

 

2. Виконати код побудови гілки папоротника

from turtle import*

def draw_partial_fern(t, size, angle, c1, c2):

    t.left(angle)

    draw_fern(t, size * c1)

    t.right(angle)

    t.backward(size * c2)

 

def draw_fern(t, size):

    if size > 1:

        t.forward(size)

        draw_partial_fern(t, size, 5, 0.8, 0.05)

        draw_partial_fern(t, size, -40, 0.45, 0.2)

        draw_partial_fern(t, size, 35, 0.4, 0.75)

 

def draw_art():

    window = Screen()

    fr = Turtle()

    fr.color("green")

    fr.speed(0)

    fr.hideturtle()

    fr.left(90)

    draw_fern(fr, 60)

    window.exitonclick()

 

draw_art()

 

3.  Виконати код побудови трикутника Серпинського

from turtle import*

def draw_sierpinski(length,depth):

    if depth==0:

        for i in range(0,3):

            t.fd(length)

            t.left(120)

    else:

        draw_sierpinski(length/2,depth-1)

        t.fd(length/2)

        draw_sierpinski(length/2,depth-1)

        t.bk(length/2)

        t.left(60)

        t.fd(length/2)

        t.right(60)

        draw_sierpinski(length/2,depth-1)

        t.left(60)

        t.bk(length/2)

        t.right(60)

 

window = Screen()

t = Turtle()

t.speed(10)

t.pensize(2)

t.penup()

t.goto(-200, -200)

t.pendown()

t.hideturtle()

draw_sierpinski(500,7)

window.exitonclick()

 

4. Виконайте код побудови фрактала Коха

from turtle import*

def koch(t, order, size):

    if order == 0:                

        t.forward(size)

    else:

        koch(t, order-1, size/2.7) 

        t.left(60)

        koch(t, order-1, size/2.7)

        t.right(120)

        koch(t, order-1, size/2.7)

        t.left(60)

        koch(t, order-1, size/2.7)

 

fr = Turtle()

wn = Screen()

fr.speed(10)

fr.penup()

fr.backward(150)

fr.pendown()

fr.hideturtle()

fr.pensize(2)

fr.penup()

fr.goto(-400, -100)

fr.pendown()

 

koch(fr, 5, 500)

wn.exitonclick()

 

Додаткові завдання*

Змініть програму для рекурсивного дерева, використовуючи одну з наступних ідей:

1. Змініть товщину гілок, щоб при зменшенні branchLen лінії ставали тоншими.

2. Змініть колір гілок таким чином, щоб самі кірок гілки забарвлювалися як листя.

3. Змініть кут повороту черепахи, щоб кожна гілка поверталася довільним чином в деякому діапазоні. Наприклад, вибирайте кут між 15-ю і 45-ю градусами. Поекспрериментуйте в пошуках кращого вигляду.

4. Змініть рекурсивную частина branchLen, щоб кожен раз віднімалося довільне значення з деякого діапазону замість якоїсь постійної величини.