2. 4. Построение фракталов с помощью систем итерированных функций
2. 4.1. Построение треугольника Серпинского с помощью системы итерированных функций
Рассмотрим построение треугольника Серпинского с помощью системы итерированный функций.
1 способ. Детерминированный алгоритм.
Для построения будем использовать аффинные преобразования  (см. рис. 7). Если  - замкнутое множество в виде треугольника с вершинами  , то образы  – три меньшие треугольные области, изображенные на рисунке 7 в центре.
Рисунок Построение треугольника Серпинского с помощью СИФ16
В детерминированном алгоритме рассмотрим следующую последовательность множеств
   
Ясно, что выполняя подобный алгоритм, мы в точности воспроизводим алгоритм построения треугольника Серпинского. Поэтому после бесконечного числа шагов мы придем в конце концов к множеству точек, образующих этот фрактал.
Важно заметить, что для получения точно такого же предельного результата мы могли бы стартовать с любой фигуры, необязательно имеющей форму равностороннего треугольника. Это, например, мог быть круг или квадрат или любая другая (даже несвязная) фигура, произвольным образом расположенная на плоскости.
На рис. 8 показан результат построения треугольника Серпинского после 5 итераций. В качестве множества  взят квадрат.
Рисунок Треугольник Серпинского: детерминированный алгоритм17
2 способ. Рандомизированный алгоритм.
В рандомизированном алгоритме в качестве начального множества выберем одну точку.
  
На каждом шаге вместо того, чтобы применять сразу три преобразования, мы применяем только одно, выбранное случайным образом. На каждом шаге мы получаем ровно одну точку. Начиная с некоторого шага, точки начинают заполнять треугольник Серпинского.
Рисунок Треугольник Серпинского: рандомизированный алгоритм. 10000 точек18
2. 4.2. Построение папоротника Барнсли с помощью системы итерированных функций
Папоротник Барнсли - фрактал, названный в честь Майкла Барнсли, британского математика, который первым описал его в своей книге «Фракталы повсюду».
Построение.
Папоротник Барнсли строится при помощи 4-х афинных преобразований вида:
Барнсли представил свой IFS-код в виде матрицы значений:
Таблица Матрица значений для построения папоротника Барнсли
w
|
a
|
b
|
c
|
d
|
e
|
f
|
p
|
ƒ1
|
0
|
0
|
0
|
0.16
|
0
|
0
|
0.01
|
ƒ2
|
0.85
|
0.04
|
-0.04
|
0.85
|
0
|
1.6
|
0.85
|
ƒ3
|
0.2
|
-0.26
|
0.23
|
0.22
|
0
|
1.6
|
0.07
|
ƒ4
|
-0.15
|
0.28
|
0.26
|
0.24
|
0
|
0.44
|
0.07
|
где столбцы a-f - коэффициенты уравнения, а p - коэффициент вероятности,  и  - координаты.19
Данная таблица отвечает следующим преобразованиям:
Папоротник Барнсли теоретически может быть построен вручную. Т.е. вы берете ручку, лист в бумаги в мелкую клетку и следуете матрице коэффициентов. Однако, количество необходимый итераций исчисляется десятками тысяч, что делает использование компьютера, мягко говоря, желательным.
Первая точка находится в начале координат  , а затем новые точки итеративно вычисляются путем случайного применения одного из следующих четырех преобразований координат:
Данное преобразование выбирается в 1% случаев и указывает на точку у основания «стебля» (см. рис. 10) Эта часть рисунка в результате итерационных преобразований завершается первой.
Преобразование (2) используется в 85% случаев и указывает на любую точку листа, попадающую в красный треугольник (см. рис. 10)
Выбирается в 7% случаев - попадания точки в синий треугольник (см. рис. 10) и симметричного ему относительно главного стебля треугольника.
В оставшихся 7% случаев используется преобразование (4) - для симметричных преобразованию (3) относительно стеблей 2-го порядка позиций.
На рис. 10 представлен пошаговый процесс генерации папоротника Барнсли с помощью рандомизированного алгоритма.
Рисунок Папоротник Барнсли: пошаговое генерирование20
Варьируя значения констант в таблице 1 можно получать множество различных моделей, отличных от папоротника Барнсли (см. рис. 11)
Рисунок Телиптерисовый папоротник
2. 4.3. Построение дракона Хартера-Хэйтуэя с помощью системы итерированных функций
Считается, что такое название фрактал получил за сходство с традиционными китайскими драконами. Каждая ломаная-дракон состоит из отрезков. Ломаная с номером n будет состоять из 2n отрезков. Длина каждого равна 1/2n-й части длины исходного отрезка. Если их занумеровать числами 0, 1, 2, ... и идти по ломаной, то после каждого отрезка нужно поворачивать. Направление поворота определяется номером k текущего отрезка:
повернуть направо, если k дает остаток 1 от деления на 4;
повернуть налево, если k дает остаток 3 от деления на 4;
поступить также, как после отрезка с номером k/2 , если k четно.
Эти правила позволяют запрограммировать процедуру рисования драконов.21
Построим систему итерированных функций для дракона Хартера-Хейтуэя. Для этого расположим первое поколение этого фрактала на сетке координат  . Обозначим точки получившейся ломаной  . По правилам построения у этого фрактала две части, подобные целому - на рис. 12 это ломаные  . 22
Рисунок Заготовка для построения IFS дракона Хартера-Хейтуэя
Зная координаты концов этих отрезков, можно вычислить коэффициенты двух аффинных преобразований, переводящих ломаную  :
 
и 
Задавшись начальной стартовой точкой (например  ) и итерационно действуя на нее этой IFS, после десятой итерации на экране получим фрактальную структуру, изображенную на рис.13, которая представляет собой дракон Хартера-Хейтуэя. Его кодом (сжатым описанием) является набор коэффициентов двух аффинных преобразований.
Рисунок Дракон Хартера-Хэйтуэя: 10 итераций23
2. 4.4. Построение кривой Коха с помощью системы итерированных функций
Аналогично можно построить систему итерированных функций для кривой Коха. Нетрудно видеть, что эта кривая имеет четыре части, подобные целой кривой (см. рис 2, глава 1). Для нахождения системы итерированных функций опять расположим первое поколение этого фрактала на сетке  (Рис.14).
Рисунок Заготовка для построения IFS кpивой Коха24
Для ее построения требуется набор аффинных преобразований, состоящий из четырех преобразований:
      
Результат применения этого аффинного коллажа после десятой итерации можно увидеть на рис.15.
Рисунок Кpивая Коха, постpоенная с помощью IFS25
|
