L-система

Деревья L-системы образуют реалистичные модели природных закономерностей.

L -система или система Линденмайера — это система параллельного переписывания и тип формальной грамматики . L-система состоит из алфавита символов, которые можно использовать для создания строк , набора правил производства , которые расширяют каждый символ до некоторой большей строки символов, начальной строки « аксиомы », с которой можно начать построение, и механизма для перевод сгенерированных строк в геометрические структуры. L-системы были введены и разработаны в 1968 году Аристидом Линденмайером , венгерским биологом -теоретиком и ботаником из Утрехтского университета . Линденмайер использовал L-системы для описания поведения растительных клеток и для моделирования ростовых процессов развития растений . L-системы также использовались для моделирования морфологии различных организмов. и может быть использован для создания самоподобных фракталов .

Происхождение

«Сорняки», созданные с использованием L-системы в 3D.

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

Структура L-системы

Рекурсивная фрактальные природа правил L-системы приводит к самоподобию , и, таким образом, формы легко описать с помощью L-системы. Модели растений и естественные органические формы легко определить, поскольку при увеличении уровня рекурсии форма медленно «растет» и становится более сложной. Системы Линденмайера также популярны в создании искусственной жизни .

Грамматики L-системы очень похожи на грамматику полу-Туэ (см. Иерархию Хомского ). L-системы теперь широко известны как параметрические L-системы, определяемые как кортеж

G = ( V , ω, P ),

где

• V ( алфавит ) — набор символов, содержащий как элементы, которые можно заменить ( переменные ), так и те, которые нельзя заменить («константы» или «терминалы»).
• ω ( старт , аксиома или инициатор ) — строка символов из V, определяющая начальное состояние системы
• P — это набор производственных правил или продукций, определяющих способ замены переменных комбинациями констант и других переменных. Продукция состоит из двух строк: предшественника и преемника . Для любого символа A, который является членом множества V, который не появляется в левой части производства в P, предполагается тождественное производство A → A; эти символы называются константами или терминалами . (См. Закон тождества ).

Правила грамматики L-системы применяются итеративно, начиная с начального состояния. На каждой итерации одновременно применяется как можно больше правил. Тот факт, что каждая итерация использует как можно больше правил, отличает L-систему от формального языка, порожденного формальной грамматикой , которая применяет только одно правило на итерацию. Если бы правила производства применялись только по одному, можно было бы просто генерировать строку на языке, и все такие последовательности приложений создавали бы язык, определенный грамматикой. Однако в некоторых языках есть строки, которые невозможно сгенерировать, если грамматику рассматривать как L-систему, а не как спецификацию языка. Например, предположим, что в грамматике существует правило S→SS. Если производства производятся по одному, то, начиная с S, мы можем получить сначала SS, а затем, снова применив правило, SSS. Однако если все применимые правила применяются на каждом этапе, как в L-системе, то мы не можем получить эту сентенциальную форму. Вместо этого первый шаг даст нам SS, а второй применит правило дважды, давая нам SSSS. Таким образом, набор строк, создаваемых L-системой из данной грамматики, является подмножеством формального языка, определенного грамматикой, и если мы берем язык как набор строк, это означает, что данный L- система фактически является подмножеством формального языка, определенного грамматикой L-системы.

L-система является контекстно-свободной , если каждое продукционное правило относится только к отдельному символу, а не к его соседям. Таким образом, контекстно-свободные L-системы определяются контекстно-свободной грамматикой . Если правило зависит не только от одного символа, но и от его соседей, его называют контекстно-зависимой L-системой.

Если для каждого символа существует ровно одна продукция, то L-система называется детерминированной (детерминированная бесконтекстная L-система в народе называется D0L-системой ). Если их несколько и каждый выбирается с определенной вероятностью на каждой итерации, то это стохастическая L-система.

Использование L-систем для генерации графических изображений требует, чтобы символы в модели относились к элементам рисунка на экране компьютера. Например, программа Fractint использует черепаховую графику (аналогичную той, что есть в языке программирования Logo ) для создания экранных изображений. Он интерпретирует каждую константу в модели L-системы как команду черепахи.

Примеры L-систем

Пример 1: водоросли

Оригинальная L-система Линденмайера для моделирования роста водорослей.

переменные : AB

константы : нет

аксиома : А

правила : (А → AB), (B → A)

который производит:

п = 0: А

п = 1: АБ

п = 2: АБА

n = 3: АБАБ

n = 4: КРЫЛЬЯ

n = 5: ДВОЙНОЙ РАЗМЕР

n = 6: БОЛИ

п = 7

Пример 1: водоросли, объяснение

n=0:               A             start (axiom/initiator)
                  / \
n=1:             A   B           the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
                /|     \
n=2:           A B      A        former string AB with all rules applied, A spawned into AB again, former B turned into A
             / | |       | \
n=3:         A B A       A B     note all A's producing a copy of themselves in the first place, then a B, which turns ...
           / | | | \     | \ \
n=4:       A B A A B     A B A   ... into an A one generation later, starting to spawn/repeat/recurse then

Результатом является последовательность слов Фибоначчи . Если мы посчитаем длину каждой строки, мы получим знаменитую последовательность чисел Фибоначчи (пропуская первую единицу из-за нашего выбора аксиомы):

1 2 3 5 8 13 21 34 55 89 ...

Если мы не хотим пропускать первую единицу, мы можем использовать B. аксиому Это поместит узел B перед самым верхним узлом ( A ) графа выше.

Для каждой строки, если мы отсчитываем k -ю позицию от левого конца строки, значение определяется тем, попадает ли кратное золотому сечению в интервал $(k-1,k)$. Соотношение А и Б также приближается к золотой середине.

Этот пример дает тот же результат (с точки зрения длины каждой строки, а не последовательности A и B ), если правило ( A → AB ) заменяется на ( A → BA ), за исключением того, что строки зеркально отражены.

Эта последовательность является локально катенативной последовательностью, поскольку $G(n)=G(n-1)G(n-2)$, где $G(n)$ это n -е поколение.

Пример 2: фрактальное (бинарное) дерево

• переменные : 0, 1
• константы : "[", "]"
• аксиома : 0
• правила : (1 → 11), (0 → 1[0]0)

Форма создается путем рекурсивной подачи аксиомы через правила производства. Каждый символ входной строки проверяется по списку правил, чтобы определить, каким символом или строкой его заменить в выходной строке. В этом примере «1» во входной строке становится «11» в выходной строке, а «[» остается прежним. Применяя это к аксиоме «0», мы получаем:

аксиома:	0
1-я рекурсия:	1[0]0
2-я рекурсия:	11[1[0]0]1[0]0
3-я рекурсия:	1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
...

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

• 0: нарисовать отрезок линии , заканчивающийся листом
• 1: нарисовать отрезок линии
• [: положение и угол нажатия, поворот налево на 45 градусов
• ]: поп-позиция и угол, поворот направо на 45 градусов.

Толчок и поп относятся к стеку LIFO (более техническая грамматика будет иметь отдельные символы для «положения нажатия» и «поворота налево»). Когда интерпретация черепахи встречает «[», текущая позиция и угол сохраняются, а затем восстанавливаются, когда интерпретация встречает «]». Если было «загружено» несколько значений, то «pop» восстанавливает самые последние сохраненные значения. Применяя перечисленные выше графические правила к предыдущей рекурсии, мы получаем:

• 
  Аксиома
• 
  Первая рекурсия
• 
  Вторая рекурсия
• 
  Третья рекурсия
• 
  Четвертая рекурсия
• 
  Седьмая рекурсия, уменьшенная в десять раз

Пример 3: множество Кантора

переменные : AB

константы : нет

start : A {начальная строка символов}

правила : (А → ABA), (B → BBB)

Пусть А означает «движение вперед», а Б означает «движение вперед».

получается знаменитый фрактальный набор Кантора на реальной прямой R. В результате

Пример 4: кривая Коха

Вариант кривой Коха , в котором используются только прямые углы.

переменные : F

константы : + −

начало : Ф

правила : (F → F+F−F−F+F)

Здесь F означает «натянуть вперед», + означает «повернуть налево на 90°», а – означает «повернуть направо на 90°» (см. рисунок черепахи ).

п = 0:

Ф

п = 1:

Ф+Ф−Ф−Ф+Ф

п = 2:

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

п = 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+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

Пример 5: Треугольник Серпинского

Треугольник Серпинского, нарисованный с использованием L-системы.

переменные : FG

константы : + −

начало : F-G-G

правила : (F → F−G+F+G−F), (G → GG)

угол : 120°

Здесь F и G означают «движение вперед», + означает «поворот налево на угол», а – означает «поворот направо на угол».

• 
  п = 2
• 
  п = 4
• 
  п = 6

Также возможно аппроксимировать треугольник Серпинского, используя L-систему кривой со стрелкой Серпинского .

переменные : AB

константы : + −

начало : А

правила : (A → B−A−B), (B → A+B+A)

угол : 60°

Здесь A и B означают «движение вперед», + означает «поворот налево на угол», а – означает «поворот направо на угол» (см. рисунок черепахи ).

Эволюция для n = 2, n = 4, n = 6, n = 8

Пример 6: кривая дракона

, Кривая дракона нарисованная с использованием L-системы.

переменные : FG

константы : + −

начало : Ф

правила : (F → F+G), (G → FG)

угол : 90°

Здесь F и G означают «движение вперед», + означает «поворот налево на угол», а – означает «поворот направо на угол».

Кривая Дракона для n = 10

Пример 7: фрактальный завод

См. Также: Папоротник Барнсли.

переменные : XF

константы : + − [ ]

начало : Х

правила : (X → F+[[X]-X]-F[-FX]+X), (F → FF)

угол : 25°

Сначала вам нужно инициализировать пустой стек. Это соответствует методу LIFO (последний пришел, первый ушел) для добавления и удаления элементов. Здесь F означает «выдвижение вперед», − означает «поворот направо на 25°», а + означает «поворот налево на 25°». X не соответствует никакому действию рисования и используется для управления развитием кривой. Квадратная скобка «[» соответствует сохранению текущих значений положения и угла, поэтому вы помещаете положение и угол на вершину стека, когда встречается токен «]», извлекаете стек и сбрасываете положение и угол. Каждый «[» предшествует каждому токену «]».

Фрактальный завод для n = 6

Вариации

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

Стохастические грамматики

Грамматическая модель, которую мы обсуждали до сих пор, была детерминистической, то есть для любого символа в алфавите грамматики существовало ровно одно правило производства, которое всегда выбиралось и всегда выполняло одно и то же преобразование. Одной из альтернатив является указание более одного правила производства для символа, определяющего вероятность появления каждого из них. Например, в грамматике примера 2 мы могли бы изменить правило перезаписи «0» на:

0 → 1[0]0

вероятностному правилу:

0 (0.5) → 1[0]0

0 (0.5) → 0

При таком производстве всякий раз, когда во время перезаписи строки встречается «0», с вероятностью 50% он будет вести себя так, как описано ранее, и с вероятностью 50% он не изменится во время производства. Когда стохастическая грамматика используется в эволюционном контексте, желательно включить случайное в генотип семя , чтобы стохастические свойства изображения оставались постоянными между поколениями.

Контекстно-зависимые грамматики

Контекстно-зависимое производственное правило рассматривает не только изменяемый символ, но и символы в строке, появляющиеся до и после него. Например, производственное правило:

б < а > с → аа

преобразует «a» в «aa», но только если «a» находится между «b» и «c» во входной строке:

…назад…

Как и в случае со стохастическими постановками, существует множество постановок для обработки символов в разных контекстах. Если для данного контекста не может быть найдено правило производства, предполагается производство идентичности, и символ не изменяется при преобразовании. Если контекстно-зависимая и бесконтекстная продукция существуют в рамках одной и той же грамматики, предполагается, что контекстно-зависимая продукция имеет приоритет, когда она применима.

Параметрические грамматики

В параметрической грамматике с каждым символом алфавита связан список параметров. Символ, связанный со списком его параметров, называется модулем, а строка в параметрической грамматике представляет собой серию модулей. Пример строки может быть:

а(0,1)[б(0,0)]а(1,2)

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

a(x,y) : x == 0 → a(1, y+1)b(2,3)

Модуль a(x,y) претерпевает преобразование по этому продукционному правилу, если выполняется условие x=0. Например, a(0,2) подвергнется трансформации, а a(1,2) — нет.

В части преобразования производственного правила можно повлиять как на параметры, так и на целые модули. В приведенном выше примере к строке добавляется модуль b(x,y) с начальными параметрами (2,3). Также преобразуются параметры уже существующего модуля. Согласно вышеуказанному правилу производства,

а(0,2)

становится

а(1,3)б(2,3)

поскольку параметр «x» a(x,y) явно преобразуется в «1», а параметр «y» a увеличивается на единицу.

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

Двунаправленные грамматики

Двунаправленная модель явно отделяет систему символьного переписывания от назначения формы. Например, процесс перезаписи строк в примере 2 (фрактальное дерево) не зависит от того, как графические операции назначаются символам. Другими словами, к данной системе переписывания применимо бесконечное количество методов отрисовки.

Двунаправленная модель состоит из 1) прямого процесса построения дерева вывода с продукционными правилами и 2) обратного процесса поэтапной реализации дерева с формами (от листьев к корню). Каждый шаг обратного вывода включает в себя важные геометрическо-топологические рассуждения. В этой двунаправленной структуре ограничения и цели проекта закодированы в переводе грамматической формы. В приложениях архитектурного проектирования двунаправленная грамматика обеспечивает постоянную внутреннюю связь и богатую пространственную иерархию.

Открытые проблемы

Существует много открытых проблем, связанных с изучением L-систем. Например:

• Характеристика всех детерминированных контекстно-свободных L-систем, которые являются локально цепляющими . (Полное решение известно только в случае, когда имеется только две переменные).
• Учитывая структуру, найдите L-систему, которая может создать эту структуру.

Виды L-систем

L-системы на действительной прямой R :

• Система Пруэ-Тюэ-Морса

Известные L-системы на плоскости R ² являются:

• кривые, заполняющие пространство ( кривая Гильберта , кривые Пеано , церковь Деккинга, коламы ),
• срединные кривые заполнения пространства ( кривая Леви C , кривая дракона Хартера-Хайуэя , тердрагон Дэвиса-Кнута),
• мозаика ( плитка сфинкса , плитка Пенроуза )

См. также

• Цифровой морфогенез
• фрактал
• Итерированная система функций
• Кривая Гильберта
• Система реакции-диффузии - тип математической модели, которая обеспечивает моделирование диффузии химических реагентов (в том числе реалистичную).
• Стохастическая контекстно-свободная грамматика
• Скоростное дерево
• Алгоритмическая красота растений

Книги

• Пшемыслав Прусинкевич , Аристид Линденмайер – Алгоритмическая красота растений PDF-версия доступна здесь бесплатно. Архивировано 10 апреля 2021 г. на Wayback Machine.
• Гжегож Розенберг , Арто Саломаа – Системы Линденмайера: влияние на теоретическую информатику, компьютерную графику и биологию развития ISBN   978-3-540-55320-5
• Д.С. Эберт, Ф.К. Масгрейв и др. – Текстурирование и моделирование: процедурный подход , ISBN   0-12-228730-4
• Берри, Джейн, Берри Марк (2010). Новая математика архитектуры, Нью-Йорк: Темза и Гудзон.
• Аристид Линденмайер, « Математические модели клеточного взаимодействия в развитии ». Дж. Теория. Биология, 18:280–315, 1968.

Внешние ссылки

• Алгоритмическая ботаника в Университете Калгари
• L-Systems : удобная страница для создания фракталов и растений из L-Systems.
• Ветвление: Дерево L-системы и Java-апплет его исходный код ( с открытым исходным кодом ) для моделирования роста ботанического дерева с использованием L-системы.
• Fractint L-система Истинные фракталы
• OpenAlea. Архивировано 17 октября 2005 г. на Wayback Machine : программная среда с открытым исходным кодом для моделирования предприятий. который содержит L-Py , реализацию систем Lindenmayer с открытым исходным кодом на Python.
• PowerPlant - программное обеспечение для ландшафтного моделирования с открытым исходным кодом.
• Фрактинта Домашняя страница
• Простой генератор L-систем (Windows)
• Lyndyhop: еще один простой генератор L-систем (Windows и Mac)
• Эволюционный генератор L-систем (любой*)
• Реализация L-систем в Racket
• Гриффитс, Дэйв (2004). «Lсистемнаякомпозиция» . Пауфал . Архивировано из оригинала 6 ноября 2004 г. Проверено 19 апреля 2012 г. Страница об использовании L-систем и генетических алгоритмов для создания музыки.
• eXtended L-Systems (XL), грамматики реляционного роста и программная платформа с открытым исходным кодом GroIMP.
• JAVA-апплет со множеством фрактальных фигур, созданных L-системами. Архивировано 6 августа 2016 г. в Wayback Machine.
• My Graphics – приложение для iPhone/iPad, которое генерирует несколько графических шаблонов L-системы.
• Манусакис, Стелиос (июнь 2006 г.). Музыкальные L-системы (PDF) (Магистерская диссертация). Королевская консерватория Гааги . Архивировано (PDF) из оригинала 23 июля 2011 г. Проверено 19 июля 2022 г.
• Онлайн-эксперименты с L-Systems с использованием JSXGraph (JavaScript)
• Flea Реализация LSYSTEM на Ruby, использующая предметно-ориентированный язык вместо кратких команд генератора.
• Мощность Линденмайера. Растение и фрактальный генератор с использованием L-систем (JavaScript)
• Розенберг, Г.; Саломаа, А. (2001) [1994], «L-системы» , Энциклопедия математики , EMS Press
• L-Parser Лоренса Лапре, заархивированный 13 сентября 2013 г. в Wayback Machine.
• HTML5 L-Systems – экспериментируйте онлайн
• Программа векторной графики Inkscape оснащена анализатором L-системы.
• Лю, Чэн-Юань; Ву, Тай-Хэй; Ли, Цзя-Ин (2009). «Моделирование сложности в музыкальном ритме». Сложность . 15 (4): 19–30. дои : 10.1002/cplx.20291 . S2CID   18737938 .
• Реализация парсера L-системы и простой черепашьей графики на языке программирования Icon.
• Генератор системы Линденмейера Нолана Кэрролла
• Bloogen: L-системы с генетическим уклоном