cinoea/fg03-algebraicfractals

Задание 3.1. Бассейны Ньютона

Написать программу, визуализирующую бассейны Ньютона для полинома 3-ей степени p(x)=z<sup>3</sup> - 1. Программа должна предусматривать возможность раскраски пикселей различными способами, а именно "классическим", "уровневым" и "зеброй". Для подробного исследования фрактала должно быть реализовано масштабирование.

Метод построения

• Для каждого пикселя экрана найти соответствующую точку комплексной плоскости
• Определить необходимое количество итераций метода Ньютона, чтобы перевести эту точку в некоторую малую окресность любого из 3 аттракторов
• В зависимости от найденного количества итераций аттрактора, а также способа раскраски задать цвет пикселю.

Входные данные

• максимальное количество итераций n
• тип раскраски colorType

Раскраска "Классическая"

Данный метод предполагает раскрашивание в один цвет всех точек, относящихся к одному бассейну притяжения. Так как всего имеется 3 аттрактора, для раскрашивания обычно выбирают красный, зеленый и синий цвета.

Раскраска "Уровни"

Данный метод предполагает раскрашивание в один цвет всех точек, попадающих в окрестность любого из аттракторов за одинаковое количество шагов метода Ньютона.

При выборе яркости в зависимости от количества итераций можно использовать следующие подходы:

• Линейный brightness = n > 1 ? 255*k/(n - 1) : 0
• Логарифмический brightness = n > 1 ? 255*log(1+k)/log(n) : 0;

где k - фактическое количество итераций

Раскраска "Зебра"

Данный метод предполагает раскрашивание в черный цвет всех точек, попадающих в окрестность любого из аттракторов за четное количество шагов метода Ньютона, а в белый - за нечетное. Или наоборот. Можно использовать попеременно больше двух цветов. Тогда раскраска будет радужной.

Раскраска "Гибридная"

Гибридную раскраску можно получить, объединив идеи классической и уровневой раскрасок.

Организация пространства координат

Аттракторы фрактала - вполне конкретные точки на комплексной плоскости. Экран, на который производится отрисовка имеет свою дискретную систему координат. Эти две системы надо как-то отобразить друк на друга.

Для этого достаточно сопоставить двум точкам экрана две точки комплексной плоскости, а все остальные точки сопоставить друг другу по линейному закону.

Имеем крайние точки экрана: (0, 0), (width - 1, height - 1). Назовем соответствующие точки комплексной плоскости так: (left, top), (right, bottom). Тогда для произвольной точки экрана (i, j) легко определить соответствующую точку (x, y) комплексной плоскости: (x, y) = (i*(right - left)/(width - 1) + left, j*(bottom - top)/(height - 1) + top).

Аналогичной формулой можно преобразовать (x, y) к (i, j). Как известно на экране ось ординат направлена вниз. Комплексная плоскость обычно изображается наоборот. Приведенная выше формула позволяет легко обойти этот неприятный момент: достаточно правильно задать соответствие между начальными парами точек.

Организация масштабирования

Техническая составляющая масштабирования - это выбор способа. Довольно очевидны следующие:

• Выделение рамкой новой, меньшей области для отображения
• Клик по точке, которая станет новым центром отображения, с одновременным увеличением/уменьшением размеров показываемой области

Любой из способов должен выдавать координаты прямоугольной области, которую следует показать на экране. Зная эти координаты, т.е. левую верхнюю и правую нижнюю точки прямоугольника, достаточно привязать к ним крайние точки экрана, а затем заново построить фрактал.

Замечания

• В методе построения фигурирует некая малая окрестность аттрактора, в которую должна перейти точка после некоторого числа итераций. Так как числа с плавающей точкой имеют ограниченную точность, то можно использовать в качестве радиуса такой окрестности минимальное число с плавающей точкой. Для меньшей окрестности все равно посчитать не удастся. В этом случае попадание в малую окрестность эквивалентно тому, что после очередной итерации метода Ньютона координаты точки останутся прежними.
• Все расчеты можно осуществлять в комлексных числах, используя готовые или свою реализации, либо можно перейти к действительной плоскости.
• Не для каждой точки за отведенное число итераций удастся приблизиться к аттрактору. В худшем случае достаточно будет только бесконечного числа шагов. Такие точки следует раскрашивать в особый цвет. Например, в белый или черный.

Задание 3.2. Множество Мандельброта

Написать программу, визуализирующую множество Мандельброта. Программа должна предусматривать возможность раскраски пикселей различными способами, а именно "классическим", "уровневым" и "зеброй". Для подробного исследования фрактала должно быть реализовано масштабирование.

Метод построения

• Для каждого пикселя экрана найти соответствующую точку комплексной плоскости
• Для каждой такой точки c определить необходимое количество итераций, после которого модуль очередного значения последовательности z<sub>n+1</sub>=z<sub>n</sub><sup>2</sup> + c, где z<sub>0</sub>=0, окажется строго больше 2
• В зависимости от найденного количества итераций аттрактора, а также способа раскраски задать цвет пикселю.

Входные данные

• максимальное количество итераций n
• тип раскраски colorType

Раскраска "Классическая"

Данный метод предполагает раскрашивание в один цвет (обычно белый) всех точек, относящихся к бассейну притяжения бесконечности. А в другой цвет (соответсвенно, черный) всех остальных точек плоскости.

Раскраска "Уровни"

Данный метод предполагает раскрашивание в один цвет всех точек, выходящих за круг радиуса 2 за одинаковое количество шагов.

При выборе яркости в зависимости от количества итераций можно использовать линейный и логарифмический подходы.

Раскраска "Зебра"

Данный метод предполагает раскрашивание в черный цвет всех точек, выходящих за круг радиуса 2 за четное количество шагов, а в белый - за нечетное. Или наоборот. Можно использовать попеременно больше двух цветов. Тогда раскраска будет радужной.

Замечания

• Согласно Bail-out правилу гарантируется, что если хотя бы один член последовательности выйдет за пределы круга радиуса 2, то предел последовательности будет равен бесконечности. На практике используется именно проверка на выход за пределы круга.
• Все расчеты можно осуществлять в комлексных числах, используя готовые или свою реализации, либо можно перейти к действительной плоскости.
• Не для каждой точки, для которой рассматриваемая последовательность стремится к бесконечности, за отведенное число итераций удастся выйти за круг радиуса 2. В худшем случае достаточно будет только бесконечного числа шагов. Такие точки следует раскрашивать в особый цвет. Например, в белый или черный. Либо раскрашивать также как точки, которые вышли из круга за n шагов.

Задание 3.3. Множество Жюлиа

Написать программу, визуализирующую заполненное множество Жюлиа для полинома второй степени. Программа должна предусматривать возможность раскраски пикселей различными способами, а именно "классическим", "уровневым" и "зеброй". Для подробного исследования фрактала должно быть реализовано масштабирование.

Метод построения

• Для каждого пикселя экрана найти соответствующую точку комплексной плоскости
• Для каждой такой точки z<sub>0</sub> определить необходимое количество итераций, после которого модуль очередного значения последовательности z<sub>n+1</sub>=z<sub>n</sub><sup>2</sup> + c, где c - некоторая константа, окажется строго больше 2
• В зависимости от найденного количества итераций аттрактора, а также способа раскраски задать цвет пикселю.

Входные данные

• максимальное количество итераций n
• тип раскраски colorType
• характеризующее множество Жюлиа значение c

Раскраска "Классическая"

Раскраска "Уровни"

Раскраска "Зебра"

Замечания

• Методы раскрашивания аналогичны методам раскрашивания множества Мандельброта.
• См. замечания по множеству Мандельброта.