Суперфрактал
Шрифт:
Рассмотрим несколько совершенно разных алгоритмов, которые производят одну и ту же фрактальную форму — «салфетку Серпинского».
Метод вырезания трем
Берем равносторонний треугольник со стороной r. На первом шаге вырезаем в центре него перевернутый вершиной вниз равносторонний треугольник с длиной стороны r1 = r0/2. В результате этого шага у нас получаются три равносторонних треугольника с длинами сторон r1 = r0/2, располагающиеся в вершинах исходного треугольника.
На втором шаге в каждом из трех образовавшихся треугольников вырезаем перевернутые вписанные треугольники с длиной стороны r2 = r1/2 = r0/4. Результат — 9 треугольников с длиной стороны r2 = г/4.
Продолжаем повторять эту операцию, на любом n-м шаге в каждом из имеющихся треугольников вырезая перевернутый треугольник со стороной гn = г0/2n = r02– n.
В результате форма «салфетки Серпинского» постепенно становится все более и более определенной.
Алгебраический алгоритм
Поместим равносторонний треугольник с длиной стороны, равной 1, на комплексную плоскость = х + iу (левый треугольник на рисунке). Пусть у нас имеются три оператора t1, t2, t3, каждый из которых переводит исходный равносторонний треугольник в подобный ему, но в два раза меньшего размера.
Применение операторов t1, t2, t3 приводит к тому, что мы получаем треугольник, подобный исходному, но меньшего размера и строго определенного положения по отношению к исходному треугольнику, как показано на рисунке.
Многократное повторение этих операторов позволяет построить «салфетку Серпинского».
Здесь реализуется кумулятивная фиксация образа, то есть накопительное пошаговое формирование его так, что фрагмент n-го шага накладывается на образ n-1 шага.
Метод FASS– линии
Данный метод позволяет построить фрактал Серпинского при помощи алгоритма построения так называемых FASS-кривых. Название происходит от английского описания подобных кривых: «space-Filling, self-Avoiding, Simple and self-Similar», что означает «кривые, заполняющие собой всю плоскость, без самопересечений, состоящие из простых и самоподобных фрагментов». Пошаговое построение FASS– линии при многократном повторении может произвести фрактал Серпинского.
Конечно, при фиксации образа последующего шага все предыдущие построения «стираются».
Метод L– систем
Метод L– систем был изобретен в 1968 году не математиком, а венгерским биологом Аристидом Линденмайером, разработавшим метод описания сложных природных систем и процессов с помощью простых составляющих и правил их преобразования.
Линденмайер использовал формальную грамматику, опирающуюся на правила генерации преобразования символов. L– система позволяет получить сложную форму при помощи аксиомы и правил преобразования. Результат этого процесса детерминирован, то есть строго и однозначно определен алгоритмом построения. Однако проблемой метода в общем смысле является то, что предсказать конечный результат невозможно до тех пор, пока алгоритм не будет завершен полностью. При этом каждый шаг вызывает удлинение командной строки, а значит, на ее обработку требуется все больше и больше времени, так что даже для современных компьютеров этот процесс достаточно долог, а в далеком 1968 году на решение задачи потребовалась бы почти вечность.
Рассмотрим алгоритм построения «салфетки Серпинско- го» методом L-систем немного подробнее.
Аксиомой этого процесса служит выражение: FXF — — FF — — FF. Имеются также три правила:
Нулевой шаг процесса имеет вид: FXF — — FF — — FF. Уже первый шаг имеет довольно длинную запись:
О длине записи на десятом или двадцатом шаге даже говорить не приходится. Впрочем, для вычислительной машины это не проблема. Заметим, что, в отличие от предыдущего алгоритма, при фиксации следующего шага все предыдущие построения не стираются. Поскольку фрактальные алгоритмы сводятся к повтору установленных правил, общей идеей для их вычислений будет организация цикла, в котором по завершении последней операции программа будет возвращаться к исходной операции. Эта операциональная петля не возвращает нас к начальной точке, но каждый раз переопределяет начальные условия. Начальные условия обновляются на каждом такте цикла построения фрактала, и это всякий раз приводит к новому результату в конце цикла. Промежуточные результаты могут «стираться», но могут и накапливаться. Команда «стирать» или «сохранить» — последняя команда в цикле построения фрактала.
Метод систем итерированных функций Барнсли
Метод систем итерированных функций (IFS — Iterates Function System) был разработан Майклом Барнсли на основе сжимающих аффинных преобразований, которые мы рассмотрим подробно в главе III. Пока иллюстрируем этот метод простым примером.
Дано: равносторонний треугольник с координатами углов А (0,0), В (1,0), С (1/2,31/2/2),Z0и произвольная точка внутри этого треугольника — игральная кость, на гранях которой имеется по две буквы A, В и С.
Шаг 1. Бросаем кость. Вероятность выпадения каждой буквы составляет 2/6 = 1/3.
• Если выпала буква А — строим отрезок z0– А, на середине которого ставим точку z1.
• Если выпала буква В — строим отрезок z0– В, на середине которого ставим точку z1.
• Если выпала буква С — строим отрезок z0 – С, на середине которого ставим точку z1.
Шаг 2. Бросаем кость еще раз.
• Если выпала буква А — строим отрезок z1– А, на середине которого ставим точку z2.
• Если выпала буква В — строим отрезок z1– В, на середине которого ставим точку z2.
• Если выпала буква С — строим отрезок z1– С, на середине которого ставим точку z2.
Повторяя операцию много раз, мы получим точки z3, z4, ..., zn. Особенность каждой из них в том, что точка находится точно на полпути от предыдущей до произвольно выбранной вершины. Теперь, если отбросить достаточно большое количество точек, например, от z0 до z100, то остальные при достаточно большом их количестве образуют структуру «салфетки Серпинского». Чем больше точек, чем больше итераций, тем явственнее является наблюдателю фрактал Серпинского. И это притом, что процесс идет, казалось бы, случайным путем (благодаря игральной кости). «Салфетка Серпинского» представляет собой своего рода аттрактор процесса, то есть фигуру, к которой стремятся все траектории, построенные в этом процессе при достаточно большом количестве итераций. Фиксация образа при этом представляет собой кумулятивный, накопительный процесс.