Множество Мандельброта
Для построения графического изображения множества Мандельброта можно использовать алгоритм, называемый escape-time.
Суть его в том, что все множество полностью расположено внутри круга радиуса 2 на плоскости.
Чтобы определить, принадлежит ли конкретная точка множеству, выполняется заданное количество итераций приведенной ниже формулы:
Если после всех проведенных итераций ее значение не вышло за пределы заданного круга, то точка принадлежит множеству Мандельброта и поэтому краситься в черный цвет.
Если же точка покинула установленные границы, то с помощью номера итерации, на которой это произошло, устанавливается цвет, чтобы показать скорость ее «побега».
Эту последовательность действий необходимо проделать с каждой точкой на плоскости.
Чтобы получить полное представление о таком множестве, нужно выполнить огромное количество вычислений — сотни, тысячи, миллионы. Вручную это сделать было бы крайне затруднительно.
Поэтому нам, как и в свое время Бенуа Мандельброту, необходимо реализовать программу для этих целей.
Очертим границы комплексной плоскости, где будет изображено множество Мандельброта:
min.re = -2.0;
max.re = 2.0;
min.im = -2.0;
max.im = min.im + (max.re - min.re) * HEIGHT / WIDTH;С помощью приведенных выше строк определяется, что минимальная действительная часть комплексных чисел (то есть левая граница изображения) равна -2.0, а максимальная (то есть правая граница) равна 2.0.
Таким же образом определяется минимальная мнимая часть. А максимальная рассчитывается на основе размеров окна, чтобы избежать искажения изображения.
Также необходимо рассчитать связь между комплексными числами и пикселями на экране.
factor.re = (max.re - min.re) / (WIDTH - 1);
factor.im = (max.im - min.im) / (HEIGHT - 1); c.re = min.re + x * factor.re;
c.im = max.im - y * factor.im;Как можно заметить c.im считается особым образом. Это происходит по причине того, что ось y в окне программы направлена сверху вниз, а не снизу вверх как мы привыкли.
Кроме уже сделанных расчетов, необходимо установить еще и количество итераций:
max_iteration = 50;Чем больше будет указанное число, тем точнее будет полученное изображение фрактала. И тем больше вычислительных задач ляжет на компьютер.
Поэтому при установке данной переменной необходимо найти баланс между двумя возможными крайностями.
На данный момент основная часть программы выглядит вот так:
min.re = -2.0;
max.re = 2.0;
min.im = -2.0;
max.im = min.im + (max.re - min.re) * HEIGHT / WIDTH;
factor.re = (max.re - min.re) / (WIDTH - 1);
factor.im = (max.im - min.im) / (HEIGHT - 1);
max_iteration = 50;
y = 0;
while (y < HEIGHT)
{
c.im = max.im - y * factor.im;
x = 0;
while (x < WIDTH)
{
c.re = min.re + x * factor.re;
// Формула множества Мандельброта
// Установка цвета точки
x++;
}
y++;
}Поскольку инициализацию комплексного числа нам предстоит выполнять довольно часто, стоит написать функцию для этих целей:
t_complex init_complex(double re, double im)
{
t_complex complex;
complex.re = re;
complex.im = im;
return (complex);
}Пока преимущества такой функции не очевидны, но во время написания формулы самого множества она нам очень пригодится:
min = init_complex(-2.0, -2.0);
max.re = 2.0;
max.im = min.im + (max.re - min.re) * HEIGHT / WIDTH;
factor = init_complex(
(max.re - min.re) / (WIDTH - 1),
(max.im - min.im) / (HEIGHT - 1));
max_iteration = 50;
y = 0;
while (y < HEIGHT)
{
c.im = max.im - y * factor.im;
x = 0;
while (x < WIDTH)
{
c.re = min.re + x * factor.re;
// Формула множества Мандельброта
// Установка цвета точки
x++;
}
y++;
}На месте первого комментария нам необходимо записать уже упомянутую формулу множества Мандельброта, а также описанное выше ограничение в виде круга радиусом 2.
С инициализацией переменной z все очень просто:
z = init_complex(c.re, c.im);Определить принадлежит ли точка кругу, если его центр совпадает с началом координат, можно с помощью этой несложной формулы:
Также ее можно записать в следующем виде:
.svg)
Если значение приведенного выражения истинно, то точка с координатами (x, y) принадлежит окружности с радиусом r.
С этими знаниями мы можем дополнить существующий код:
y = 0;
while (y < HEIGHT)
{
c.im = max.im - y * factor.im;
x = 0;
while (x < WIDTH)
{
c.re = min.re + x * factor.re;
z = init_complex(c.re, c.im);
iteration = 0;
while (pow(z.re, 2.0) + pow(z.im, 2.0) <= 4
&& iteration < max_iteration)
{
// Формула множества Мандельброта
iteration++;
}
// Установка цвета точки
x++;
}
y++;
}Осталось только записать саму формулу множества Мандельброта и программа почти готова.
Вот только как перенести следующую формулу в код:
Добавить одно комплексное число к другому очень просто. Реальную часть к реальной. Мнимую к мнимой. Готово.
Но умножение, как и возведение в степень, более сложный процесс:
Действительная часть получившегося числа:
Его мнимая часть:
В коде формула Мандельброта будет записана в следующей форме:
y = 0;
while (y < HEIGHT)
{
c.im = max.im - y * factor.im;
x = 0;
while (x < WIDTH)
{
c.re = min.re + x * factor.re;
z = init_complex(c.re, c.im);
iteration = 0;
while (pow(z.re, 2.0) + pow(z.im, 2.0) <= 4
&& iteration < max_iteration)
{
z = init_complex(
pow(z.re, 2.0) - pow(z.im, 2.0) + c.re,
2.0 * z.re * z.im + c.im);
iteration++;
}
// Установка цвета точки
x++;
}
y++;
}Формула фрактала перенесена в код. Осталось лишь ознакомиться с фрагментом кода, отвечающим за выбор цвета в зависимости от количества выполненных итераций:
t = (double)iteration / (double)max_iteration;
red = (int)(9 * (1 - t) * pow(t, 3) * 255);
green = (int)(15 * pow((1 - t), 2) * pow(t, 2) * 255);
blue = (int)(8.5 * pow((1 - t), 3) * t * 255);