Реализация фракталов в информатике

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Реализация фракталов в информатике

Студент

Остриков Константин

Оглавление

• Определение и классификация фракталов
• Геометрические фракталы
• Стохастические фракталы
• Алгебраические фракталы
• Множество Мандельброта
• Множество Жулиа
• Другие способы получения алгебраических фракталов
• Метод побитовых операций
• Ещё фракталы
• Реализация
• Реализация алгебраических фракталов
• фрактал алгебраический стохастический геометрический
• Определение и классификация фракталов

Фракталы - геометрические самоподобные объекты с нецелыми коэффициентами размерности.То есть некоторая часть этого объекта в точности повторяет форму целого, но имеет размер в нецелое количество раз меньший.

По построению фракталы можно разделить на геометрические и алгебраические.

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

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

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

Пример: отрезок Коха.

Первоначальная фигура - отрезок.

Она заменяется фигурой:

Затем каждый из отрезков данной фигуры заменяется на подобный ей:

Далее происходит ещё одна итерация:

И через бесконечное количество итераций получается что-то вроде вот этого:

Посчитаем коэффициент самоподобия.

Каждый раз мы меняем отрезок на образующую фигуру. Причём эта фигура каждый раз уменьшается ровно в три раза. Коэффициент подобия равен одна треть.

Так как в каждой новой фигуре ровно 4 элемента, которые будут потом заменяться, то есть отрезков, то коэффициент самоподобия равен. Четыре трети это не целое число, значит эта фигура - фрактал по определению. Коэффициент размерности d = log ₃ 4 (из уравнения Nr^d = 1, где N = 4 , r = )

Если первоначальной фигурой взять не отрезок, а правильный треугольник, то получится так называемая Снежинка Коха:

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

Коэффициент самоподобия здесь , так как здесь так же подобие в 2 раза, а объект превращается в 3 треугольника. Коэффициент размерности, соответственно, log ₂ 3

Так же геометрически строятся стохастические фракталы.

Стохастические фракталы

Если некоторый параметр в итерациях выбирается случайно, как то: угол наклона, длина, то фрактал получается не симметричным, и называется стохастическим.

Примером стохастического фрактала в природе является дерево. Каждая ветвь, по сути, подобна целому дереву - на ней так же есть более мелкие ветки. Но длина и вообще наличие этих веток - довольно случайная величина.

Сначала покажу, как построить обычное фрактальное дерево без стохастических построений.

Будем менять верхние веточки на подобную этой фигуру. Через несколько итераций получим такое дерево:

Остаётся заменить последние веточки листиками, а отрезки чем-то, покрытым корой - и дерево готово.

Если же длину отрезков и/или угол между новыми веточками задавать случайно, то дерево получится более натуральное:

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

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

Существует также другой способ построения фракталов.

Для каждой точки комплексной плоскости определяется, лежит ли она во фрактале, или нет. Каким образом это делается.

Фрактал определяется некоторой формулой w = f(z) в поле комплексных чисел. Для того, чтоб определить, лежит ли некоторая точка во фрактале, необходимо провести бесконечное количество итераций такого вида z:=f(z), т.е. цепочка z, f(z), f(f(z), f(f(…f(z))…) (эти числа проще обозначить за Z₀, Z₁, Z₂, …, Z_n) Если на бесконечной итерации полученное число является бесконечностью, то точка НЕ лежит во фрактале. Если же последовательность итераций сходится к какому-то комплексному числу, или хотя бы ограничена каким-то действительным радиусом, то точка лежит во фрактале и будет чёрной.

Множество Мандельброта

Формула такова: W=Z²+C.

Для каждой точки A плоскости полагаем С=А, Z₀=0. Теперь для любой точки A можно узнать, лежит ли она во множестве Мандельброта.

Узнаем, например, лежит ли точка 1+i во множестве.

Z₀=0; C=1+i; Z₁=f (Z₀) = 0² + (1+i) = 1+i;

Далее:

Z₁=1+i; C=1+i; Z2=f (Z1) = (1+i) ² + (1+i) =1 + 3*i;

Можно и далее продолжать эти операции, но есть теорема, которая гласит, что для множества Мандельброта «бесконечностью» является 2, т.е. если на какой-то итерации функция дала значение, по модулю большее, чем 2 (а модуль числа 1+3*i равен > 2), то далее она уйдёт в бесконечность.

А для точки 0.

Z₀=0; C=0; Z1=f (Z0) = 0²+0 = 0

Очевидно, что и далее будут только нули, то есть при C=0 любое Z_i=0. Значит, последовательность сходится в нуле, ограничена радиусом 0 и не уходит в бесконечность, а значит, 0 принадлежит множеству Мандельброта.

Множество Жулиа

Если использовать ту же формулу, но с такой вариацией: С - фиксированная точка, а Z₀=A, то получаются многочисленные множества Жулиа, вид которых зависит от того, какую точку С мы взяли. Самые красивые множества Жулиа получаются, если точку С взять ближе к границе множества Мандельброта. Пример:

При С = :

Теперь следует объяснить происхождение остальных цветов на рисунке.

Чем раньше Z_i становится по модулю больше, чем 2, тем цвет светлее. Почему зелёный «светлее» охры см. ниже.

Другие способы получения алгебраических фракталов

Я определил алгебраические фракталы как те, которые состоят их точек комплексной плоскости, у которых бесконечный ряд, определённый реккурентной формулой, ограничен. Но можно расширить это определение:

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

Метод побитовых операций

Например, мне в голову пришёл такой фрактал. Для каждой точки A комплексной плоскости мы считаем функцию f (A) = Re(A) & Im(A) , где & - операция побитового И.

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

3,25₁₀=11,01₂7,5₁₀=111,1₂3₁₀=11₂

Таким образом переводим действительную и мнимую части числа в двоичную систему, записываем друг под другом и побитово делаем операцию И:

011,01₂111,10_{2__________}011,00₂

То есть, для

A = 3,25 + 7,5*if (A) = 3

Теперь, простейший способ определения фрактала: если f (A) = 0, то A входит во фрактал, иначе - нет. Получается треугольник Серпинского, если за начальный треугольник принимать не равносторонний, а прямоугольный равнобедренный, причём бесконечный:

Если же вводить всякие вариации на эту тему, например, определять цвет в RGB как

(Re (A) & Im (A) * q) mod 2^24, где q - случайное большое число,

то будут появляться причудливые фракталы такого рода:

(Здесь q = 15508215)

Цвет не лишён некоторой стохастичности: умножение на большое число и взятие по модулю несколько схоже с генератором случайных чисел.

Если использовать не побитовое И, а операцию XOR, то получится что-то такое:

Ещё фракталы

Это функция

где a_i(x) - i-ое неполное частное непрерывной дроби числа x.

Реализация

Я реализовывал все перечисленные фракталы в среде Borland Delphi.

Реализация геометрических, побитовых и музыкальных фракталов сложности не составляет сложностей:

1. Геометрические фракталы реализуются «в лоб», как и написано, итеративно. Для ускорения лишь стоит не прорисовывать изначальные объекты, а потом стирать, нужно лишь держать их координаты в памяти. Прорисовывать же только те, что остаются на какой-нибудь большой итерации. Например, для снежинки Коха можно хранить список отрезков. На каждой итерации проходим по всему списку и заменяем каждый элемент списка на 4 новых элемента, т.е. отрезки, в которые он превращается. Когда длина списка будет довольно большой, пробегаем во всему списку и рисуем отрезки, которые хранятся в элементах списка.

2. Побитовые фракталы реализуются, например, попиксельно:

for x := 0 to ClientWidth do for y := 0 to ClientHeight do if (x and y = 0) then MyForm.MyPaintBox.Canvas.Pixels [x,y] := clBlack;

В случае «вариаций» следует заменить последнюю строчку на

begin q := random(Maxint); MyForm.MyPaintBox.Canvas.Pixels[x,y] := q * (x and y);end;

Так же and можно заменить на xor, или любую другую побитовую операцию.

3. Музыкальные фракталы реализуются так: выбирается какой-то маленький шаг по оси x, и для всех x от 1 до 2 находится y и соответствующая точка ставится на график (для каждой полученной точки, определяется соответствующая ей точка на мониторе ).

Хотелось бы остановиться на реализации алгебраических фракталов.

Реализация алгебраических фракталов

Написанная мной программа довольно сложна в понимании, поскольку имеет очень много кнопочек.

Кнопка Paint - нарисовать фрактал с заданными Вами ниже параметрами.

· Программа работает с фракталами вида (Zⁿ+C^k) * V^m

· Далее выставляются значения действительной и мнимой частей чисел Z0, C и VМинус означает, что действительная или мнимая часть этого числа будет определяться соответственно действительной или мнимой частью точки A, принадлежность которой к фракталу будет определяться

· Так же выставляются значения n,k,m, которые здесь считаются целыми, хотя ничто не мешает мне изменить программу так, чтоб они были не обязательно целыми.

· Далее следуют значения, которые определяют, какой прямоугольный кусок комплексной плоскости будет показан на рисунке. Эти значения X,Y левого верхнего угла и X,Y правого нижнего угла. Ничто не мешает сделать координату Y нижнего угла больше координат верхнего, или координату X левого больше, чем правого, - в таком случае изображение просто будет отражённым.

· Iterations - параметр, который показывает, через сколько итераций компьютер, всё ещё не получивший «бесконечность» решит, что никогда её и не получит и объявит точку чёрной.

· Infinity - параметр, который показывает, какой модуль является «бесконечностью», то есть, если в какой-то момент Z_i по модулю больше этого параметра, компьютер решает, что оно далее улетит в бесконечность. Причём номер этого Z_i, то есть i, он запоминает.

· Далее следует система окраски. В зависимости от того, на какой итерации Z_i превысило infinity, у него выбирается цвет от 1 до iterations. Какие именно это цвета регулируется здесь.По умолчанию выбрана система RGB, т.е. для каждой компоненты цвета распределяются равномерно: т.е. для 30 итераций:

Если поставлена галочка FFFFFF system of color, то RGB переводится в 16-ричный код, который равномерно делится на iterations частей.

· Crazy paint. Пожалуй, самая бессмысленная, но самая сложная в понимании галочка. Дело в том, что когда для некоторого A мы считаем его ряд Z₀, Z₁, Z₂, … Z_iterations, то если A=Z₀, то существует некое A' = Z1(A), у которого Z1(A') = Z2(A), Z2 (A') = Z3(A) и т.д.То есть попутно, определяя цвет точки A, можно определить цвета точек A', A'', A''', и т.д.: если у A итерация вылета равна 17, то у A' - 16, у A'' - 15 и т.д. Правда, если A не уходит в бесконечность, никто не гарантирует, что A' следующей итерацией туда не вылетит (хотя это, по сути, значит, что A тоже бы вылетело в бесконечность, будь iterations больше, но здесь обратная зависимость, что довольно некрасиво реализуемо). Поэтому если A=Z₀, то картинку можно нарисовать быстрее и довольно красивыми россыпями точек, а не унылым «слева направо». Но если Z₀ не равно A, то красивыми россыпями будет рисоваться что-то совсем не то, что нужно, но тоже порой красиво. Поэтому галочка и называется Crazy paint.

· Current location. Эти панели показывают действительную и мнимую части комплексной точки, на которую указывает указатель мыши, если он внутри рисунка.

· Выпадающее меню модулей. Дело в том, что модуль комплексного числа можно определить не только как , но и, например, как

o

o

o

o

o

o

Для удобства Re(Z) обозначено за X, Im(Z) - за Y.Тогда определяться, когда Z_i стало больше infinity по модулю, будет несколько иначе, и раскраска будет несколько другая.

· Следующая панель имеет в виду, что если правой кнопкой мыши щёлкнуть по какой-то точке на рисунке, её координаты (т.е. x=Re(Z) и y=Im(Z)) попадут в поля ввода координат точки C, Координаты точки Z₀ заполнятся минусами, координаты прямоугольника рисунка станут (-2;-2), (2;2), поставится галочка Crazy paint.

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

· Последняя панель - мой копирайт.

Для реализации всех этих функций я написал некоторое количество функций, которые выполняют действия над комплексными переменными (хотя аналогичные, есть в некоторых библиотеках). Присутствуют функции xm, ym, которые восстанавливают соответствующие координаты на мониторе в соответствии со значениями координат прямоугольника рисунка, и обратные им xr и yr, которые восстанавливают значение комплексного числа по его координате на экране. Написано множество функций для реализации того, что указано выше, в общем, ясно как они пишутся. Основная процедура, вызываемая кнопкой Paint, просто перебирает все пиксели, переводит их в реальные xr и ym, для них выполняет итеративный процесс (с некоторыми коррекциями в случае Crazy paint). После того, как рисуется линия для одного xm, делается Refresh, чтобы вывести это на форму, чтоб процесс рисования был виден для пользователя. В качестве небольшой оптимизации по времени, значения из всех полей с формы дублируются локальными переменными. Буфер не используется, хотя можно было бы. Система Windows иногда излишне перегружена непонятно чем, и вместо того, чтоб рисовать, особенно если выбран Crazy paint, особенно, если ресурсы компьютера не такие уж хорошие, предпочитает дождаться, пока изображение дорисуется в оперативной памяти, а уж потом выводить его на экран, что есть печально.

Фракталы поражают своей красотой, примеры программ и принтскринов работы программ, находятся в этой же папке. Если что-то непонятно или интересует - могу объяснить.

Размещено на Allbest