Фрактальный генератор Коха для ковра Серпинского

ФРАКТАЛЬНЫЙ ГЕНЕРАТОР КОХА ДЛЯ КОВРА СЕРПИНСКОГО

А.А. Виноградова, Д.Н. Калитеевский Научный руководитель - д.т.н., профессор В.М. Мусалимов

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

Введение

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

Структуры, похожие на фракталы, можно обнаружить в окружающей нас природе: границы облаков, границы морских побережий, турбулентные потоки в жидкостях, трещины в некоторых породах, зимние узоры на стекле, изображения структуры некоторых веществ, полученные с помощью электронного микроскопа, кровеносная система сердечной мышцы и т.д. Хорошим примером может служить кривая Коха [2]. В 1904 г. математик Кох дал пример кривой, которая нигде не имеет касательной. Это кривая, состоящая из частей, каждая из которых - бесконечной длины. Также в 1915 г. польский математик Вацлав Серпинский представил множество, получаемое путем удаления из равностороннего треугольника подобных ему треугольников (ковер Серпинского) [2]. Важно, что в нем самоподобие сочетается с симметрией поворота.

Понятие «фрактал» уже доказало свою пользу в ряде прикладных областей. Фракталы используются при анализе и классификации сигналов сложной формы, возникающих в разных областях, например при анализе колебаний курса валют в экономике. Они применяются в физике твердого тела, в динамике активных сред и т. д.

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

Фрактальная размерность

Пусть d - обычная евклидова размерность пространства, в котором находится наш фрактальный объект (d=1 - линия, d =2 - плоскость, d =3 - обычное трехмерное пространство). Теперь покроем этот объект целиком d -мерными шарами радиуса l. Предположим, что нам для этого потребовалось не менее, чем N(l) шаров. Тогда, если при достаточно малых l величина N(l) меняется по степенному закону

N

то D называется хаусдорфовой или фрактальной размерностью этого объекта. Эта формула эквивалентна соотношению N « (R /1)D, использованному для определения береговой линии [3].

Формулу (1) можно переписать также в виде

7Л Г ln N

D = lim-

lnl

Это служит общим определением фрактальной размерности D. В соответствии с ним величина D является локальной характеристикой данного объекта.

Разберем некоторые классические примеры регулярных фракталов. Пусть на некотором этапе покрытия фрактала пришлось использовать, как минимум, N (/) таких элементов характерного размера /, а на другом N (/') элементов размера /'. Тогда величина фрактальной размерности может быть вычислена по формуле

V N (/'),

D = - lim .

'0 ЧЙ

Эту формулу можно переписать в виде:

N (/) = ( Г1D

N

что является следствием выражения (1).

Несложно рассчитать фрактальную размерность для кривой Коха. Построение кривой похоже на строение точек множества Кантора. Начинаем с отрезка-основы: удаляем его среднюю третью часть и заменяем ее сторонами равностороннего треугольника (рис. 1).

Рис. 1. Последовательные приближения кривой Коха

Мысленно можно представить кривую Коха как предел таких операций. Если основа имеет длину 1, то фрагмент будет состоять из четырех отрезков, каждый длины 1/ 3 и, следовательно, общей длины 4/ 3. На следующем шаге получаем ломаную, состоящую из 16 отрезков и имеющую общую длину 16/ 9 или (4/ 3)2 и т.д. Так как на каждом шаге

1п4 _ 1п42 _

Шэ _Шз7_ .. ,

то можно применить формулу (2). Так как предел / ^ 0 соответствует п ^ да, то фрактальная размерность равна 1п4

Б _-_ 1.26....

1п3

Ковер Серпинского - это регулярный фрактал, который получается последовательным вырезанием равносторонних треугольников (рис. 2). Здесь на нулевом шаге имеется один равносторонний треугольник с длиной стороны / _ 1, а на следующем - три равносторонних треугольника со сторонами /'_ 1/2. Поэтому / _ 1, N(/) _ 1, а /'_ 1/2, N(/') _ 3. Тогда фрактальная размерность

1 "5

D = — = 1,5849.

ln2

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

AAA

Рис. 2. Построение салфетки Серпинского Применение фрактального генератора Коха для ковра Серпинского

При помощи программирования в М-файлах системы MATLAB была выведена кривая Коха (рис. 3).

Построение кривой Коха начинается с прямолинейного отрезка единичной длины. Исходный отрезок называется затравкой и может быть заменен каким-нибудь многоугольником. Затравка - это нулевое поколение кривой Коха. Затем каждое звено затравки мы заменяем образующим элементом, n=1. В результате этого получаем первое поколение - кривую из четырех прямолинейных звеньев. Следующее поколение получается при замене каждого прямолинейного звена уменьшенным образующим элементом. В результате получаем кривую второго поколения, n=2. В MATLAB мы вывели кривую пятого поколения (рис. 3).

Рис. 4. Салфетка Серпинского

Рис. 5. Применение кривой Коха для ковра Серпинского

Также в системе MATLAB был выведен ковер Серпинского. Построение начинается с равностороннего треугольника. Из него удаляется перевернутый равносторонний треугольник со стороной, равной половине длины стороны исходного треугольника. У нас остаются три равносторонних треугольника со сторонами, вдвое меньшими стороны исходного треугольника. Повторив эту операцию 5 раз, мы получаем ковер Серпинского, показанный на рис. 4. Затем, совмещая две программы построения и совмещая координаты построения кривой Коха и ковра Серпинского, получаем изображение, приведенное на рис. 5. Ниже приведена программа для построения этого изображения в системе MATLAB. function z=Koch(N);

x1=0; y1=0; x2=0.5; y2=cos(pi/6); figure (1);

axis ([-0.19 1.19 -0.29 1.09]); hold on;

set(gca, ,xtick',[],'ytick,,[]); set(gca, 'XColor', 'w', 'YColor', W) Coord (x1,y1,x2,y2,4); Coord (x2+x2,y1,x1,y1,4); Coord (x2,y2,x2+x2,y1,4); Serpinsky(x1,y1,x2,y2,x2+x2,y1,5); function z=Coord (x1,y1,x2,y2,n) if n>0

dx=(x2-x1)/3; dy=(y2-y1)/3;

x1n=x1+dx; y1n=y1+dy;

x2n=x1+2*dx; y2n=y1+2*dy;

xmid=dx/2-dy*sin(pi/3)+x1n;

ymid=dy/2+dx*sin(pi/3)+y1n;

Serpinsky(x1n,y1n,x2n,y2n,xmid,ymid,n);

Coord(x1,y1,x1n,y1n,n-1);

Coord(x1n,y1n,xmid,ymid,n-1);

Coord(xmid,ymid,x2n,y2n,n-1);

Coord(x2n,y2n,x2,y2,n-1);

else

hold on;

r1=[x1 y1]; r2=[x2 y2]; R=cat(1,r1,r2); plot (R(:,1), R(:,2), 'Color','kj,

end; z=1;

end;

end;

function z=Serpinsky(x1,y1,x2,y2,x3,y3,Lmax); h= figure (1); hold on;

fill ([x1 x2 x3],[y1 y2 y3],'k0; Simplex (x1,y1,x2,y2,x3,y3,0,Lmax); hold off;

function z=Simplex(x1,y1,x2,y2,x3,y3,m,Lmax); if m<Lmax;

x1m=(x1+x2)/2; y1m=(y1+y2)/2; x2m=(x2+x3)/2; y2m=(y2+y3)/2; x3m=(x3+x1)/2; y3m=(y3+y1)/2;

fill([x1m x2m x3m],[y1m y2m y3m],'w) m=m+1;

Simplex(x1,y1,x1m,y1m,x3m,y3m,m,Lmax); Simplex(x1m,y1m,x2,y2,x2m,y2m,m,Lmax); Simplex(x3m,y3m,x2m,y2m,x3,y3,m,Lmax);

end;

end;

end;

Заключение

В работе были рассмотрены примеры фракталов (Коха и Серпинского). В ходе данной работы были приведены расчеты фрактальной размерности, в том числе для кривой Коха (D = 1,26 ) и для ковра Серпинского ( D = 1,5849 ).

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

Литература

1. Мандельброт Б.Б. Фрактальная геометрия природы. - М.: -Ижевск, Ин-т комп. ис-след., 2002. - 666 с.

2. Морозов А.Д. Введение в теорию фракталов - М.: -Ижевск, 2002. - 163 с.

3. Федер Е. Фракталы. - М.: Мир, 1991. - 260с.

4. Шредер М. Фракталы, хаос, степенные законы. - Ижевск: НИЦ «РХД», Ижевская республиканская типография, 2001. - 528 с.