Приведём два метода построения самоподобных фракталов, известных как IFS-аттракторы.
Метод последовательных приближений
Глядя на эту картинку, нетрудно понять, как можно построить самоподобный фрактал
(в данном случае пирамиду Серпинского).
Нужно взять тетраэдр, удалить середину (октаэдр),
в результате получим четыре маленьких тетраэдра.
С каждым из них мы проделываем ту же самую операцию и т.д.
Пусть это несколько наивное, но наглядное объяснение.
Опишем метод в математических терминах.
Пусть имеется некоторая IFS-система, т.е. система
сжимающих отображений S={S1,...,Sm}
Si:Rn->Rn.
Для данной пирамиды отображения имеют вид
Si(x)=1/2*(x+oi), где
oi - вершины тетраэдра, i=1,..,4.
Выберем некоторое компактное множество A1 в Rn
(в нашем случае выбираем тетраэдр).
Определим по индукции последовательность множеств Ak:
Ak+1=S1(Ak) U...U Sm(Ak).
Множества Ak, называемые итерациями, по теореме Хатчинсона (J. Hutchinson, 1981 г.)
с ростом k всё лучше приближают искомый аттрактор системы S.
Заметим, что каждая из этих итераций является
аттрактором рекуррентной системы итерированных функций
(английский термин Digraph IFS, RIFS и также Graph-directed IFS)
и поэтому их не сложно построить программой IFS Builder 3D.
|
Это наиболее лёгкий для реализации на компьютере метод.
Для простоты рассмотрим случай плоского самоаффинного множества.
Итак, пусть {S1,..,Sm} - некоторая система аффинных сжатий.
Отображения Si представимые в виде:
Si(x)=Ai( x-oi )+oi,
где Ai - фиксированная матрица размера 2x2
и oi - двумерный вектор столбец.
- Возьмем неподвижную точку первого отображения S1 в качестве
начальной точки:
x := o1;
Здесь мы пользуемся тем, что все неподвижные точки
сжатий S1,..,Sm принадлежат фракталу.
Вообще, в качестве начальной точки можно выбрать произвольную точку,
и порожденная ею последовательность точек стянется к фракталу,
но тогда на экране появятся несколько лишних точек.
- Отметим текущую точку x=(x1,x2) на экране:
putpixel(x1,x2,15);
- Выберем случайным образом число j от 1 до m и пересчитаем координаты
точки x:
j:=Random(m)+1;
x:=Sj(x);
- Переходим на шаг 2, либо, если сделали достаточно большое число
итераций, то останавливаемся.
Примечание. Если коэффициенты сжатия отображений Si разные,
то фрактал будет заполняться точками неравномерно.
В случае, если отображения Si являются подобиями,
этого можно избежать небольшим усложнением алгоритма.
Для этого на 3-ем шаге алгоритма число j от 1 до m надо выбирать с
вероятностями p1=r1s,..,pm=rms,
где ri обозначают коэффициенты сжатия отображений Si, а
число s (называемое размерностью подобия) находится из уравнения
r1s+...+rms=1.
Решение этого уравнения можно найти, например, методом Ньютона.
Данный метод используется программой Fractracer и многими др.
|