L-система - L-system

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью от добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «L-система»  – Новости  · газеты  · книги  · ученый  · JSTOR (апрель 2013) (Узнайте, как и когда удалить этот шаблон сообщения) эта статья читается как учебник и может потребовать уборка. Пожалуйста помоги чтобы улучшить эту статью сделать это нейтральный в тон и познакомьтесь с Википедией стандарты качества. (Август 2020 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Деревья 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-я позиция от левого конца строки, значение определяется тем, кратно ли Золотое сечение попадает в интервал ${ Displaystyle (к-1, к)}$. Отношение A к B аналогично сходится к золотой середине.

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

Эта последовательность представляет собой локально катенативная последовательность потому что ${ Displaystyle G (N) = G (N-1) G (N-2)}$, где ${ Displaystyle G (п)}$ это п-го поколения.

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

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

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

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

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

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

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

переменные : А Б

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

Начните : A {строка начальных символов}

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

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

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

Пример 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-системы.

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

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

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

переменные : X Y

константы : F + -

Начните : FX

правила : (X → X + YF +), (Y → −FX − Y)

угол : 90°

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

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

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

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

Начните : ИКС

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

угол : 25°

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

Вариации

Был разработан ряд усовершенствований этой базовой техники 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-системы на плоскости р² находятся:

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

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

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

Заметки

Книги

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

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