Лабораторная работа
Знакомство с фрактальной графикой

1 Цель работы
Познакомиться с основами создания фрактальных композиций при помощи среды программирования BORLANDC.
2 Порядок выполнения работы
2.1 Внимательно изучить алгоритмы построения фракталов.
2.2 Выполните все задания по созданию фракталов, используя различные алгоритмы.
2.3. Выполните индивидуальное задание.

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

4 Теоретические положения
4.1 Понятие фрактальной графики
Фракталы встречаются везде, где заканчиваются правильные формы евклидовой геометрии. Все, что создано человеком, ограничено плоскостями. Если встречается природный объект, то с первого взгляда видно, что осознать, описать его форму со всеми шероховатостями можно только приблизительно. Здесь на помощь приходят фракталы.
Термин «фрактал» (от английского слова «fraction» — дробь) введен бельгийским математиком Бенуа Мандельбротом и обозначает множество, имеющее дробную фрактальную размерность. Для пояснения фрактальной размерности необходимо ввести понятие топологической размерности. Под топологической размерностью Dt множества в линейном пространстве понимают число линейно независимых координат в пространстве. Например, окружность и линия имеют топологическую размерность 1; круг и квадрат — 2; шар и куб — 3. Фрактальная размерность множества D — размерность того пространства, которое полностью заполняется множеством. Для связи фрактальной и топологической размерностей используют показатель Херста Н, вычисляемый по формуле: H = D — Dt. Фракталом называют множество, фрактальная размерность которого не совпадает с топологической. Например, для кривых Пеано (кривые, заполняющие плоскость) Dt = 1, D = 2.
Рассмотрим классический пример фрактального множества — триадную кривую Кох (рис. 1).

Рис. 1. Построение триадной кривой Кох
Построение кривой начинается с единичного отрезка, который называется инициатором и является предфракталом 0-го порядка. Далее инициатор заменяется на образующий элемент — кривую из четырех прямолинейных звеньев, каждое из которых имеет длину 1/3. Так образуется предфрактал 1-го порядка. Его длина равна 4/3. Для построения предфрактала следующего порядка каждое звено заменяется на уменьшенный образующий элемент. В результате получаем кривую, состоящую из 4 x 4 = 16 звеньев, каждое из которых имеет длину (1/3) / 3 = 1/9, общая длина равна 16/9. Длина предфрактала n-го порядка равна (4/3) в степени n. Очевидно, что предел длины кривой при n, стремящемся к бесконечности, равен бесконечности. В итоге получили кривую бесконечной длины, заполняющую ограниченное множество на плоскости, что само по себе очень любопытно. Если построение кривой начинать не с отрезка, а с треугольника, и применить вышеперечисленные построения к каждой его стороне, то получим «снежинку» Кох (рис. 2).

Рис. 2. «Снежинка» Кох (Предфрактал 4-го порядка)
Эта фигура интересна тем, что ее периметр — линия бесконечной длины — ограничивает конечную площадь. Фрактальная размерность триадной кривой Кох D равна ln4/ln3, то есть D является дробным числом, находящимся между 1 и 2.
L — системы
Существуют два основных способа построения фракталов. Первый способ — использование L-систем (от имени Lindenmayer), второй способ — применение системы IFS (iterated function systems). L-система — это грамматика некоторого языка (достаточно простого), которая описывает инициатор и преобразование, выполняемое над ним, при помощи средств, аналогичных средствам языка Лого (аксиоматическое описание простейших геометрических фигур и допустимых преобразований на плоскости и в пространстве). Приведем фрагмент программы, задающей построение кривой Кох в формате L-системы:
Koch {
Angle 6 // Задается угол поворота 360 / 6 = 60.
Axiom F // Это инициатор в виде отрезка (F — вперед).
F=F+F—F+F // Функция (+ влево, — вправо).
}

Рис. 3. Пример построения дерева с помощью L — системы
Подобные L-системы применяются в пакете Autodesk 3D Studio для описания цветов и других растений.
Отметим, что L-системы предназначены для генерирования предфракталов, заданного порядка. Это свойство отличает их от IFS, которые предназначены для построения самих фракталов.
Системы итерирующих функций (IFS)
Система итерирующих функций — это совокупность сжимающих аффинных преобразований. Как известно, аффинные преобразования включают в себя масштабирование, поворот и параллельный перенос. Аффинное преобразование считается сжимающим, если коэффициент масштабирования меньше единицы.
Рассмотрим подробнее построение кривой Кох с использованием аффинных преобразований. Каждый новый элемент кривой содержит четыре звена, полученных из образующего элемента использованием масштабирования, поворота и переноса.
1. Для получения первого звена достаточно сжать исходный отрезок в три раза. Следует отметить, что, то же масштабирование применяется для всех звеньев.
2. Следующее звено строится с использованием всех возможных преобразований, а именно: сжатие в три раза, поворот на – 60? и параллельный перенос на 1/3 по оси X.
3. Третье звено строится аналогично второму: сжатие в три раза, поворот на 60о, параллельный перенос на 2/3 по оси X.
4. Последнее звено: сжатие в три раза, параллельный перенос на 2/3 по оси X.
4.2. Создание фрактала Мандельброта.
Для создания фрактала Мандельброта необходимо для каждой точки изображения выполнить цикл итераций согласно формуле:
, k=0,1,…,n.
Величины — это комплексные числа, , причем стартовые значения X0 и Y0 — это координаты точки изображения. Для каждой точки изображения итерации выполняются ограниченное количество , или до тех пор, пока модуль числа Zk не превышает 2. Модуль комплексного числа равен корню квадратному из . Для вычисления квадрата величины Zk можно воспользоваться формулой:
, поскольку .
Цикл итераций для фрактала Мандельброта можно выполнять в диапазоне
X = (от -2.2 до 1), Y = (от -1.2 до 1.2).
Для того чтобы получить изображение в растре необходимо пересчитывать координаты этого диапазона в пиксельные.
Задание 1: Получите изображение фрактала Мандельброта.

#include<math.h>
#include<graphics.h>
#include<conio.h>
#include<dos.h>
#include<stdio.h>
#include<process.h>
#include<iostream.h>

void Mand(int xx,int yy, int cx, int cy, double minx, double maxx, double miny,double maxy);
int Iter(double x, double y);
int COLOR(int index);
void main() {
int driver = VGA;
int mode = VGAHI;
int res;
initgraph ( &driver, &mode, «»);
if ( ( res = graphresult () ) != grOk )
{ printf («\nGraphics error: %s\n», grapherrormsg (res) );
exit (1);}
int mx,my;
mx=getmaxx()/2; my=getmaxy()/2;
Mand(0,0,mx,my,-2.2,1,-1.2,1.2);
Mand(mx,0,mx,my,-1,-0.5,-0.5,0);
Mand(mx,my,mx,my,-0.75,-0.6,-0.5,-0.35);
Mand(0,my,mx,my,-0.68,-0.65,-0.37,-0.36);
getch();
closegraph();
}
void Mand(int xx,int yy, int cx, int cy, double minx, double maxx, double miny,double maxy)
{
double stepx,stepy;
int i,j,iter;
double x,y;
stepx=(maxx-minx)/(double)cx;
stepy=(maxy-miny)/(double)cy;
y=miny;
for(j=0;j<cy;j++){
x=minx;
for(i=0;i<cx;i++){
iter= Iter(x,y);
putpixel(xx+i,yy+j,COLOR(iter));

x+=stepx;}
y+=stepy;}
}
int Iter(double x, double y)
{
int i; double xx,yy,xk,yk;
xx=x; yy=y; i=0;
while ((xx*xx+yy*yy<=4.0)
{ xk=xx*xx-yy*yy+x;
yk=2.0*xx*yy+y;
xx=xk;
yy=yk;
i++;
if(i>=MaxIter) break;}
return i;
}
int COLOR(int index)
{
return (MaxIter-index);}

Фрактал Джулия внешне совсем не похож на фрактал Мандельброта, однако он определяется итерационным циклом, почти полностью тождественным с циклом генерации Мандельброта.
Формула итераций для фрактала Джулия такая:

где С — комплексная константа. Условием завершения итераций является | Zл | > 2 — так же, как для фрактала Мандельброта.

Алгоритм:
Шаг 0:
Выбрать параметр c=p+iq, выбрать Xmin = -1.5, Ymin = -1.5, Xmax = 1.5, Ymax = 1.5
Это означает, что p- реальная переменная, iq — воображаемая, но тоже вполне реальная переменная. Например, p = 0.32 c_img = 0.043. Эти параметры являются константой при построении одного отображения и их значения определяют рисунок. Масштабировать отображения можно, меняя значения Xmax, Xmin, Ymax, Ymin.
Выбрать число M, которое считается бесконечно большим.
Этот параметр определяет максимальное число итераций
Вычислить dx=(Xmax-Xmin)/(A-1), dy=(Ymax-Ymin)/(B-1).
Для всех пар (Nx, Ny), где Nx=0,1… A-1 и Ny=0,1…B-1 выполнить следующую процедуру.
Шаг 1(первый и второй циклы):
Положить x(n)=xmin+Nx*dx, y(n)=ymin+Ny*dy, k=0. Здесь последовательно изменяются только Nx и Ny, на одно изменение Nx приходится В изменений Ny. Пиксел который будет в дальнейшем окрашиваться имеет координаты (x(n),y(n)).
Шаг 2 (третий цикл, итерация):
Вычислить x(k+1) и y(k+1), по формулам
x(k+1)=x(k)2*x(k)-y(k)2 + p,
y(k+1)=2*x(k)*y(k) + q.
Увеличить счетчик k на 1 (k=k+1).
Шаг 3 (оценка внутри 3 цикла):
Вычислить r=x(k)2+y(k)2.
Если r>M, то идти на шаг 4.
Если k=M то выбрать цвет 0 (черный) и идти на шаг 4.
Если r<=M и k<M. Вернуться на шаг 2.
Шаг 4:
Приписать цвет k точке экрана (x(n), y(n)) и перейти к следующей точке, начиная с шага 1.

Другие параметры для построения фрактала, например, С = 0.36 + i* 0.36, количество итераций =256. Границы X= (от -1 до 1), Y = (от -1.2 до 1.2).
Задание 2: Получить изображение фрактала Джулия.

Само подобие считается важным свойством фракталов. Это отличает их от других типов объектов сложной формы.
Рассмотрим следующий пример фрактала — фрактал Ньютон. Для него итерационная формула имеет такой вид:

где Z — также комплексные числа, причем Z0 = Х + i*У соответствует координатам точки изображения.
Условием прекращения цикла итераций для фрактала Ньютон есть приближение значений |Z4- 1| к нулю.
Задание 3: Получить изображение фрактала Ньютона для |Z4- 1|2> 0.001, границы расчета Х= (от-1 до 1), У = (от-1 до 1).

Фракталы, которые генерируются согласно методу «систем итеративных функций» — IFS (Iterated Function Systems). Этот метод может быть описан, как последовательный итеративный расчет координат новых точек в пространстве:

Где Fx и Fy — функции преобразования координат, например, аффинного преобразования. Эти функции и определяют форму фрактала. В случае аффинного преобразования необходимо найти соответствующие числовые значения коэффициентов.
Примеры само подобных множеств:

Попробуем создать фрактал, который бы выглядел как растение. Вообразим себе ствол, на котором много веточек. На каждой веточке много меньших веточек и так далее. Самые малые ветки можно считать листвой — колючками. Все элементы будем рисовать отрезками прямой. Каждый отрезок будет задаваться двумя конечными точками.
Для начала итераций необходимо задать стартовые координаты линии. Это будут точки 1, 2. На каждом шаге итераций будем рассчитывать координаты других точек.
Сначала находим точку 3. Это повернутая на угол ? точка 2, центр поворота — в точке 1

X3 = (X2 –X1)* соs ? — (Y2 – Y1)* sin а + X1,

Y3 = (X2 –X1)*sin ? — (Y2 – Y1)* cos а + Y1,

Если ? = 0, то ствол и все ветви прямые. Потом находим точку 4. От нее будут распространяться ветви. Пусть соотношение длин отрезков 1-4 и 1-3 равно причем 0<k<1. Тогда для вычисления координат точки 4 можно воспользоваться следующими формулами:
X4 =X1 *(1-k)+X3 *k,
Y4 =Y1 *(1-k)+Y3 *k,

Теперь зададим длину и угол наклона ветвей, которые выходят из точки 4.Сначала найдем координаты точки 5. Введем еще один параметр — k1, который будет определять соотношение длин отрезков 4-5 и 4-3, причем так же 0<k1<1. Координаты точки 5 равны:
X5 =X4 *(1-k1)+X3 *k1,
Y5 =Y4 *(1-k1)+Y3 *k1,
Точки 6 и 7 — это точка 5, повернутая относительно точки 4 на углы ? и -? соответственно:
X6 =(X5 –X4)*cos ? – (Y5 –Y4)*sin ? +X4,

Y6 =(X5 –X4)*sin ? – (Y5 –Y4)*cos ? +Y4,

Кроме расчета опорных точек на каждом шаге будем рисовать один отрезок 1-4. В зависимости от номера итераций можно изменять цвет отрезка. Так можно устанавливать его толщину, например, пропорционально длине. Таким образом, фрактал мы задали как последовательность аффинных преобразований координат точек. Величины ?, ?, k, k1 — это параметры, которые описывают вид фрактала в целом. Они представляют собой константы на протяжении всего итеративного процесса. Это дает возможность в итерациях использовать только операции сложения, вычитания и умножения, если вычислить значения sin(), соs(), (1 — k) и (1 – k1) только один раз перед началом итераций как коэффициенты-константы.
Дадим запись алгоритма в виде рекурсивной процедуры ШАГ ().
ШАГ(x1,y1,x2,y2,num)
{
ЕСЛИ (x1-x2)2+(y1-y2)2 > lmin,
{
Вычисляем координаты точек 3-7:
Х3 = (X2 — X1) А — (Y2 — Y1) В + X1
У3 = (X2 — X1) В + (Y2 — Y1) А + Y1
Х4 = X1 С + X3 D
У4 = Y1 С + Y3 D
X5 = X4 Е + X3 F
У5 = Y4 Е + Y3 F
X6 = (X5 — X4) G — (Y5 — Y4) Н + X4
Y6 = (X5 — X4) Н + (Y5 — Y4) G + Y4
X7 = (X5 — X4) G + (Y5 — Y4) Н + X4
Y7 = -(X5 — X4) Н + (Y5 — Y4) G + Y4

Рисуем отрезок (х1,у1 — х4,у4)

ШАГ(X4, Y4, X3, Y3, num)
ШАГ(X4, Y4, X6, Y6, num+1)
ШАГ(X4, Y4, X7, Y7, num+1)
Для того чтобы нарисовать фрактал, необходимо вызывать процедуру ШАГ, Установив соответствующие значения ее аргументов: ШАГ(X1, Y1, X2, Y2, 0) .Обратите внимание на один из аргументов этой процедуры — num, кoторый в начале работы равен 0. В теле процедуры есть три рекурсивных вызова с различными значениями этого аргумента:
ШАГ(X4, Y4, X3, Y3, num) —продолжаем ствол;
ШАг(X4, У4, X6, Y6, num+1) —правая ветвь;
ШАГ (X4, Y4, Х7, У7, num+1) —левая ветвь.
Значение num показывает степень детализации расчета дерева. Один цикл итераций содержит много шагов, соответствующих одному значению величины num. Числовое значение num можно использовать для прекращения итеративного процесса, а также для определения текущего цвета элементов «растения».
Завершение циклов итераций в нашем алгоритме происходит тогда, длина ветви становится меньше некоторой величины lmin, например, lmin=1 .
Этот фрактал при ? = 2°, ? = 86°, k = 0.14, k1 =0.3 похож на папоротник.
Задание 4: Получите изображение листа папоротника, используя выше описанный алгоритм.

Самоподобные и самоаффинные фракталы строят простым и быстрым алгоритмом итераций отображений подобия. Среди изображений построенных компьютером встречаются естественно выглядящие картины растений и деревьев. Пусть {S1,..,SN} — некоторая система аффинных сжатий. Отображения Si представимы в виде:
Si(x)=Ai( x-oi )+oi, где Ai — фиксированная матрица размера 2×2 и oi — двумерный вектор столбец.
1. Возьмем неподвижную точку первого отображения S1 в качестве начальной точки:
x := o1;
Здесь мы пользуемся тем, что все неподвижные точки сжатий S1,..,SN принадлежат фракталу. Кстати можно в качестве начальной точки выбрать произвольную и порожденная ею последовательность точек стянется к фракталу (хотя несколько лишних точек появится).
2. Отметим текущую точку x=(x1,x2) на экране:
putpixel(x1,x2,15);
3. Выберем случайным образом число k от 1 до N и пересчитаем координаты точки x:
k:=Random(N)+1;
x:=Sk(x);
4. Переходим на шаг 2.
Фрактальный морфинг
Если есть описание нескольких фракталов в формате IFS, можно произвести морфинг (непрерывное преобразование одного в другой).

Рис. 7. Изображение листа папоротника, полученное с помощью IFS
Fern {
0 0 0 .16 0 0 .01
.85 .04 -.04 .85 0 1.6 .85
.2 -.26 .23 .22 0 1.6 .07
-.15 .28 .26 .24 0 .44 .07
}
Для осуществления морфинга достаточно линейно интерполировать элементы одной матрицы в те же элементы другой и строить фракталы для каждого из промежуточных состояний. Чтобы получить лучший визуальный эффект, нужно продумать положение строк в матрицах. При выводе одного фрактала этот факт не играет роли. При построении разных фракталов с использованием IFS можно отметить, что они все имеют разные размеры, и поэтому нуждаются в масштабировании. На рисунке приведен пример фрактального морфинга.

Рис. 8. Пример фрактального морфинга «дерева» в «лист папоротника»
Если для построения фрактала используем систему итерирующих функций, получаем изображение, деталировка которого ограничена только разрешением устройства отображения, в отличие от построения, основанного на L-системе, где точность зависит от заданного порядка предфрактала. Чтобы получить высокое разрешение с использованием L-систем, необходимо задавать большой порядок предфрактала. Но так как построение основано на рекурсивном алгоритме, соответственно получается большая глубина рекурсии и, как следствие, замедление построения.
Для синтеза фрактала выбирается начальная точка, к которой применяется случайным образом выбранное из IFS преобразование, в результате чего точка перемещается в другой конец экрана. Эта операция повторяется много раз (достаточно 100 итераций), и через некоторое время точка начинает блуждать по аттрактору, (аттрактор — множество всех возможных траекторий), который и будет представлять собой изображение фрактала. Каждое новое положение точки окрашивается цветом, отличным от фона. Существует теорема, доказывающая, что полученный аттрактор будет замкнутым. Для того, чтобы блуждающая точка окрашивала новые пиксели, а не блуждала по старым, используют седьмой параметр, который представляет собой вероятность появления конкретного аффинного преобразования из набора преобразований IFS. Если выбрать начальную точку так, чтобы она сразу оказалась на аттракторе, то она начинает блуждать в области этого аттрактора, не перемещаясь в другие области экрана. Рассматривая каждое преобразование в отдельности, можем заметить, что где бы мы ни начинали, после нескольких итераций, точка перестанет двигаться по экрану. Точка остановки называется неподвижной точкой — это решение системы линейных уравнений двух переменных, которое находится методом простой итерации. Неподвижная точка каждого преобразования входит в состав аттрактора. Поэтому за начальную точку при построении фрактала можно взять неподвижную точку первого преобразования из набора IFS. На рис. 5 изображена кривая Кох, построенная при помощи метода IFS.

Рис. 5. Изображение кривой Кох, полученное с использованием IFS
Увеличивая разрешение устройства отображения или масштаб, можно увидеть новые части фрактала, которые будут похожи на весь фрактал.