Лекция 13 Фрактальные алгоритмы - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Лекция 13 Фрактальные алгоритмы - страница №1/1

Лекция 13

Фрактальные алгоритмы


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

По характеру изменения объема пространства, занимаемого фрактальными объектами, между соседними уровнями рекурсии, фракталы делятся на аддитивные (увеличивающие объем занимаемого фракталом пространства) и субтрактивные (объем занимаемого фракталом пространства уменьшается – треугольник Серпинского).



Свойства фракталов.

  1. Прежде всего фрактал – это не линия или поверхность в виде привычных уравнений. Фракталы выражаются не в первичных геометрических формах, а в алгоритмах, которые трансформируются в геометрические формы с помощью компьютерной программы.

  2. Характер большинства фрактальных алгоритмов преимущественно рекурсивный.

  3. Теоретически глубина рекурсии фрактала бесконечна.

  4. Независимо от природы и метода построения у всех фракталов есть одно важное общее свойство, характеризующее степень их раздробленности и предельные свойства. Это – фрактальная размерность. Согласно идее Мандельброта ее можно определить подсчетом числа элементов N, принадлежащих фрактальному множеству, при различных разрешениях  – минимальных линейных размерах элементов.

  5. Размерность фрактала может быть дробной

Геометрические фракталы


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

Метод построения фрактального объекта может быть как итерационным, так и рекурсивным, причем рекурсивный чаще бывает богаче возможностями и проще в программировании.



Алгоритмические фракталы


Фрактал Мандельброта. Мандельброт исследовал предельное (при k ) поведение последовательности комплексных чисел zk+1= zk2 + z0 , k=0, 1, 2,; z0=c при различных значениях комплексных чисел c.

Последовательность zk с ростом числа итераций демонстрирует поведение двух типов в зависимости от выбора начальной точки z0. Ее элементы либо постепенно уходят в бесконечность, либо всегда остаются в определенной замкнутой области, совершая циклическое движение или сходясь в точку.

Математиками строго доказано, что если при некотором k модуль |zk|>rmin, где rmin=2 – минимальный радиус расходимости множества Мандельброта, то далее последовательность расходится.

Множество точек z0, для которых последовательность не расходится, называется множеством Мандельброта.



Для получения графической интерпретации используется следующий алгоритм.

Комплексное число z=x+iy может быть изображено на плоскости точкой с координатами


(x, y). Изображение строится в некоторой прямоугольной области с разрешением n*m точек.

Формула итераций для фрактала Мандельброта выглядит следующим образом:



zk+1= zk2 + z0 , k=0, 1, 2,

Цикл итераций для фрактала Мандельброта можно выполнять в диапазоне для x0=(от -2,2 до 1) , для y0=(от -1,2 до 1,2) – начальные точки z0.

Для каждой начальной точки вычисляется количество k точек, попадающих в круг сходимости (k – число итераций). Условием завершения итераций является |zk|>2.

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

Если принять значения k для каждой начальной точки (x,y) в качестве высот некоторой поверхности в данной точке можно построить объемное изображение множества Мандельброта или его части, которое при специально подобранном освещении может выглядеть и как скала с плоской вершиной, и как водопад, и как горная пещера.

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

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

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

zk+1= zk2 + c , k=0, 1, 2,

где c – комплексная константа.

Если при генерации фрактала Мандельброта значение z0 каждый раз совпадает со значением в начальной точке на данном шаге итераций, то для фрактала Джулио значение c всегда одно и то же комплексное число.

В программе, (приведенной в приложении 2), построено изображение фрактала Джулио для c=0,36+i*0,36.

Итерационная формула для фрактала Ньютон имеет вид

где z – также комплексные числа, причем z0=x+iy соответствует координатам точки изображения. Условием прекращения цикла итераций для фрактала Ньютон есть приближение значений |z4-1| к нулю.

Границы расчета: для x от -1 до 1, для yот -1 до 1.

Площадные фракталы


Строительными элементами площадных геометрических фракталов служат плоские полигоны, чаще всего трех- и четырехугольники.

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

Алгоритм построения треугольника Серпинского (рис. 23).


  1. В
    нутри исходного треугольника выбирается центральная точка:



  1. Задается число m итераций генерирования случайных точек.

  2. В цикле для k от 1 до m:

– случайным образом выбирается номер n одной из вершин треугольника pn (генерируется случайное число в интервале от 1 до 3).

– вычисляется очередная точка qk в середине отрезка qk-1 pn:



Благодаря выбору точки q0 внутри треугольника ppp3 центр отрезка q0 pn (точка q1) никогда не окажется внутри центрального треугольника, отмеченного на рисунке пунктиром. При достаточно большом числе итераций m генерируемые точки qk образуют случайный узор, предельная форма которого стремится к треугольнику Серпинского.

Следует отметить, что небольшое число начальных точек qk все-таки может попасть в запретные области. В частности, это случится при выборе точки q0 в центре треугольника ppp3 .

Аналогично треугольнику Серпинского может быть построена треугольная пирамида Серпинского.


Фракталы на основе метода IFS


Эту группу составляют фракталы, которые генерируются согласно методу "систем итеративных функций" – IFS (Iterated Functions Systems).

Данный метод может быть описан как последовательный итеративный расчет координат новых точек в пространстве:



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



Для начала итераций необходимо задать стартовые координаты линии – точки 1 и 2. На каждом шаге итераций рассчитываются координаты других точек.

Точка 3 получается поворотом точки 2 на угол  относительно центра в точке 1:



x3=(x2-x1)cos-(y2-y1)sin+x1,

y3=(x2-x1)sin+(y2-y1)cos+y1.

Если =0, то ствол и все ветви прямые.

Находим точку 4. От нее будут распространяться ветви. Пусть соотношение длин отрезков 1-4 и 1-3 равно k (0<k<1). Тогда координаты точки 4: x4=x1(1-k)+kx3, y4=y1(1-k)+ky3.

Задаем длину и угол наклона ветвей, которые выходят из точки 4.

Найдем координаты точки 5: параметр k1 – соотношение длин отрезков 4-5 и 4-3 (0<k1<1):

x5=x4(1-k1)+k1x3,

y5=y4(1-k1)+k1y3.

Точка 6 получается поворотом точки 5 относительно точки 4 на угол , а точка 7 – на угол (-):



x6=(x5-x4)cos-(y5-y4)sin+x4;

y6=(x5-x4)sin+(y5-y4)cos+y4;

x7=(x5-x4)cos+(y5-y4)sin+x4;

y7=-(x5-x4)sin+(y5-y4)cos+y4.

После расчета опорных точек на каждом шаге рисуется отрезок 1-4. В зависимости от номера итерации цвет отрезка можно изменять.

Таким образом, фрактал задается как последовательность аффинных преобразований координат точек. Величины , , k, k1 – это параметры, которые описывают вид фрактала в целом. Они представляют собой константы на протяжении всего итеративного процесса. Это дает возможность в итерациях использовать только операции сложения, вычитания и умножения, если вычислить заранее значения:

A=cos; B=sin; C=(1-k); D=k;

E=1-k1; F=k1; G=cos; H=sin.

Опишем рекурсивный алгоритм в виде процедуры ШАГ.



ШАГ(x1, y1, x2, y2, num)

Если (x1-x2)2+(y1-y2)2>lmin, то

Вычисляем координаты точек 3-7:

x3=(x2-x1)A ­- (y2-y1)B + x1

y3=(x2-x1)B + (y2-y1)A + y1

x4=x1C + x3D

y4=y1C + y3D

x5=x4E + x3F

y5=y4E + y3F

x6=(x5-x4)G - (y5-y4)H + x4

y6=(x5-x4)H + (y5-y4)G + y4

x7=(x5-x4)G + (y5-y4)H + x4

y7=-(x5-x4)H + (y5-y4)G + y4

Рисуем отрезок (x1, y1 - x4, y4)

ШАГ(x4, y4, x3, y3, num)

ШАГ(x4, y4, x6, y6, num+1)

ШАГ(x4, y4, x7, y7, num+1)

Для того чтобы нарисовать фрактал, необходимо вызвать процедуру ШАГ, установив соответствующие значения ее аргументов: ШАГ(x1,y1,x2,y2,0). Параметр num показывает степень детализации расчета дерева. Это значение можно использовать для прекращения итеративного процесса.

Завершение циклов итерации в нашем алгоритме происходит тогда, когда длина ветви становится меньше некоторой величины lmin.

Тексты программ для построения фрактальных


изображений

Программа для построения фрактала Мандельброта

Program fr_mandelbrot;

uses crt,graph;

const mi=511;

var gd,gm:integer;

function c(index:integer):integer; {определение цвета точки}

begin

c:=1*(mi-index)



end;

{** функция подсчета количества итераций **}

function iteration(x,y:double):integer;

var i:integer; xx,yy,xk,yk:double;

begin

xx:=x; yy:=y; i:=0;



while (sqr(xx)+sqr(yy)<=4) do

begin


xk:=sqr(xx)-sqr(yy)+x;

yk:=2*xx*yy+y;

xx:=xk; yy:=yk; i:=i+1;

if i>=mi then break

end;

iteration:=i;



end;

{*** процедура формирования фрактала ***}

procedure mand(xx,yy,cx,cy:integer; minx,maxx,miny,maxy:double);

var stepx, stepy,x,y:double; i,j,iter:integer;

begin

stepx:=(maxx-minx)/cx;



stepy:=(maxy-miny)/cy;

y:=miny;


for j:=0 to cy do

begin


x:=minx;

for i:=0 to cx do

begin

iter:=iteration(x,y);



putpixel(xx+i,yy+j,c(iter));

x:=x+stepx;

end;

y:=y+stepy



end;

end;


begin

gd:=Detect;

initgraph(gd,gm,'C:\BP\BGI');

setBkcolor(1);

{формирование фрактала с разной степенью детализации}

mand(0,0,640,480,-2.2,1,-1.2,1.2); {весь фрактал}

readkey;

cleardevice;

{увеличенные фрагменты фрактала}

mand(0,0,640,480,-0.85,-0.7,0.1,0.25);

readkey;

cleardevice;

mand(0,0,640,480,-0.8,-0.7,0.2,0.3);

readkey;


cleardevice;

mand(0,0,640,480,-1.25,-1,-0.5,-0.25);

readkey;

cleardevice;

mand(0,0,640,480,-1.05,-1,-0.35,-0.3);

readkey;


closegraph;

end.


Программа для построения фрактала Джулиа

Program fr_Julia;

uses crt,graph;

const mi=511;

var gd,gm:integer;

function c(index:integer):integer; {определение цвета точки}

begin

c:=7*(mi-index)



end;

{** функция подсчета количества итераций **}

function iteration(x,y:double):integer;

const cx=0.36;cy=0.36;

var i:integer; xx,yy,xk,yk:double;

begin


xx:=x; yy:=y; i:=0;

while (sqr(xx)+sqr(yy)<=4) do

begin

xk:=sqr(xx)-sqr(yy)+cx;



yk:=2*xx*yy+cy;

xx:=xk; yy:=yk; i:=i+1;

if i>=mi then break

end;


iteration:=i;

end;


{*** процедура формирования фрактала ***}

procedure julia(xx,yy,cx,cy:integer; minx,maxx,miny,maxy:double);

var stepx, stepy,x,y:double; i,j,iter:integer;

begin


stepx:=(maxx-minx)/cx;

stepy:=(maxy-miny)/cy;

y:=miny;

for j:=0 to cy do

begin

x:=minx;


for i:=0 to cx do

begin


iter:=iteration(x,y);

putpixel(xx+i,yy+j,c(iter));

x:=x+stepx;

end;


y:=y+stepy

end;


end;

begin


gd:=Detect;

initgraph(gd,gm,'C:\BP\BGI');

setBkcolor(1);

{формирование фрактала с разной степенью детализации}

julia(0,0,640,480,-1,1,-1.2,1.2); {весь фрактал}

readkey;


cleardevice;

{увеличенные фрагменты фрактала}

julia(0,0,640,480,-0.1,0.1,-0.1,0.1);

readkey;


cleardevice;

julia(0,0,640,480,-1,0,-1.2,0);

readkey;

cleardevice;

julia(0,0,640,480,-1,-0.5,-0.5,0);

readkey;


cleardevice;

julia(0,0,640,480,-0.75,-0.06,-0.5,-0.35);

readkey;

cleardevice;

julia(0,0,640,480,-0.68,-0.65,-0.37,-0.36);

readkey;


closegraph;

end.


Программа для построения фрактала Кох

Program fr_kox;

uses graph,crt;

var x0,y0,x,y,gd,gm:integer;x1,y1:real;

{*** рекурсивная процедура построения линии Коха ***}

procedure kox(xn,yn,xk,yk:real);

var x2,y2,x3,y3,x4,y4:real; c:char;

begin


if abs(xn-xk)<2 then exit;

x2:=xn+(xk-xn)/3; y2:=yn+(yk-yn)/3;

x3:=xn+(xk-xn)*2/3; y3:=yn+(yk-yn)*2/3;

x4:=x2+(x3-x2)*cos(pi/3)+(y3-y2)*sin(pi/3);

y4:=y2-(x3-x2)*sin(pi/3)+(y3-y2)*cos(pi/3);

line(round(x2),round(y2),round(x4),round(y4));

line(round(x3),round(y3),round(x4),round(y4));

if keypressed then halt;

kox(xn,yn,x2,y2); {рекурсивные вызовы}

kox(x2,y2,x4,y4);

kox(x4,y4,x3,y3);

kox(x3,y3,xk,yk);

end;

begin


x0:=50; y0:=250;

x:=590; y:=250;

gd:=Detect;

initgraph(gd,gm,'C:\BP\BGI');

setcolor(10);

line(x0,y0,x,y);

kox(x0,y0,x,y); {Рисование фрактала - линии Коха}

readkey;


cleardevice;

{Рисование фрактального треугольника с использованием}

{процедуры для построения линии Коха}

x0:=150; y0:=320;

x:=490; y:=320;

x1:=x0+(x-x0)*cos(pi/3)+(y-y0)*sin(pi/3);

y1:=y0-(x-x0)*sin(pi/3)+(y-y0)*cos(pi/3);

kox(x0,y0,x1,y1);

kox(x1,y1,x,y);

kox(x,y,x0,y0);

readkey;

closegraph

end.
Программа для построения ветки папоротника

Program fr_paporotnik;

uses crt, graph;

const alfa=80;beta=2.1; k=0.3; k1=0.5; lmin=1;

var a,b,c,d,e,f,g,h:real; gd,gm:integer;

{*** рекурсивная процедура на основе метода IFS ***}

procedure step(x1,y1,x2,y2:real; nom:integer);

var x3,y3,x4,y4,x5,y5,x6,y6,x7,y7:real;

begin

if sqr(x1-x2)+sqr(y1-y2)>lmin then



begin

{координаты точек вычисляются по формулам}

x3:=(x2-x1)*a-(y2-y1)*b+x1; y3:=(x2-x1)*b+(y2-y1)*a+y1;

x4:=x1*c+x3*d; y4:=y1*c+y3*d;

x5:=x4*e+x3*f; y5:=y4*e+y3*f;

x6:=(x5-x4)*g-(y5-y4)*h+x4; y6:=(x5-x4)*h+(y5-y4)*g+y4;

x7:=(x5-x4)*g+(y5-y4)*h+x4; y7:=(x5-x4)*(-h)+(y5-y4)*g+y4;

line(round(x1),round(y1),round(x4),round(y4));

{рекурсивные вызовы для рисования фрагментов фрактала}

step(x4,y4,x3,y3,nom);

step(x4,y4,x6,y6,nom+1);

step(x4,y4,x7,y7,nom+1);

end;

end;


begin

gd:=Detect;

initgraph(gd,gm,'C:\BP\BGI');

setBkcolor(1);

{вычисление коэффициентов}

a:=cos(pi/alfa); b:=sin(pi/alfa);

c:=1-k; d:=k;

e:=1-k1; f:=k1;

g:=cos(pi/beta); h:=sin(pi/beta);

step(200,350,225,70,0); {рисование ветки папоротника}

readkey;

closegraph

end.
Программа построения треугольника Серпинского

program fr_treug_serpinsky;

uses graph,crt;

const m=2500; { количество точек фрактала }

type koord=array[1..3] of integer;

var gd,gm: integer;

x,y: koord; { массивы координат }

{**** Процедура заполнения заданного треугольника точками ****}

procedure serpinsky(xs,ys:koord);

var x0,y0,xk,yk: real; n,k: integer;

begin

randomize;



x0:=(xs[1]+xs[2]+xs[3])/3; { координаты начальной точки }

y0:=(ys[1]+ys[2]+ys[3])/3;

for k:=1 to m do

begin


n:=random(3)+1; { случайная вершина }

xk:=(x0+xs[n])/2; { середина отрезка, соединяющего }

yk:=(y0+ys[n])/2; { начальную точку с вершиной }

putpixel(round(xk), round(yk), 12); { вывод точки }

x0:=xk; { новые координаты для начальной точки }

y0:=yk


end;

end;


begin

gd:=Detect;

initgraph(gd,gm,'C:\BP\BGI');

setcolor(10);

setviewport(20,20,500,250, true);

x[1]:=320; y[1]:=50; { координаты вершин треугольника }

x[2]:=150; y[2]:=200;

x[3]:=450; y[3]:=200;

serpinsky(x,y); { процедура вывода треугольника Серпинского }

readkey;


closegraph

end.