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

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

Истоки

«Сорняки», созданные с использованием 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-систему. [ требуется уточнение ] Таким образом, L-системы являются строгими подмножествами языков. [ нужно уточнение ]

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

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

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

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

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

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

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

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

п = 0 : А
п = 1 : АВ
п = 2 : АБК
п = 3: АВААБ
n = 4 : АБААБАБА
n = 5 : АБАБАБААБААБ
n = 6 : АБААБАБАБАБАБАБАБАБА
n = 7: АБААБАБААБААБАБАБАБАБААБААБАБАБААБ

Пример 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 из-за нашего выбора аксиомы):

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

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

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

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

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

  • Аксиома

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

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

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

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

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

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

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

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

Это дает знаменитый фрактал Кантора, расположенный на реальной прямой линии 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-системы.

переменные  : ФГ
константы  : + -
начало  : 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 означают «тянуть вперед», + означает «повернуть налево на угол», а - означает «повернуть направо на угол» (см. Рисунок черепахи ).

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

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

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

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

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

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

Пример 7: Фрактальная установка

См. Также: папоротник Барнсли .
переменные  : XF
константы  : + − [ ]
начало  : Х
правила  : (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, у + 1) б (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) обратного процесса, реализующего дерево с формами поэтапно (от листьев к корню). Каждый шаг обратного вывода включает в себя существенные геометро-топологические рассуждения. С помощью этой двунаправленной структуры ограничения и цели дизайна закодированы в переводе формы грамматики. В приложениях для архитектурного дизайна двунаправленная грамматика обеспечивает согласованную внутреннюю связность и богатую пространственную иерархию. [3]

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

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

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

Типы L-систем

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

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

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

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

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

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

Примечания

  1. ^ Линденмайер, Аристид (март 1968 г.). «Математические модели клеточных взаимодействий в развитии II. Простые и ветвящиеся нити с двусторонними входами». Журнал теоретической биологии . 18 (3): 300–315. Бибкод : 1968JThBi..18..300L . doi : 10.1016/0022-5193(68)90080-5 . ISSN  0022-5193 . PMID  5659072 .
  2. ^ Гжегож Розенберг и Арто Саломаа. Математическая теория L-систем (Academic Press, Нью-Йорк, 1980). ISBN 0-12-597140-0 
  3. ^ Хуа, Х., 2017, декабрь. Двунаправленная процедурная модель для архитектурного проектирования . На форуме компьютерной графики (том 36, № 8, стр. 219-231).
  4. ^ Кари, Лила; Розенберг, Гжегож; Саломаа, Арто (1997). «Л Системы». Справочник по формальным языкам . стр. 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). Новая математика архитектуры, Нью-Йорк: Темза и Гудзон.
  • Аристид Линденмайер, « Математические модели клеточного взаимодействия в процессе развития ». Дж. Теорет. Биология, 18:280—315, 1968.

внешняя ссылка

  • Алгоритмическая ботаника в Университете Калгари
  • Ветвление: дерево L-системы　Java - апплет и его исходный код ( с открытым исходным кодом ) моделирования роста ботанического дерева с использованием L-системы.
  • Истинные фракталы Fractint L-System
  • OpenAlea Архивировано 17 октября 2005 г. в Wayback Machine : программная среда с открытым исходным кодом для моделирования растений, [1] которая содержит L-Py , реализацию систем Lindenmayer на Python с открытым исходным кодом [2]
  • PowerPlant — программа для моделирования ландшафтов с открытым исходным кодом.
  • Домашняя страница Фрактинта
  • Простой генератор L-систем (Windows)
  • Lyndyhop: еще один простой генератор L-систем (Windows и Mac)
  • Генератор эволюционных L-систем (anyos*)
  • eXtended L-Systems (XL), грамматики реляционного роста и программная платформа с открытым исходным кодом GroIMP.
  • Апплет JAVA с множеством фрактальных фигур, сгенерированных L-системами. Архивировано 6 августа 2016 г. в Wayback Machine .
  • My Graphics — приложение для iPhone/iPad, которое генерирует несколько графических шаблонов L-системы.
  • Музыкальные L-системы: теория и приложения об использовании L-систем для создания музыкальных структур, от волновых форм до макроформ.
  • Онлайн-эксперименты с L-Systems с использованием JSXGraph (JavaScript)
  • Flea Реализация LSYSTEM на Ruby с использованием предметно-ориентированного языка вместо кратких команд генератора.
  • Lindenmayer power Установка и генератор фракталов с использованием L-систем (JavaScript)
  • Розенберг, Г.; Саломаа, А. (2001) [1994], «L-системы» , Математическая энциклопедия , EMS Press
  • L-Parser Лоренса Лапре. Архивировано 13 сентября 2013 г. в Wayback Machine .
  • HTML5 L-Systems — попробуйте эксперименты онлайн
  • Программа векторной графики Inkscape включает анализатор L-System.
  • Сложность L-системы [ мертвая ссылка ]
  • Реализация парсера L-системы и простой графики черепахи на языке программирования Icon.
  • Генератор системы Линденмейера от Нолана Кэрролла
  • Bloogen: L-системы с генетическим уклоном
  1. ^ Прадал, Кристоф; Фурнье, Кристиан; Вальдурье, Патрик; Коэн-Булакия, Сара (2015). OpenAlea: научные рабочие процессы, сочетающие анализ данных и моделирование (PDF) . Материалы 27-й Международной конференции по управлению научными и статистическими базами данных - SSDBM '15 . п. 1. doi : 10.1145/2791347.2791365 . ISBN  9781450337090. S2CID  14246115 .
  2. ^ Будон, Фредерик; Прадаль, Кристоф; Кокелер, Томас; Прусинкевич, Пшемыслав; Годин, Кристоф (2012). «L-Py: среда моделирования L-системы для моделирования разработки архитектуры предприятия на основе динамического языка» . Границы науки о растениях . 3 : 76. doi : 10.3389/fpls.2012.00076 . ПВК 3362793 . PMID 22670147 .  
Получено с https://en.wikipedia.org/w/index.php?title=L-system&oldid=1062288091 .
Contribute a better translation