WikiDer > L-система

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

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

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

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

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

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

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

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

г = (V, ω, п),

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта последовательность представляет собой локально катенативная последовательность потому что , где это п-го поколения.

Пример 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: множество Кантора

Набор Кантора за семь итераций.svg
переменные : А Б
константы : никто
Начните : A {строка начальных символов}
правила : (A → ABA), (B → BBB)

Позволять А означает "тянуть вперед" и B означают «двигаться вперед».

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

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

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

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

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

п = 0:
F
Квадрат Коха - 0 итераций
п = 1:
F + F − F − F + F
Квадрат Коха - 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
Квадрат Коха - 2 итерации
п = 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
Квадрат Коха - 3 итерации

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

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

переменные : F G
константы : + −
Начните : F − G − G
правила : (F → F − G + F + G − F), (G → GG)
угол : 120°

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

  • п = 2

  • п = 4

  • п = 6

Также возможно приблизить Треугольник Серпинского с помощью Кривая наконечника стрелы Серпинского L-система.

переменные : А Б
константы : + −
Начните : А
правила : (A → B − A − B), (B → A + B + A)
угол : 60°

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

Серпинский Lsystem.svg
Эволюция для п = 2, п = 4, п = 6, п = 8

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

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

переменные : X Y
константы : F + -
Начните : FX
правила : (X → X + YF +), (Y → −FX − Y)
угол : 90°

Здесь F означает «тянуть вперед», - означает «повернуть налево на 90 °», а + означает «повернуть направо на 90 °». X и Y не соответствуют никакому действию рисования и используются только для управления эволюцией кривой.

Кривая дракона L-system.svg
Кривая дракона для п = 10

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

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

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

Фрактальный завод для п = 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-системы на реальная линия р:

Известные L-системы на плоскости р2 находятся:

Смотрите также

Заметки

  1. ^ Линденмайер, Аристид (март 1968 г.). «Математические модели клеточных взаимодействий в развитии II. Простые и ветвящиеся нити с двусторонними входами». Журнал теоретической биологии. 18 (3): 300–315. Дои: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. Дои:10.1007/978-3-642-59136-5_5. ISBN 978-3-642-63863-3.

Книги

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

  1. ^ Прадаль, Кристоф; Фурнье, Кристиан; Вальдуриес, Патрик; Коэн-Булакия, Сара (2015). OpenAlea: научные рабочие процессы, сочетающие анализ данных и моделирование (PDF). Материалы 27-й Международной конференции по управлению научными и статистическими базами данных - SSDBM '15. п. 1. Дои:10.1145/2791347.2791365. ISBN 9781450337090. S2CID 14246115.
  2. ^ Будон, Фредерик; Прадаль, Кристоф; Cokelaer, Томас; Прусинкевич, Пшемыслав; Годен, Кристоф (2012). "L-Py: структура моделирования L-системы для моделирования разработки архитектуры предприятия на основе динамического языка". Границы растениеводства. 3: 76. Дои:10.3389 / fpls.2012.00076. ЧВК 3362793. PMID 22670147.