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

 
 
 
 
 
 
 
 
 
 
 
 
 

     Студент

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

 

      Оглавление 

Определение и классификация фракталов

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

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

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

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

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

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

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

Ещё фракталы

Реализация

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

фрактал алгебраический стохастический геометрический

 

      Определение и классификация фракталов 

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

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

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

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

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

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

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

       

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

       

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

       

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

       

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

     

 

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

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

       

      Так как в  каждой новой фигуре ровно 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 – нарисовать фрактал с заданными Вами ниже параметрами.