ЛАБОРАТОРНАЯ РАБОТА № 6
Двумерные фракталы
 
1. Цель работы
 
1) Освоить  программирование двумерных фракталов.
2) Разработать программу в среде визуального проектирования C++Builder, позволяющую демонстрировать процесс итерактивного построения геометрических, алгебраических или стохастических фракталов.
 
2. Постановка задачи
 
2.1. В проект, разработанный для лабораторных работ №1–5, добавьте новый модуль.
2.2. На поле формы установите графическое окно и панель с элементами управления.
2.3. Разработайте функции, позволяющие выполнять построение одного из трех видов фракталов (по собственному выбору), приведенных в таблице 1. Номер и количество итераций фракталов должны задаваться средствами регулирования, расположенными на панели управления.
2.4. В зоне графического окна должен наблюдаться процесс построения заданного фрактала по мере последовательного увеличения номера итерации.
 
Таблица 1
Вар.
Типы фракталов
Геометрические
Алгебраические
Стохастические (IFS)
1
Триада Коха
Множество Мандельброта
Аффинные
2
Снежинка Коха
Множество Жюлиа
2D-полином
3
Салфетка Серпинского
Бассейн Ньютона
Комплексный полином
4
Ковер Серпинского
Биоморф
Спираль (Helix)
5
Кривая Серпинского
Множество Мандельброта
Рябь (Ripple)
6
Кривая Пеано
Множество Жюлиа
Плазма
7
Кривая Госпера
Бассейн Ньютона
Аффинные
8
Кривая Леви
Биоморф
2D-полином
9
Дерево Пифагора
Бассейн Ньютона
Комплексный полином
10
Дракон Хартера-Хейтуэя
Биоморф
Спираль (Helix)
 
3.  Краткие теоретические сведения
 
3.1.  Общая  характеристика  фракталов
 
Термин "фрактал" образован от латинского fractus и в переводе означает состоящий из фрагментов. Он было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которые он исследовал. Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому".
Основным свойством фракталов является самоподобие, когда небольшая часть фрактала содержит информацию о всем фрактале.
Математические фракталы обладают следующими качествами: они имеют бесконечную длину, непрерывны, способны заполнить плоскость, но ни в одной точке не имеют производной.
Роль фракталов в компьютерной графике достаточно велика. С их помощью, например, можно задавать линии и поверхности очень сложной формы. Фрактальная геометрия незаменима при генерации искусственных облаков, гор, поверхности моря, а также сложных неевклидовых объектов, образы которых весьма похожи на природные.
В общепринятой классификации выделяют 3 вида фракталов: геометрические, алгебраические и стохастические.
Существуют и другие классификации фракталов, например деление фракталов на детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).
Фракталы разделяются также на регулярные и мультифракталы.
Мультифракталы это неоднородные фракталы, для их полной характеристики требуется не одна, а несколько фрактальных размерностей, число которых в общем случае бесконечно.
 

3.2.  Геометрические  фракталы
 
Фракталы этого класса получают с помощью некоторой ломаной (или поверхности в трехмерном случае), называемой генератором [14]. За один шаг алгоритма каждый из отрезков, составляющих ломаную, заменяется на ломаную-генератор, в соответствующем масштабе. В результате бесконечного повторения этой процедуры, получается геометрический фрактал.
Существует два основных способа построения геометрических фракталов:
- первый способ - использование L-систем (от имени Lindermayer);
- второй способ - применение систем итерирующих функций (IFS).
Наиболее простой способ построение фракталов — это метод построения с помощью L систем. Данный метод был разработан биологом Аристидом Линдермауером.
L-система - это грамматика некоторого языка (достаточно простого), которая описывает инициатор и преобразование, выполняемое над ним, при помощи средств, аналогичных средствам языка Лого (аксиоматическое описание простейших геометрических фигур и допустимых преобразований на плоскости и в пространстве).
В данном методе рисование фракталов осуществляется с помощью простой, но достаточно эффективной технологии компьютерной графики - “черепашьей графики”.
Система итерирующих функций - это совокупность сжимающих аффинных преобразований. Как известно, аффинные преобразования включают в себя масштабирование, поворот и параллельный перенос. Афинное преобразование считается сжимающим, если коэффициент масштабирования меньше единицы.
Данный метод был разработан и воплощен в жизнь американским математиком М. Барнсли (M.Barnsley).
Это метод сложнее и гибче чем метод L систем. В отличие от метода L систем данный метод описывает фракталы не графически, а математически, в виде формул.
IFS позволяет строить более сложные фракталы, чем метод L систем. В нем можно строить такие знаменитые фракталы как: Множество Жюлиа, фрактал Мандельброта и другие. В СИФ для работы с фракталами используются комплексные числа и комплексная плоскость.
 
Рассмотрим один из фрактальных объектов – триадную кривую Коха [14]. Построение этой кривой в режиме L-системы начинается с отрезка единичной длины (рисунок 1) – это 0-е поколение кривой Коха. Далее каждое звено (в нулевом поколении один отрезок) заменяется на образующий элемент, обозначенный на рисунке 1 через n = 1. В результате такой замены получается следующее поколение кривой Коха. В 1-ом поколении – это кривая из четырех прямолинейных звеньев, каждое длиной по 1/3. Для получения 3-го поколения проделываются те же действия - каждое звено заменяется на уменьшенный образующий элемент. Итак, для получения каждого последующего поколения, все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. На рисунке.1 представлены пять поколений кривой. При n стремящемся к бесконечности кривая Кох становится фрактальным обьектом.
 
 
Рисунок 1 – Построение триадной кривой Коха.
 
Для получения другого фрактального объекта нужно изменить правила построения. Пусть образующим элементом будут два равных отрезка, соединенных под прямым углом. В нулевом поколении заменим единичный отрезок на этот образующий элемент так, чтобы угол был сверху. Можно сказать, что при такой замене происходит смещение середины звена.
При построении следующих поколений выполняется правило: самое первое слева звено заменяется на образующий элемент так, чтобы середина звена смещалась влево от направления движения, а при замене следующих звеньев, направления смещения середин отрезков должны чередоваться. На рисунке 2 представлены несколько первых поколений и 11-е поколение кривой, построенной по вышеописанному принципу. Предельная фрактальная кривая (при n стремящемся к бесконечности) называется драконом Хартера-Хейтуэя.
 
 
 
Рисунок 2 – Построение "дракона" Хартера-Хейтуэя
 
3.3. Алгебраические фракталы
 
Алгебраические фракталы получают с помощью нелинейных процессов в n-мерных пространствах. Наиболее изучены двухмерные процессы. Интерпретируя нелинейный итерационный процесс, как дискретную динамическую систему, можно пользоваться терминологией теории этих систем: фазовый портрет, установившийся процесс, аттрактор и т.д. [14].
Известно, что нелинейные динамические системы обладают несколькими устойчивыми состояниями. То состояние, в котором оказалась динамическая система после некоторого числа итераций, зависит от ее начального состояния. Поэтому каждое устойчивое состояние обладает некоторой областью начальных состояний, из которых система обязательно попадет в рассматриваемые конечные состояния. Таким образом, фазовое пространство системы разбивается на области притяжения аттракторов. Если фазовым является двухмерное пространство, то окрашивая области притяжения различными цветами, можно получить цветовой фазовый портрет этой системы (итерационного процесса). Меняя алгоритм выбора цвета, можно получить сложные фрактальные картины с причудливыми многоцветными узорами. Неожиданностью для математиков стала возможность с помощью примитивных алгоритмов порождать очень сложные нетривиальные структуры.
 
 
 
Рисунок 3 – Множество Мандельброта
 
В качестве примера рассмотрим множество Мандельброта (рисунки 3 и 4). Алгоритм его построения достаточно прост и основан на простом итеративном выражении:
 
Z[i+1] = Z[i] * Z[i] + C                                                                            (2.1)
 
где Zi и C - комплексные переменные.
Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости. Итерационный процесс продолжается до тех пор, пока Z[i] не выйдет за пределы окружности радиуса 2, центр которой лежит в точке (0,0), или после достаточно большого числа итераций (например 200-500) Z[i] сойдется к какой-нибудь точке окружности. В зависимости от количества итераций, в течении которых Z[i] оставалась внутри окружности, можно установить цвет точки C (если Z[i] остается внутри окружности в течение достаточно большого количества итераций, итерационный процесс прекращается и эта точка растра окрашивается в черный цвет).


 
 
Рисунок 4 – Участок границы множества Мандельброта, увеличенный в 200 pаз
 
Вышеописанный алгоритм дает приближение к так называемому множеству Мандельброта. Множеству Мандельброта принадлежат точки, которые в течение бесконечного числа итераций не уходят в бесконечность (точки, имеющие черный цвет). Точки, принадлежащие границе множества (именно там возникает сложные структуры) уходят в бесконечность за конечное число итераций, а точки лежащие за пределами множества, уходят в бесконечность через несколько итераций (белый фон).
 
3.4.  Стохастические  фракталы
 
Стохастические фракталы - получаются в том случае, если в итерационном процессе случайным образом менять какие-либо его параметры. При этом получаются объекты очень похожие на природные - несимметричные деревья, изрезанные береговые линии и т.д. Стохастические фракталы, полученные на основе системы итерационных функций с заданием вероятности каждого афинного преобразования (Iterated Function System) называются IFS-фракталами.
IFS-фракталы. Метод "Систем Итерируемых Функций" (Iterated Functions System - IFS) появился в середине 80-х годов как простое средство получения фрактальных структур.
Система итерирующих функций - это совокупность сжимающих аффинных преобразований. Как известно, аффинные преобразования включают в себя масштабирование, поворот и параллельный перенос. Афинное преобразование считается сжимающим, если коэффициент масштабирования меньше единицы.
 
Алгоритм построения IFS-фракталов. Матричные преобразования дву- и трехмерных объектов [3] позволяют переносить, масштабировать, отображать, сдвигать проектировать и поворачивать отдельные участки изображения, которые впоследствии служат компоновочными блоками некоторой картины. Матричная запись перечисленных афинных преобразований некоторой точки с использованием однородных координат в общем виде может быть представлена следующим соотношением.
 
 
Матричное уравнение (1) вместе с заданными вероятностями образуют IFS-набор для построения фрактального изображения.
При известных параметрах этого набора алгоритм построения фрактального изображения представляется следующим:
1. Задаются матрицы начальных значений координат некоторого объекта [x], [y], например, [x]=0, [y]=0.
2. Выполняется заданное матричное преобразование, выходные величины которого служат в качестве исходных для следующего шага преобразований. Одновременно эти промежуточные результаты выводятся на экран монитора.
3. Видовые преобразования в каждой итерации выбираются случайным образом в соответствии с заданными вероятностями.
4. Итерационный процесс может состоять из многих тысяч операций.
 
Рассмотрим построение кривой Коха с использованием аффинных преобразований.
Каждый новый элемент кривой содержит четыре звена, полученных из образующего элемента использованием масштабирования, поворота и переноса.
1. Для получения первого звена достаточно сжать исходный отрезок в три раза.
2. Следующее звено строится с использованием всех возможных преобразований, а именно: параллельный перенос на 1/3 по оси OX, поворот на 60° (против часовой стрелки) и сжатие в три раза.
3. Третье звено строится аналогично второму: параллельный перенос на 2/3 по оси OX, поворот на 60° (против часовой стрелки), сжатие в 3 раза по оси OY и сжатие в -3 раза по оси OX.
4. Последнее звено: параллельный перенос на 2/3 по оси OX, сжатие в три раза.
Теперь мы можем найти систему итерирующих функций для описания кривой Кох. Осталось только произвести суперпозицию аффинных преобразований - масштабирования, поворота и параллельного переноса.
Из курса аналитической геометрии известны формулы вычисления новых координат x',y' при аффинных преобразованиях [1]:
x' = x * а + y * b + e,
y' = x * c + y * d + f.
Если мы примем договорённость рассматривать только такие системы координат, у которых кратчайший поворот от первого базисного вектора ко второму происходит против часовой стрелки (будем называть такие системы правыми), то любое преобразование координат будет определяться формулами:
a = cos(alpha) * scale_x,
b =-sin(alpha) * scale_x,
c = sin(alpha) * scale_y,
d = cos(alpha) * scale_y,
e = move_x,
f = move_y,
где scale_x - масштабирование по оси OX;
      scale_y - масштабирование по оси OY;
      alpha    - угол поворота (против часовой стрелки);
      move_x - параллельный перенос по оси OX;
     move_y - параллельный перенос по оси OY.
Полученные коэффициенты a,b,c,d,e,f для каждого звена и составят требуемую систему итерирующих функций.
Вычислим коэффициенты аффинного преобразования IFS для кривой Кох.
Для первого звена коэффициенты аффинного преобразования будут следующими:
a = 0.3333,  b = 0.0000,   c = 0.0000,  d = 0.3333,  e = 0.0000,  f = 0.0000
Для второго звена:
a = 0.1667,   b = -0.2887, c = 0.2887,  d = 0.1667,  e = 0.3333,  f = 0.0000
Для третьего звена:
a = -0.1667,  b = 0.2887,  c = 0.2887, d = 0.1667,  e = 0.6666,   f = 0.0000
И, наконец, для четвертого звена:
a = 0.3333,  b = 0.0000,  c = 0.0000,  d = 0.3333,  e = 0.6666,   f = 0.0000
 
Расчет требует порядка 100 тысяч итераций.
Вычисление первых шести параметров (a,b,c,d,e,f) было проведено выше. Значение последнего (седьмого) параметра (P) каждого преобразования пропорционально площади, занимаемой звеном. Сумма последних параметров для всех преобразований равна единице. В нашем примере размеры звеньев равны, поэтому седьмой параметр равен 0.25 для всех звеньев.
В том случае, если оценить приблизительно размеры не удается, можно использовать формулу вычисления площади p = abs (a * d - b * c). Следует учитывать то, что эта формула дает не нормализованный результат. Поэтому нам придется еще приводить сумму к единице.
Проверим формулу на нашем примере, используя коэффициенты, задающие кривую Кох в формате IFS:
1: 0.3333 * 0.3333 - 0.0000 * 0.0000 = 0.111,
2: 0.3333 * 0.3333 - 0.0000 * 0.0000 = 0.111,
3: 0.1667 * 0.1667 + 0.2887 * 0.2887 = 0.111,
4:-0.1667 * 0.1667 - 0.2887 * 0.2887 = 0.111.
Теперь подбором нормирующего множителя можно нормализовать значение седьмого параметра до значения 0.25.
 
 
 
Рисунок 5 – Кривая Коха, построенная с помощью IFS
 
Если для построения фрактала используем систему итерирующих функций, получаем изображение, деталировка которого ограничена только разрешением устройства отображения, в отличие от построения, основанного на L-системе, где точность зависит от заданного порядка предфрактала. Чтобы получить высокое разрешение с использованием L-систем, необходимо задавать большой порядок предфрактала. Но так как построение основано на рекурсивном алгоритме, соответственно получается большая глубина рекурсии и, как следствие, замедление построения.
 Метод, основанный на IFS, в отличие от L-систем считается перспективным методом синтеза фракталов, а также сжатия изображений.
Рассмотрим другой пример, а именно ковер Серпинского. Для его геометрического построения выбирается в качестве исходного множества треугольник, и на каждом шаге выкидываются центральные треугольные часть (не включая границу) образующихся треугольников. Ниже мы рассмотрим два других метода: детерминированный и рандомизированный.
 
 
 
Рисунок 6 - Построение ковра Серпинского с помощью детерминорованной СИФ
 
Построение ковра Серпинского в детерминированном алгоритме начинается с выбора компактного множества E0, например квадрата (рис.6). Затем задаются аффинные преобразования так чтобы исходное множество E0 было преобразовано, как показано на втором шаге построения рисунка 6. Это достигается путем выбора следующих трех преобразований:
 
 
и преобразование компактного множества E0 записывается в виде:
 
E1 = T1(E0) U T2(E0) U T3(E0)
 
После выполнения n преобразований, получаем изображение, соответствующее ковру Серпинского:
 
E1 = T1(En-1) U T2(En-1) U T3(En-1)
 
Заметим, что все множество возможных построений определяется набором аффинных преобразований   T1, … ,Tn
Обычно коэффициенты аффинного преобразования записываются в матрицу C размером n × 6 элементов, которая полностью описывает фрактальное множество:

 
В рандомизированном алгоритме, который часто называют игрой в «Хаос», в качестве начального множества выбирают одну точку:
xo - начальная точка (с произвольными координатами)
x1 = T1(xo)  или  T2(xo)  или  T3(xo)
xn = T1(xn-1)  или  T2(xn-1)  или  T3(xn-1)
На каждом шаге, вместо того чтобы применять сразу три преобразования T1(S), T2(S), T3(S), мы применяем только одно, выбранное случайным образом. Таким образом, на каждом шаге мы получаем ровно одну точку. Оказывается, что после некоторого переходного процесса точки, сгенерированные в рандомизированном алгоритме, заполняют в точности ковер Серпинского.
Замечательным свойством алгоритмов, основанных на теории систем итерированных функций, является то, что их результат (аттрактор) совершенно не зависит от выбора начального множества E0 или начальной точки x0 В случае детерминированного алгоритма это означает, что в качестве E0 можно взять любое компактное множество на плоскости: предельное множество по-прежнему будет совпадать с ковром Серпинского. В случае рандомизированного алгоритма, вне зависимости от выбора начальной точки x0, после нескольких итераций точки начинают заполнять ковер Серпинского.
Для равномерного распределения точек по экрану в рандомизированном алгоритме аффинные преобразования следует выбирать с вероятностью
 
 
 
Очевидно, что:      p1 + p2 + … + pn = 1
 
 
4. Рекомендации по разработке программы
 
Процесс создания дополнительного модуля для установки на его поле графического окна и панели управления аналогичен действиям, рассмотренным в предыдущих лабораторных работах.
Разработка файла реализации в этой работе также очень проста. Здесь необходимо создать несколько обработчиков: для графического окна, для компонентов ввода номера итераций, либо параметров уравнения (в зависимости от выбранного вида фрактала), для управляющих кнопок.
Кроме этих обработчиков создаются функции расчета координат элементов фрактала, прорисовки фрактала и заливки (при необходимости).
Порядок создания подобных функций описан в предыдущих лабораторных работах. Поэтому, разработку программного кода для данной работы предлагается выполнить самостоятельно.
 
5. Контрольные вопросы
 
1. Дайте определение, что такое фрактал.
2. Назовите основные виды фракталов, в чем заключаются особенности каждого из них.
3. Что такое геометрический фрактал и перечислите его основные разновидности.
4. Что такое алгебраический фрактал и перечислите его основные разновидности.
5. Что такое стохастический фрактал и перечислите его основные разновидности.
6. Что такое "генератор", и в каких видах фракталов он применяется?
7. Что обозначают термины "фазовый портрет", "аттрактор", и в каких фракталах они применяются?
8. В чем заключаются принципы построения IFS-фракталов?
9. В чем заключается метод случайных итераций построения фракталов?
10. Что такое мультифракталы, и в чем их отличие от регулярных фракталов?