Ніч фракталів

Йшов вже останню годину цього воскресіння, я вже думав йти спати, але добрий sourcerer прислав мені картинку з мого занедбаного сайту, яку можна побачити нижче, і текст «красиво!». Ці картинки я малював років п'ять тому, з допомогою т. зв. алгоритму часу втечі, але для застосування даного алгоритму, потрібно вміти для заданого набору перетворень розбивати площину на регіони, тоді я не придумав, як це зробити, і більше до цього алгоритму не повертався. Але зараз я відразу зметикував, що робити, і написав Дімі: «Спочатку Random IFS, потім kNN, а потім Escape-Time Algorithm!»



Під рукою у мене був тільки старий нетбук, який мені дали друзі, поки мій ноутбук в ремонті. Діма мені ще щось говорив, я йому щось відповідав, але в мене вже в голові писався код, і я шукав на нетбуці хоч який-небудь компілятор або інтерпретатор і знайшов C++ Builder 6! Після цього я зрозумів, що ранок я зустріч наодинці з борландовским компілятором. Через п'ять годин я відправив Дімі нових картинок, але він, як нормальна людина, давно спав…





Отже, трошки формул. Уявімо, що у нас є кінцевий набір перетворень площини Ti: R2R2, i = 1, ..., k. Для довільного безлічі E визначимо T(E) = T1(E) ∪… ∪ Tk(E), тобто подіємо кожним перетворенням на безліч E, а результати об'єднаємо. Можна довести, що якщо відображення Ti були стискають, то послідовність E, T(E), T(T(E)),… зійдеться до деякого безлічі F для будь-якого непустого компактного E. Дана конструкція і відома як система итерируемых функцій.

Наприклад, якщо в якості непустого компакта взяти смайлик, і розглянути три перетворення, кожне з яких є композицією стиснення та зсуву в i-шу вершину правильного трикутника, то перші ітерації будуть виглядати так, а в межі вийде трикутник Серпінського:



Зазвичай замість прямого обчислення послідовності E, T(E), T(T(E)),… для побудови фракталів використовують т. зв. «гру в хаос», яка полягає в наступному. Виберемо довільну точку z0 на площині, далі виберемо випадково перетворення Ti1 і обчислимо z1= Ti1(z0), далі знову випадково виберемо Ti2 і обчислимо z1= Ti2(z0), і т. д. Можна показати, що все буде добре, і безліч отриманих точок буде в деякому сенсі наближати безліч F, визначене вище. На цей алгоритм я нижче буду посилатися як на Random IFS.

z = (0, 0)
for (i = 0; i < maxIterNum; ++i) {
cl = random([p1, ..., pk]) // pi -- ймовірність, з якою вибираємо перетворення Ti.
z = T[cl](z)
if (i > skipIterNum) { // Перших кілька ітерацій можуть бути досить далеко від атрактора.
draw(z)
}
}




Тепер саме час перейти до опису алгоритму часу утікання. Нехай у нас для початку є одне перетворення площині f. Для кожної точки z площині почнемо обчислювати послідовність f(z), f(f(z)), f(f(f(z))),… до тих пір поки або число ітерацій не перевищить деякого заданого числа N, або поки норма числа z не стане більше деякого числа B. Після цього колір точки вибираємо відповідно з кількістю вироблених ітерацій.

for (y = y1; y < y2; y += dy) {
for (x = x1; x < x2; x += dx) {
z = (x, y);
iter = 0;
while (iter < N && ||z|| < B) {
z = f(z)
iter += 1;
}
drawPixel((x, y), color(iter))
}
}

Якщо на час уявити що наша площина є комплексною, а перетворення f(z) дорівнює z2 + c, то в результаті роботи цього алгоритму ми отримаємо фрактальне безліч Жюлиа. Більш докладно про це можна прочитати в хабрастатье «Побудова безлічі Жюлиа» хабрапользователя mephistopheies.



Нехай тепер у нас є система итерируемых функцій, задана набором оборотних стискуючих перетворень площини T1, ..., Tk. Нехай F — це аттрактор цієї системи.

Додатково припустимо, що множина F можна розбити так, що Ti(F) ∩ Tj(F) = ∅, i != j (це припущення далеко не завжди виконується). Розіб'ємо всю площину R2 на шматки A1, ...., Ak так, що Ti(F) є підмножиною Ai для всіх i. Тепер визначимо функцію f(z) кусково: на множині Ai покладемо f(z) = Tk-1(z), i.

Наприклад, для трикутника Серпінського розглянемо таке розбиття (тут є невеликі проблеми з трьома точками, але закриємо на них очі).



А тепер найголовніше питання, що вийде, якщо алгоритм часу утікання застосувати до побудованої таким чином функції f?

Давайте подивимося:



Вийшов симпатичний такий трикутник Серпінського!

Виявляється, це не випадковість. Ще кілька прикладів:





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

А саме, спочатку з допомогою Random IFS генеруємо кілька тисяч точок, при цьому для кожної точки запам'ятовуємо номер перетворення, з допомогою якого вона була отримана. Потім під час роботи EscapeTimeAlgorithm для кожного пікселя визначаємо область, в яку він потрапляємо з допомогою 1NN.

Наприклад, для такої зірочки 1NN дає наступне розбиття на чотири шматки:



Збираючи разом, отримаємо:

points = RandomIFS(Ts)
classifier = kNN(points);
for (y = y1; y < y2; y += dy) {
for (x = x1; x < x2; x += dx) {
z = (x, y)
iter = 0
while (iter < maxIterNum && ||z|| < sqrdBound) {
cl = classifier.getClass(z);
z = T[cl].applyInvert(z);
iter += 1;
}
draw((x, y), color(iter))
}
}



Ще кілька картинок.









От і все. Наостанок два зауваження.

По-перше, уважний читач, можливо задався питанням, раз фрактали, які будуються за допомогою Random IFS, можна побудувати з допомогою алгоритму часу втечі, то можна безліч Жюлиа побудувати з допомогою Random IFS? Виявляється, можна, потрібно просто звернути відображення f(z) = z2 + c, згадавши, як витягується корінь з комплексного числа. (Правда при застосуванні цього методу для побудови зображень безлічі Жюлиа виникають великі труднощі.)

x = z0.re
y = z0.im
for (i = 0; i < N; ++i) {
x -= c.re;
y -= c.im;
len = sqrt(x*x + y*y);
ang = atan2(y, x);
if (rand() % 2 == 0) { // Тут потрібно що-небудь і цікавіше.
x = sqrt(len) * cos(ang / 2);
y = sqrt(len) * sin(ang / 2);
} else {
x = sqrt(len) * cos(ang / 2 + M_PI);
y = sqrt(len) * sin(ang / 2 + M_PI);
}
draw(x, y)
}



По-друге, у статті було розказано відбувається, якщо ви хочете дізнатися чому так відбувається, то рекомендую книгу M. Barnsley «Fractals Everywere».

(Миті вихідного коду можна знайти на гітхабі.)

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.