Материал: Создание фракталов

Рис 9. Участок границы множества Мандельброта, увеличенный в 200 pаз

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

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

Кривая Коха, как бы ни была похожа на границу берега, не может выступать в качестве её модели из-за того, что она всюду одинакова, самоподобна, слишком «правильна». Все природные объекты создаются по капризу природы, в этом процессе всегда есть случайность. Фракталы, при построении которых в итеративной системе случайным образом изменяются какие-либо параметры, называются стохастическими. К этому классу фракталов относится и фрактальная монотипия, или стохатипия <#"786118.files/image012.gif">

Рис.10. Рандомизированный фрактал на основе множества Жюлиа

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

Плазма

Типичный представитель данного класса фракталов "Плазма". Для её построения возьмём прямоугольник и для каждого его угла определим цвет. Далее находим центральные точки прямоугольника и его сторон, и раскрашиваем их в цвет, равный среднему арифметическому цветов по углам прямоугольника плюс некоторое случайное число, пропорциональное размеру разбиваемого прямоугольника. Прямоугольник разбиваем на 4 равных прямоугольника, к каждому из которых применяется та же процедура. Далее процесс повторяется. Чем больше случайное число - тем более «рваным» будет рисунок.

Рис.11. Плазма

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

Системы итерируемых функций

Метод "Систем Итерируемых Функций" (Iterated Functions System - IFS) появился в середине 80-х годов как простое средство получения фрактальных структур.

В программе IFS Builder 3d собраны последние достижения в области трёхмерного фракталостроительства. С помощью IFS Builder 3d, можно строить трехмерные фракталы, стереоизображения (т. е. 2 изображения, посмотрев сквозь которые, можно увидеть одно трёхмерное) и анимации фракталов - их движение, полёт в глубь и морфинг (изменения формы и превращения одного фрактала в другой).представляет собой систему функций из некоторого фиксированного класса функций, отображающих одно многомерное множество на другое. Наиболее простая IFS состоит из аффинных преобразований плоскости:

X' = A*X + B*Y + C

Y' = D*X + E*Y + F

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

На основании этих идей Барнсли и Слоан создали алгоритм, который, по их утверждению, позволит сжимать информацию в 500-1000 раз. Вкратце метод можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), т.е. коэффициентами этих преобразований (в нашем случае A,B,C,D,E,F).

Например, закодировав какое-то изображение двумя аффинными преобразованиями, мы однозначно определяем его с помощью 12-ти коэффициентов. Если теперь задаться какой-либо начальной точкой (например, X=0 Y=0) и запустить итерационный процесс, то мы после первой итерации получим две точки, после второй - четыре, после третьей - восемь и т.д. Через несколько десятков итераций совокупность полученных точек будет описывать закодированное изображение. Но проблема состоит в том, что очень трудно найти коэффициенты IFS, которая кодировала бы произвольное изображение.

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

X' = (A1*X + B1*Y + C1) / (D1*X + E1*Y + F1)

Y' = (A2*X + B2*Y + C2) / (D2*X + E2*Y + F2)

или квадратичные:

X' = A1*X*X + B1*X*Y + C1*Y*Y + D1*X + E1*Y + F1

Y' = A2*X*X + B2*X*Y + C2*Y*Y + D2*X + E2*Y + F2

преобразования на плоскости.

В качестве примера использования IFS для построения фрактальных структур, рассмотрим кривую Коха (Рис.2{пункт «геометрические фракталы»}) и "дракона" Хартера-Хейтуэя (Рис.5{пункт «геометрические фракталы»}). Выделим в этих структурах подобные части и, для каждой из них вычислим коэффициенты аффинного преобразования. В аффинный коллаж будет включено столько аффинных преобразований, сколько существует частей подобных целому изображению.

Рис 12. Заготовка для построения IFS "дракона" Хартера-Хейтуэя

Построим IFS для "дракона" Хартера-Хейтуэя. Для этого расположим первое поколение этого фрактала на сетке координат дисплея 640 x 350 (Рис.12). Обозначим точки получившейся ломаной A, B, C. По правилам построения ({пункт «геометрические фракталы»}) у этого фрактала две части, подобные целому - на рис.12 это ломаные ADB и BEC. Зная координаты концов этих отрезков, можно вычислить коэффициенты двух аффинных преобразований, переводящих ломаную ABC в ADB и BEC:

X' = -0.5*X -0.5*Y + 490

Y' = 0.5*X -0.5*Y + 120

X' = 0.5*X -0.5*Y + 340

Y' = 0.5*X +0.5*Y - 110

Задавшись начальной стартовой точкой (например, X=0 Y=0) и итерационно действуя на нее этой IFS, после десятой итерации на экране получим фрактальную структуру, изображенную на рис.13, которая представляет собой "дракон" Хартера-Хейтуэя. Его кодом (сжатым описанием) является набор коэффициентов двух аффинных преобразований.

Рис 13. "Дракон" Хартера-Хейтуэя, построенный с помощью IFS в прямоугольнике 640x350

Аналогично можно построить IFS для кривой Кох. Нетрудно видеть, что эта кривая имеет четыре части, подобные целой кривой ({пункт «геометрические фракталы»} рис.2). Для нахождения IFS опять расположим первое поколение этого фрактала на сетке координат дисплея 640 x 350 (Рис.14).

Рис 14. Заготовка для построения IFS кривой Кох

Для ее построения требуется набор аффинных преобразований, состоящий из четырех преобразований:

X' = 0.333*X + 13.333' = 0.333*Y + 200' = 0.333*X + 413.333' = 0.333*Y + 200' = 0.167*X + 0.289*Y + 130' = -0.289*X + 0.167*Y + 256' = 0.167*X - 0.289*Y + 403' = 0.289*X + 0.167*Y + 71

Результат применения этого аффинного коллажа после десятой итерации можно увидеть на рис.15.

Рис 15. Кривая Кох, построенная с помощью IFS в прямоугольнике 640x350

Использование IFS для сжатия обычных изображений (например, фотографий) основано на выявлении локального самоподобия, в отличие от фракталов, где наблюдается глобальное самоподобие и нахождение IFS не слишком сложно (мы сами в этом убедились). По алгоритму Барнсли происходит выделение в изображении пар областей, меньшая из которых подобна большей, и сохранение нескольких коэффициентов, кодирующих преобразование, переводящее большую область в меньшую. Требуется, чтобы множество "меньших" областей покрывало все изображение. При этом в файл, кодирующий изображения будут записаны не только коэффициенты, характеризующие найденные преобразования, но и местоположение и линейные размеры "больших" областей, которые вместе с коэффициентами будут описывать локальное самоподобие кодируемого изображения. Восстанавливающий алгоритм, в этом случае, должен применять каждое преобразование не ко всему множеству точек, получившихся на предыдущем шаге алгоритма, а к некоторому их подмножеству, принадлежащему области, соответствующей применяемому преобразованию.

системы

Любителям фракталов и математических картинок известны фантастические изображения растений, полученные с помощью программ. Это так называемые L-системы. В основе их построения лежат два принципа. Первый - это так называемая «черепашья графика» (оператор draw) патриарха GWBASIC и его детей Turbo Basic и QBasic, когда движение рисуется пошагово в приращениях относительно текущей точки. Либо моделируется данное поведение, задавая движение в приращениях координат. Второй принцип - изюминка метода: каждое единичное движение заменяется на весь рисунок. Например, нарисуем вилку-рогатульку. На следующем шаге работы программы каждая из трех палочек вилки заменяется такой же вилкой, превращая вилку в ветку с сучками, после следующего шага получим лохматый куст, потом пушистое дерево, красивое, фрактальное. Меняя вид начальной картинки можно получать самые разные изображения от зонтиков укропа до колючего перекати-поле или пучка водорослей.

Суть L-кодирования сводится к следующему. Представим себе некое виртуальное программируемое устройство, состоящее из пера, управляющего им механизма и листа бумаги. Управляющий пером механизм способен исполнять несколько команд. А именно: он может опустить перо на бумагу и вычертить прямой отрезок заданной длины в направлении текущей ориентации пера (команда F). Он может изменить ориентацию пера по отношению к текущей на какой-то заданный относительный угол по часовой или против часовой стрелки (команды + и -). Он может также запоминать (заносить в стек) свое текущее состояние (команда [) и вспоминать (извлекать из стека) ранее запомненное состояние (команда ]). Под состоянием в данном случае понимается тройка чисел (x, y, a), где x и y - это координаты пера и а - это угол, определяющий направление ориентации пера. Таким образом, задав некое начальное направление а0, определив относительный угол поворота в 900 и задав длину отрезка, при помощи последовательности команд F+F+ F+F мы можем нарисовать квадрат. Определив относительный угол поворота в 600, при помощи последовательности команд F++F++F можно нарисовать равносторонний треугольник.

Предположим также, что в программы для нашего виртуального устройства, кроме пяти перечисленных команд, можно включать любые другие символы, которые управляющий механизм будет просто игнорировать. То есть если мы введем программу F+BF+CCF+CF, то устройство все равно нарисует квадрат. Теперь мысленно оснастим наше устройство приставкой, которая перед тем, как передать введенную программу на управляющий механизм, может заданное число раз просматривать ее, и при каждом очередном просмотре заменять любые символы последовательности по предварительно указанным правилам. Исходную программную последовательность символов теперь будем называть аксиомой. Например, введем аксиому FB+, и определим правило B < F+FB. Зададим также количество просмотров, равное, например, двум. Тогда на входе механизма после обработки введенной аксиомы приставкой получим последовательность FF+FF+FB+. Вот, собственно, и все. При помощи описанного несложного виртуального устройства можно строить множество самых разнообразных фрактальных форм - от традиционных математических фракталов, таких, как, например, снежинка Коха или кривая Гильберта, до структур, очень напоминающих растительную или подводную жизнь. Можете посмотреть на исходный код программы, объясняющий вышесказанное

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

Рассмотрим, как кодируются L-системы в общепринятых обозначениях.

Движение вперед обозначается буквой F (Forward - вперед), поворот по часовой стрелке обозначим «+», а против - «-», причем само значение поворота задается в программе и постоянно для всех движений. Буквой В (Back- назад) обозначается возврат без прорисовки, нам это не пригодится.

Для нас важнее механизм возврата. Точка, в которую надо возвращаться, обозначим «[», а место, откуда происходит возврат, обозначим «]». Тогда вилка будет иметь вид: F - движение вперед [ - запомнить позицию + - поворот вправо на 22.5 (например) градусов F - движение вперед после поворота ] - возврат в запомненную позицию [ - запомнить позицию - - поворот влево относительно направления в запомненной точке F - движение вперед после поворота] - возврат в запомненную позицию. Это движение можно закодировать. Можно и более сложное. Можно закодировать и следующий шаг - замену каждого прямого отрезка на такую же вилку. Два шага нарисуют три шага, три шага - четыре шага. Прорисовывать каждый шаг заменой текста программы довольно утомительно, и мы вспоминаем о рекурсии. Выполнив необходимые объявления переменных и передаче значений координат точек возврата, мы добиваемся, что любое дерево рисуется по заранее заданной формуле одной маленькой процедурой, которая сама себя и вызывает. Программа позволит вам с восхищением (ибо порядок прорисовки фрактально непредсказуем) отслеживать на экране рост дерева.

Запустив программу, вы увидите, как она нарисует ветку, клонимую ветром. Меняя переменную Kmax можно уменьшать или увеличивать глубину рекурсии, или, что тоже самое, «пушистость» ветки. А меняя закон движения можно получать самые удивительные и фантастические изображения.

Таким образом, суть L - системы состоит в том, что имеется определенных набор символов системы, каждый из которых обозначает определенное действие и набор правил преобразования символов.

Применение фракталов

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

Кроме того, фракталы находят применение в децентрализованных компьютерных сетях и «фрактальных антеннах». Весьма интересны и перспективны для моделирования различных стохастических (не детерминированных) «случайных» процессов, так называемые «броуновские фракталы». В случае нанотехнологии фракталы тоже играют важную роль, поскольку из-за своей иерархической самоорганизации многие наносистемы обладают нецелочисленной размерностью, то есть являются по своей геометрической, физико-химической или функциональной природе фракталами. Например, ярким примером химических фрактальных систем являются молекулы «дендримеров <#"786118.files/image025.gif">