Макеты страниц
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):
|
Оглавление
|