L - системы. Эволюция объекта. Порождение и визуализация строк.
L-системы изначально были предназначены для моделирования растений. Представьте себе, что растения состоит из элементов трех видов: ствола (I), левый лист (L), правый лист (R), тогда простейшую конфигурацию можно записать как ILR. Последовательность ILRможно трактовать как ствол и пара листьев.
Системы Линденмайераповзоляют задавать правила развития в конфигурации в виде:
Предок ->потомок
Используя эту запись можно «вырастить» куст любой высоты. Добавим к описанию куста новый элемент – корень (А) и укажем способ его развития:
A->AILR
Изначально куст будет состоять всего лишь из одного корня. После трехкратного применения правила роста можно получить куст, состоящий из трех сегментов:
A-> AILR -> AILRILR -> AILRILRILR
Порождение и визуализация строк.
L-системы представляют собой механизм генерации строк на основе начальной строки (аксиомой) и некоторой разновидности формальной грамматики. А также полученная в итоге строка должна каким-то образом интерпретироваться подсистемой визуализации, чтобы на экране появился осмысленный рисунок
Порождение строк:
Механизм вывода строк ничего не знает о графическом выводе; поэтому мы всего лишь подставляем на место отдельных символов те или иные строки в соответствии с правилами грамматики. В отличие от обычноый грамматики, где на каждом шаге применялось лишь одно правило, в L-системах одновременно происходит замена всех символов, для которых существуют правила развития.
Процесс замены можно продолжать бесконечно. В реальности интересно бывает либо проследить эволюцию аксиомы на протяжении некоторого конечного числа шагов.
Пример:
Визуализация строк:
Здесь не существует единого стандарта. Разные визуализаторы используют разные наборы команд. Однако существуют общие принципы работы подсистемы графического вывода.
Базовых принципа всего два:
· Визуализатор функционирует по принципу черепашьей графики
· Все нераспознанные команды игнорируются
Любая система визуализации должна представлять следующие команды:
Значения distanceи angleобычно задаются где-то в настройках визуализатора.
Пример:
Система, состоящая из аксиомы gи правила вывода g->g[+g][-g] имеющая значения distance = 15, angle = 20 (находиться в середине экрана и смотрим вверх)
На нулевом шаге: команда gозначает рисование единственного отрезка.
На первом шаге: самый левый символ g, как и раньше рисует отрезок, затем начинается ветвь: создается новая черепашка, затем она поворачивается на angleградусов направо (символ +) и рисует отрезок (команда g). После этого ветвь заканчивается, и управление передается исходной черепашке. Затем аналогичным образом рисуется левая ветвь.
На второй шаге: сначал происходит рисование уже известного фрагмента g[+g][-g], после чего рисуется более сложная ветвистая структура.
Итог:
L - системы. Фрактальные узоры. Примеры. Визуализация в JFLAP.
По определению Мандельброта, фрактал – структура, состоящая из частей, которые в каком-то смысле подобны целому.
В математике под фракталами понимают множества точек в евклидовом пространстве, имеющие дробную метрическую размерность (в смысле Минковского или Хаусдорфа), либо метрическую размерность, отличную от топологической, поэтому их следует отличать от прочих геометрических фигур, ограниченных конечным числом звеньев.
Примеры:
Кривая Коха
Кривая Коха состоит из некоторого числа отрезков одинаковой длины. На очередном шаге каждый такой отрезок за меняется фигурой из четырех равных отрезков:
Определение кривой Коха с помощью грамматики: g ->g + g - - g + g.
Кривая Коха тертьего порядка:
Треугольник Серпинского:
Фигура получается следующим образом: треугольник нулевого порядка представляет собой самый обыкновенный раносторонний треугольник. Для получения треугольника первого порядка треугольник нулевого порядка разделяется на четыре равные части:
Центральная часть фигуры «извлекается». На следующих шагах разделение будет продолжено только для неизвлеченных участков. Разделяя оставшиеся после предыдущего шага треугольники, можно получить треугольник Серпинского очередного порядка.
Грамматика преобразований:
Аксиома: gXg - - gg - - gg(Если считать что угол каждого поворота равен 60 градуса).
Правило: g ->gg
Правило: X -> - - gXg + + gXg + + gXg - -
L - системы.
L-системой (точнее, её простейшей разновидностью, детерминированной контекстонезависимой L-системой) называют набор, состоящий из алфавита, аксиомы, и множества правил.
Понятие L-систем, тесно связанное с самоподобными фракталами, появилось только в 1968 году благодаря АристридуЛинденмайеру. Изначально L-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и ковер Серпинского. Некоторые другие классические построения, например кривые Пеано (работы Пеано, Гильберта, Серпинского), также укладываются в эту схему. И конечно, L-системы открывают путь к бесконечному разнообразию новых фракталов, что и послужило причиной их широкого применения в компьютерной графике для построения фрактальных деревьев и растений. Наше изложение L-систем следует в основном работам Прузинкевича и Ханана и ограничивается случаем детерминированных -систем и графикой на плоскости.