1. Введение
1.1. Множества Жюлиа
Будем рассматривать последовательности комплексных чисел
{Zn}.
Возьмем произвольное комплексное число c.
Теперь для любого комплексного числа k рассмотрим
последовательность
{Zn(k)}:
Z0 = k,
Zi+1= Zi2
+
c
Зададим себе вопрос: сходится ли Zn
к нулю или стремится к бесконечности при n стремящемся
к бесконечности? Пусть J – множество всех комплексных
чисел {k}, таких что {Zn(k)}стремится
к 0, при n стремящемся к бесконечности.
Если теперь мы возьмем все такие kи отобразим их на комплексной
плоскости, то получим множество Жюлиа. Меняя c,
мы получим бесконечный набор фантастических само подобных образов – множеств
Жюлиа.
1.2. Множество Мандельброта
Рассмотрим набор множеств Жюлиа и зададимся вопросом: связно
ли данное конкретное множество Жюлиа? Пусть M
– множество всех множеств Жюлиа, которые связны. Это множество и называется
множеством Мандельброта.
Теперь возьмем любое множество Жюлиа J,
и комплексное число c, которое его породило.
Если J содержится в M,
то изобразим точку черным на комплексной плоскости, в противном случае
белым. Это и дает нам того “своеобразного снеговика“, которого вы уже наверное
видели миллион раз. Его - то мы и будем генерировать.
К счастью, есть более легкий путь изображения множества
Мандельброта, чем рисование каждого множества Жюлия и выяснения, связно
ли оно. Наш метод будет очень близок к построению множеств Жюлиа. Опять
рассмотрим итерационную последовательность для любого k,
и выясним, сходится ли она к нулю.
Zi+1= Zi2
+ c
Заметим, что c здесь уже не константа.Для любой точки
комплексной плоскости мы c присваиваем значение k и
выполняем итерации. Этот метод, как ни странно, дает нам то же изображение
множества Мандельброта. Итак, алгоритм:
For each point kon the complex plane do:
let x=0.
repeat infinite times:
x=x2
+
k.
end repeat
if x goes to infinity,
k is not
in the set. Color is white.
else
k is in
the set. Color is black.
Понятно, что бесконечных циклов быть не должно. Поэтому
возьмем некоторое большое число I и проитерируем I раз. Чем большее I мы
взяли, тем, понятнее, точнее ответ мы получим. Из практики, число 4000
дает довольно хороший результат. Да, но 4000 раз “крутить“ цикл для каждого
пиксела изображения, это многовато. К счастью, мы можем воспользоваться
результатами многолетней работы математиков в этой области. Оказывается,
если в любой конкретный момент вычислений, для k расстояние от zi(k)
начала координат больше 2, то мы можем принять, что данная {Zn(k)}
уйдет в бесконечность (При сравнении: расстояние < 2, поэтому его квадрат
меньше 4 и корень извлекать не нужно). Итак, теперь наш алгоритм выглядит
так:
For each point k in the complex plane do:
let x=0.
repeat 4000 times
let x=x2+k
if x2
> 4 then
Color it white
Break.
end repeat
if we reached 4000 then
Color
it black.
Этот метод дает нам черно-белое изображение множества
Мандельброта. Теперь надо подумать о том, как сделать его разноцветным.
1.3. Цветное изображение
Если точка принадлежит множеству Мандельброта, то с ней все
ясно – рисуем ее черным. Но как быть с точками, не принадлежащими множеству?
Общепринятый способ выбора цвета для них – это выбирать цвет в соответствии
с тем, как быстро {Zn(k)} стремится
к бесконечности (на какой итерации мы ее исключаем из рассмотрения). Например,
точка, для которой расстояние до начала координат больше 2 уже на третьей
итерации, должна быть почти белой, а та точка, которая “продержалась“ до
3995 итерации – почти черной. Перепишем алгоритм для изображения в градациях
серого:
For each point k in the complex plane do:
let x:=0.
for i:=0 to 4000
let x=x2+k
if ( |x|2>
4) then
Color point k color i
Break;
end if
end for
if (i=4000)
Color
point k black.
end if
Конечно, просто рисовать точку цветом i мы не можем.
Считая, что у нас есть только 256 градаций серого, а iменяется до
4000. Нам надо как-то отображать iна доступный нам диапазон цветов.
Эту проблему мы оставляем вам. После того, как мы получили приличное изображение
в градациях серого, очень легко чуть изменить алгоритм для получения цветного
изображения. Например, в изображении в градациях серого, если точка вышла
из области на n-ой, вы можете рисовать ее цветом (n, n, n). Можете попробовать
и что-нибудь поинтереснее типа (n, 255 – n, 50 mod n * 3). Оставляем простор
для вашей фантазии. И последнее: обычно, все множество Мандельброта расположено
от -2 до 0.5 по действительной оси и от –1.25 до 1.25 по мнимой оси. Ваша
программа не должна тестировать точки далеко за пределами этой области.
Требования
Итак, ваша программа должна генерировать цветное изображение
множества Мандельброта с приемлемой точностью (где цвет должен отражать
то, как быстро расходится итерационная последовательность для данной точки).Как
доплнение, вы можете сделать следующее: позволить пользователю увеличивать
любые части изображения, щелкая на них мышкой ( за это будут даваться дополнительные
баллы).
Сдача
Дата сдачи: 6 Марта.
Присылать задания по e-mail: assign1@graphics.cs.msu.su в
следующем виде: .zip файл с именем, построенным следующим образом:
имя начинается с цифры - это последняя цифра в номере вашей группы
(например, если у вас 206 группа, то название файла будет начинаться с
цифры 6), дальше- первые три буквы вашей фамилии (латинским шрифтом), далее
- знак подчеркивания и три первые буквы имени (латинским шрифтом)
Пример: Иванов Андрей из 202 группы должен прислать нам .zip файл с
именем: 2iva_and.zip.
Теперь о том, какие файлы должен содержать ваш .zip - файл:
первое - исходники
второе - *.exe - файл
третье !!! - файл readme (что работает, что не работает,
что дополнительно реализовано и т.п.)
Внимание: номер задания и его название, фамилия
и имя автора, номер группы, дата - суть обязательные атрибуты READ.ME.
Та же информация должна как комментарий содержаться в исходных текстах
программы. |
