2.2. L-системы

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

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

F переместиться вперед на один шаг, прорисовывая след,

b переместиться вперед на один шаг, не прорисовывая след.

[ открыть ветвь (подробнее см. ниже)

] закрыть ветвь (подробнее см. ниже)

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

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

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

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

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

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

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

Аксиома:

Порождающее правило:

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

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

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

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

и т. д.

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

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

Назначение: реализует правила .

Вход:

)

Выход:

Инициализация:

Шаги:

Замечание: буква в слове — строка Т, к которой присоединен знак +.

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

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

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

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

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

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

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

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

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

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

Рис. 2.12. Цепочка после 3-х итераций (Ян-Си Ло)

Рис. 2.13. Инициатор и правило для дракона Хартера-Хайтвея

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

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

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

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

Рис. 2.15. Сорняк после 4-х итераций

Для хранения триплетов используется стек

причем новые данные записываются в конец стека. Когда ветвь закрывается, переменным присваиваются значения, считанные из конца стека. Затем эти значения из стека удаляются.

Таким образом, ветвление задается двумя символами:

[ Открыть ветвь. Сохранить в конце стека.

] Закрыть ветвь. Присвоить переменным значения, считанные из конца стека, после чего удалить их из стека.

На рис. 2.15 и 2.16 изображены фракталы, построенные с помощью операции ветвления.

Ниже приведен алгоритм, который позволяет получать графическое представление слова при помощи тертл-графики.

Алгоритм 2.2.2. (ТЕРТЛ-ГРАФИКА)

Назначение: реализует тертл-графику для кодового слова, состоящего из букв [, ], + и -.

Вход:

Выход:

Графическое представление word.

Инициализация:

графический режим (подробнее см. ниже)

Шаги:

провести линию из точки в точку ,

Рис. 2.16. Куст после 4-х итераций

Можно написать специальную программу для определения размеров графического окна. Для этого достаточно выполнить в точности те же шаги, что и в алгоритме 2.2.2, но вместо вывода на экран надо отслеживать наименьшее и наибольшее значения х и у. Вначале положим эти значения равными нулю:

Каждый раз, когда появляется новая точка (х,у), размеры окна обновляюся:

Рис. 2.17. Снежинка после 3-х итераций (Джонг By Ким)

Значения , полученные по окончании работы алгоритма, используются для инициализации окна вывода тертл-графики.

Порождающие правила для L-систем. Порождающие правила для L-систем перечислены в алфавитном порядке.

Дракон Хартера-Хайтвея (рис. 2.14):

Рис. 2.18. Цветок после 3-х итераций (Брандон Нельсон)

Ковер Серпинского (рис. 2.4):

Кривая Гильберта, заполняющая плоскость (рис. 2.24):

Кривая Госпера, заполняющая плоскость (рис. 2.26):

Кривая Пеано, заполняющая плоскость (рис. 2.22, 2.23):

Кривая Серпинского, заполняющая плоскость (рис. 2.25):

Куст (рис. 2.16):

Мозаика (рис. 2.11):

Остров (рис. 2.10):

Снежинка (рис. 2.17):

Снежинка Коха (рис. 2.2):

Сорняк (рис. 2.15):

Рис. 2.19. Порождающее правило к упр. 2

Цветок (рис. 2.18):

Цепочка (рис. 2.12):