Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Деревья L-системы образуют реалистичные модели природных узоров

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

Истоки [ править ]

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

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

Структура L-системы [ править ]

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

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

G = ( V , ω, P ),

куда

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

Правила грамматики L-системы применяются итеративно, начиная с начального состояния. Максимальное количество правил применяется одновременно на итерацию. Тот факт, что каждая итерация использует как можно больше правил, отличает L-систему от формального языка, генерируемого формальной грамматикой , которая применяет только одно правило на итерацию. Если бы производственные правила применялись только по одному, можно было бы просто сгенерировать язык, а не L-систему. [ требуется пояснение ] Таким образом, L-системы являются строгими подмножествами языков. [ требуется разъяснение ]

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

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

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

Примеры L-систем [ править ]

Пример 1: водоросли [ править ]

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

переменные  : AB
константы  : нет
аксиома : A
правила : (A → AB), (B → A)

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

п = 0: А
n = 1: AB
n = 2: ABA
n = 3: ABAAB
n = 4: ABAABABA
n = 5: ABAABABAABAAB
n = 6: ABAABABAABAABABAABABA
n = 7: ABAABABAABAABABAABABAABAABABAABAAB

Пример 1: водоросли, объяснение [ править ]

n = 0: начало (аксиома / инициатор) / \n = 1: AB исходный одиночный A, порожденный в AB по правилу (A → AB), правило (B → A) не может быть применено / | \n = 2: ABA бывшая строка AB со всеми примененными правилами, A снова возникла в AB, бывшая B превратилась в A / | | | \n = 3: ABAAB замечает, что все A сначала создают копию самих себя, затем B, что превращается ... / | | | \ | \ \n = 4: ABAABABA ... в A одним поколением позже, начиная с появления / повторения / рекурсии, затем

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

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

Для каждой строки, если мы считаем k-ю позицию от левого конца строки, значение определяется тем, попадает ли кратное золотого сечения в интервал . Отношение A к B аналогично сходится к золотой середине.

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

Эта последовательность является локальной катенативной последовательностью, потому что , где - 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 градусов

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

  • Аксиома

  • Первая рекурсия

  • Вторая рекурсия

  • Третья рекурсия

  • Четвертая рекурсия

  • Седьмая рекурсия, уменьшенная в десять раз

Пример 3: набор Кантора [ править ]

переменные  : AB
константы  : нет
начало : {строка начальных символов}
правила : (A → ABA), (B → BBB)

Пусть A означает «тянуть вперед», а B означает «двигаться вперед».

Это производит знаменитый фрактальное множество Кантора на реальный прямой R .

Пример 4: кривая Коха [ править ]

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

переменные  : F
константы  : + -
начало : F
правила : (F → F + F − F − F + F)

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

п = 0:
F
п = 1:
F + F − F − F + F
п = 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
правила : (A → B − A − B), (B → A + B + A)
угол : 60 °

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

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

Пример 6: Драконья кривая [ править ]

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

переменные  : FG
константы  : + -
начало : F
правила : (F → F + G), (G → FG)
угол : 90 °

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

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

Пример 7: Фрактальный завод [ править ]

См. Также: Папоротник Барнсли
переменные  : XF
константы  : + - []
начало : X
правила : (X → F + [[X] -X] -F [-FX] + X), (F → FF)
угол : 25 °

Здесь 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)

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

а (х, у): х == 0 → а (1, y + 1) b (2,3)

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

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

а (0,2)

Становится

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

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

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

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

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

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

Открытые задачи [ править ]

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

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

Типы L-систем [ править ]

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

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

Хорошо известными L-системами на плоскости R 2 являются:

  • Кривые пространственно-разливочные ( Гильберта кривая , кривые Пеано , церковь Dekking, в kolams ),
  • Медиана заполняющей пространство кривых ( Леви С кривой , Хартер-Heighway кривой дракона , Дэвис-Кнут terdragon),
  • тайлинги ( сфинкс плиточный , Пенроуз ),
  • деревья, растения и т. д.

См. Также [ править ]

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

Примечания [ править ]

  1. ^ Линденмайер, Аристид (март 1968). «Математические модели клеточных взаимодействий в развитии II. Простые и ветвящиеся нити с двусторонними входами». Журнал теоретической биологии . 18 (3): 300–315. DOI : 10.1016 / 0022-5193 (68) 90080-5 . ISSN  0022-5193 . PMID  5659072 .
  2. ^ Гжегож Розенберг и Арто Саломаа. Математическая теория L-систем (Academic Press, Нью-Йорк, 1980). ISBN 0-12-597140-0 
  3. ^ Новый вид науки [1]
  4. ^ Хуа, Х., 2017, декабрь. Двунаправленная процедурная модель для архитектурного дизайна . В форуме компьютерной графики (Том 36, № 8, стр. 219-231).
  5. ^ Кари, Лила; Розенберг, Гжегож; Саломаа, Арто (1997). «L Systems». Справочник формальных языков . С. 253–328. DOI : 10.1007 / 978-3-642-59136-5_5 . ISBN 978-3-642-63863-3.

Книги [ править ]

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

Внешние ссылки [ править ]

  • Алгоритмическая ботаника в Университете Калгари
  • Ветвление: дерево L-системы　. Java-апплет и его исходный код ( открытый исходный код ) моделирования роста ботанического дерева с использованием L-системы.
  • Истинные фракталы Fractint L-System
  • OpenAlea : программная среда с открытым исходным кодом для моделирования предприятий [1], которая содержит L-Py , реализацию на языке Python систем Линденмайера с открытым исходным кодом [2]
  • "powerPlant" - программа для ландшафтного моделирования с открытым исходным кодом.
  • Домашняя страница Fractint
  • Простой генератор L-систем (Windows)
  • Lyndyhop: еще один простой генератор L-систем (Windows и Mac)
  • Генератор эволюционных L-систем (anyos *)
  • eXtended L-Systems (XL), грамматики реляционного роста и программная платформа с открытым исходным кодом GroIMP.
  • Апплет JAVA с множеством фрактальных фигур, созданных L-системами.
  • Моя графика - приложение для iPhone / iPad, которое генерирует несколько графических шаблонов L-системы.
  • Музыкальные L-системы: теория и приложения об использовании L-систем для создания музыкальных структур, от форм волны до макроформ.
  • Онлайн-эксперименты с 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-System Parser.
  • Сложность L-System [ мертвая ссылка ]
  • Реализация парсера L-системы и простой черепаховой графики на языке программирования Icon.
  • Генератор системы Линденмейера, Нолан Кэрролл
  • Bloogen: L-системы с генетическим уклоном
  1. ^ Прадаль, Кристоф; Фурнье, Кристиан; Вальдуриес, Патрик; Коэн-Булакия, Сара (2015). OpenAlea: научные рабочие процессы, сочетающие анализ данных и моделирование (PDF) . Материалы 27-й Международной конференции по управлению научными и статистическими базами данных - SSDBM '15 . п. 1. дои : 10,1145 / 2791347,2791365 . ISBN  9781450337090. S2CID  14246115 .
  2. ^ Будон, Фредерик; Прадаль, Кристоф; Cokelaer, Томас; Прусинкевич, Пшемыслав; Годен, Кристоф (2012). "L-Py: структура моделирования L-системы для моделирования разработки архитектуры предприятия на основе динамического языка" . Границы науки о растениях . 3 : 76. DOI : 10.3389 / fpls.2012.00076 . PMC 3362793 . PMID 22670147 .