Kranover R M - Fraktaly i khaos v din sist

2.2 Самоподобие • 2 1

имеет площадь меры нуль. Это выделяет множество S в разряд «совершенного», в том смысле, что оно разбивает свое дополнение на бесконечное число треугольных областей, обладая при этом нулевой толщиной.

Губка Менгера. Существуют и трехмерные аналоги ковров. Следуя Мандельброту, мы называем такие множества губками. Губка, изображенная на рис. 2.6, называется губкой Менгера, по имени Карла Менгера. Это самоподобный фрактал с N = 20 и г = 1/3. Его размерность равна:

d = log(20)/ log(3) * 2,7268.

Такая губка имеет объем меры нуль. Мы оставляем детали построения и анализа для рассмотрения читателю.

Упражнения 2.1.

1.Определить дробную размерность (размерность подобия) фракталов, которые строятся, как указано на рис. 2.7.

2.Определить дробную размерность (размерность подобия) фракталов, которые строятся, как указано на рис. 2.8.

3.Построить фрактал, отличный от фрактала на рис. 2.8(а), но той же размерности.

4.Показать, что сумма площадей треугольников, выкинутых при построении ковра Серпинского, равняется площади исходного треугольника. Указание: воспользоваться соотношением:

1/(1 -х) = 1 + х + х2-\ , для |х| < 1.

5.Рассмотрим фрактал, который строится, как указано на рис. 2.9. Этот фрактал иногда называют пылью Серпинского. Записать бесконечный ряд для суммы площадей частей, которые были удалены при построении. Найти сумму этого ряда.

6.(Компьютерный эксперимент.) Исследовать, какая связь существует между треугольником Паскаля (состоящим из биномиальных коэффициентов) и ковром Серпинского(см. [36]).

22 • Глава 2 / Классические фракталы

Рис. 2.6. Построение губки Менгера

1 в—-HI

о 1 ,.

1

1 1

11 в 1

(в) (г)

Рис. 2.7. Построения к упр. 1

2.2 L-системы • 23

(а)

(б)

Рис. 2.8. Построения к упр. 2

Рис. 2.9. Построения к упр. 5

2.2. L-системы

Понятие L-систем, тесно связанное с самоподобными фракталами, появилось только в 1968 году благодаря Аристриду Линденмайеру. Изначально L-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и ковер Серпинского. Некоторые другие классические построения, например кривые Пеано (работы Пеано, Гильберта, Серпинского), также укладываются в эту схему. И конечно, L-системы открывают путь к бесконечному разнообразию новых фракталов, что и послужило причиной их широкого применения в компьютерной графике для построения фрактальных деревьев и растений. Наше изложение L-систем следует

24• Глава 2 / Классические фракталы

восновном работам Прузинкевича и Ханана [39] и ограничивается случаем детерминированных L-систем и графикой на плоскости.

Для графической реализации L-систем в качестве подсистемы вывода используется так называемая тертил-графика (turtle — черепаха). При этом точка (черепашка) движется по экрану дискретными шагами, как правило, прочерчивая свой след, но при необходимости может перемещаться без рисования. В нашем распоряжении имеются три параметра (ж,у, а), где (х, у) — координаты черепашки, а — направление, в котором она смотрит. Черепашка обучена интерпретировать и выполнять последовательность команд, задаваемых кодовым словом, буквы которого читаются слева направо. Кодовое слово представляет собой результат работы L-системы и может включать следующие буквы:

+увеличить угол а на величину в

—уменьшить угол а на величину в

Размер шага и величина приращения по углу в задаются заранее и остаются неизменными для всех перемещений черепашки. Если начальное направление движения а (угол, отсчитываемый от положительного направления оси X) не указано, то полагаем а равным нулю.

Несколько примеров иллюстрируют применение команд ветвления (обозначаются ], [) и вспомогательных переменных (обозначаются X, Y и т. д.). Команды ветвления используются для построения деревьев и растений, а вспомогательные переменные заметно облегчают построение некоторых L-систем.

Формально, детерминированная L-система состоит из алфавита, слова инициализации, называемого аксиомой или инициатором, и набора порождающих правил, указывающих, как следует преобразовывать слово при переходе от уровня к уровню (от итерации к итерации). К примеру, можно заменять букву F при помощи порождающего правила newf = F—F+-f-F—F, что соответствует L-системе для снежинки Коха, рассматриваемой ниже. Символы +, —, ], [ не обновляются, а просто остаются на тех местах, где они встретились. Обновление букв в данном слове предполагается одновременным,

2.2 L-системы • 25

то есть все буквы слова одного уровня обновляются раньше любой буквы следующего уровня.

L-система, соответствующая снежинке Коха (рис. 2.2), задается следующим образом:

0 = тг/3

Аксиома: F++F++F

Порождающее правило: newf = F—F++F—F

Графическое представление аксиомы F++F++F — равносторонний треугольник. Черепашка делает один шагвперед, затем угол а увеличивается на 2тг/3 и черепашка делает ещеодин шаг вперед, угол а снова увеличивается на 2тг/3 и черепашка делает еще шаг.

На первом шаге каждая буква F в слове-инициаторе F++F++F заменяется на F-F++F—F:

(F - F++F - F)++(F - F++F - F)++(F - F++F - F) .

Убирая скобки, получаем:

F-F++F-F++F-F++F-F++F-F++F-F. Повторяя этот процесс, на втором шаге получим:

F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++ F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++ F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F

и т.д.

Псевдокод для итерирования порождающих правил в этом простейшем случае, когда используются только правила вида F =newf, Ъ = newb, выглядит следующим образом:

Алгоритм 2.2.1. (L-СИСТЕМЫ)

Назначение: реализует правила F = newf, b = newb.

Вход:

axiom (слово инициализации) newf (порождающее правило) newb (порождающее правило) level (число итераций)

Выход:

word (слово-результат)

26 • Глава 2 / Классические фракталы

Инициализация: W = axiom

n = length(W)

Т = { } (пустое множество)

Шаги:

level = level —1 end while

word = W

Замечание: W(j) — j-ая буква в слове W, {T +} — строка Т, к которой присоединен знак +.

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

График на рис. 2.10 не имеет разрывов, так как черепашка движется единичными шагами и каждый раз прорисовывает свой след. Разрывные графики можно получать, применяя в L-системе команду «Ь», то есть команду «переместиться на один шаг вперед без рисования». Примерами могут служить изображения мозаики на рис. 2.11 и цепочки на рис. 2.12.

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

2.2 L-системы • 27

Рис. 2.10. Остров после 2-х итераций

Например, для того чтобы построить фрактал под названием «дракон Хартера-Хайтвея» [9, 31], необходимо иметь возможность менять направление чтения порождающего правила, изображенного на рис. 2.13. В качестве инициатора, или аксиомы, используется кривая слева. Порождающее правило в данном случае заключается в том, чтобы нарисовать инициатор сначала в прямом, а затем в обратном направлении. Подобная схема не вписывается в рамки L-систем, использующих только одно порождающее правило. Эту проблему можно решить, введя две различных команды для передвижения вперед, например X и Y. Будем считать, что черепашка интерпретирует X и Y одинаково, то есть как один шаг вперед.

С помощью этих двух букв порождающее правило для дракона можно записать следующим образом:

axiom = X, newx = X+Y+, newy = —X-Y.

Однако, нам не хотелось бы отказываться от первоначального подхода, при котором имеется только одна буква F, интерпретируе-

28 • Глава 2 / Классические фракталы

Рис. 2.11. Мозаика после 3-х итераций (Патрик Хагерти)

мая как один шаг вперед. Чтобы вернуться в рамки этого подхода, будем считать буквы X и Y вспомогательными переменными, игнорируемыми черепашкой, и заменим их в порождающем правиле на FX и FY соответственно. Получим:

axiom = FX, FX = FX+YF+, YF = -FX-YF.

Далее замечаем, что того же результата можно добиться при помощи следующих порождающих правил:

axiom = FX, newf = F,

newx = X+YF+, newy = -FX-Y.

30 Глава 2 j Классические фракталы

Рис. 2.14. Дракон Хартера-Хайтвея после 12-и итераций

Ниже приведены несколько шагов построения дракона с использованием этих порождающих правил:

1-ый шаг: FX+YF+

2-ый шаг:FX+YF++-FX-YF+

3-ый шаг: FX+YF++-FX-YF++-FX+YF+—FX-YF+

4-ый шаг: FX+YF++-FX-YF++-FX+YF+—FX-YF++ -FX+YF++-FX-YF+—FX+YF+—FX-YF+

На рис. 2.14 изображен дракон после 12 итераций. Заметьте, что дракон состоит из нескольких похожих частей.

В заключение остановимся на операции ветвления. Когда мы встречаем символ [ (открыть ветвь), мы запоминаем положение и направление черепашки, то есть переменные (х,у, а), и возвращаемся к этим установкам позднее. Для хранения триплетов (х, у, а)