L-системы как средство генерации некоторых природных объектов

NovaInfo 39, скачать PDF
Опубликовано
Раздел: Технические науки
Просмотров за месяц: 15
CC BY-NC

Аннотация

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

Ключевые слова

L-СИСТЕМА, АКСИОМА, ПРИРОДНЫЕ ОБЪЕКТЫ, ФРАКТАЛ, ПОРОЖДАЮЩЕЕ ПРАВИЛО

Текст научной работы

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

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

При графической реализации L-систем используется turtle-графика — так называемая "черепашья" графика. Правила в этой графике весьма просты, и заключаются в следующем. Точка (черепашка) дискретными шагами движется по экрану и прочерчивает за собой след, при необходимости возможно перемещение точки без оставления следа. В каждый момент времени координаты и состояние точки определяется тремя параметрами на плоскости: координаты точки и направление, в котором будет двигаться точка. Точка может распознавать и выполнять некоторую последовательность команд, состоящую из последовательностей символов (или групп символов в более сложном случае), читающихся слева направо. Ниже в таблице 1 приведены наиболее часто используемые символы последовательности и их назначение.

Таблица 1. Интерпретация символов в L-системе

Символ последовательности

Назначение (интерпретация)

F

Перемещение на 1 шаг вперед с прорисовкой следа.

b

Перемещение на 1 шаг вперед без прорисовки следа.

[

Открыть ветвь.

]

Закрыть ветвь.

+

Увеличение угла на указанную величину.

Уменьшение угла на указанную величину.

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

Аксиома: F

Порождающее правило: FbF+

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

1. FbF+

2. FbF+bFbF++

3. FbF+bFbF++bFbF+bFbF+++

4. FbF+bFbF++bFbF+bFbF+++bFbF+bFbF++bFbF+bFbF++++

5. FbF+bFbF++bFbF+bFbF+++bFbF+bFbF++bFbF+bFbF++++bFbF+bFbF++bFbF+bFbF+++bFbF+bFbF++bFbF+bFbF+++++

Рекурсивная природа L-систем позволяет строить на основе них геометрические фракталы. Так, при количестве итераций, больших 8, на основе приведенной аксиомы и порождающего правила получим вполне определенное изображение фрактала (следует принять приращение угла, равное 90 градусов).

В приведенной таблице символы "[" и "]" выступают в качестве команд ветвления, — они используются при построении растений и деревьев. При этом, если в последовательности символов встречается символ "[", то запоминается положение и направление движения точки (тройка чисел (x,y,a)), к этим параметрам будет осуществлен возврат позднее. Обычно для хранения таких троек чисел при программной реализации алгоритма используется стек: новые значения параметров записываются в конец стека. В случае, когда ветвь закрывается (встречается символ "]"), тройкам чисел (x,y,a) присваиваются значения, считанные с конца стека, после чего эти значения из стека удаляются.

Часто в L-системы вводят дополнительные переменные (X, Y, Z и другие), которые призваны облегчить построение системы. Также могут использоваться не только отдельные символы, но и их группы, а также цифры и числа. Числа, например, могут использоваться для задания конкретных цветов при графическом построении.

Рассмотрим теперь некоторые примеры аксиом и порождающих правил для L-системы, задаваемой на основе символов из таблицы 1, а также результаты построения, получаемые на основе этих правил. Для удобства представим аксиомы и порождающие правила в виде таблицы 2 (все правила получены автором работы). Результаты построения приведены ниже на рис. 1-15, и выполнены в разрабатываемой автором программе (цифры в правилах отвечают за цвет рисуемого участка). Отмечу, что для рис. 9 получаются замкнутые фрактальные изображения при четном количестве итераций, а для рис. 10 — при нечетном. Рис. 12 и 15 представлены в работе в уменьшенном масштабе, изображения в полном разрешении представлены в [7, 8].

Таблица 2. Примеры аксиом и порождающих правил для L-системы

Аксиома и порождающее правило

Приращение угла

Вложенность

Начальный угол

Рисунок

Аксиома: F+F-FbF

Правило: b-3Fb4F-b

11

12

-90

1 (а)

17

1(б)

Аксиома: FF+F-FF-F+FF

Правило: [3F]-2F++2F-[3F]

25

4

-90

2

Аксиома: F+F-FF

Правило: -F+[FF++FF++FF]-F+

12

4

-60

3

Аксиома: F+F-[F+Fb+F]-[F-F]

Правило: -2F-[-1Fb+bF]+[bb4Fb-b2F+4F-bb2F]+[bF+b3FbF]-3bF+

30

3

0

4

Аксиома: F-F

Правило: -F-[FbF-FbF]+-+[FF]+F-FF+[FF+FF]

30

3

0

5

Аксиома: F-F

Правило: -F-[FF-FF]+[FF+FF]+F-F-[FF+FF+F]+F+

30

3

0

6

Аксиома: F-F

Правило: -F-[FF+FF]+[F]+FF-[-FFF]+[FF+FF]

15

3

-60

7

Аксиома: F-F

Правило: -2F-[1F1F-3FF-F4F]+[F+FbFF]+FF-[-FF+FF]+[FbF+FF+FF-F]

15

3

-60

8

Аксиома: F++F++F

Правило: -2F3F-

60

8

-60

9

10

12

14

Аксиома: F++F++F

Правило: -FF-

75

7

-90

10

11

13

15

Аксиома: F++F++F++F

Правило: +FF--FF+

45

2

-90

11

3

4

5

Аксиома: F

Правило: -2F3F4F-F+F+F-4F3F2F-

90

6

-90

12

Аксиома: F++F++F

Правило: +2F3F--4F3F++3F4F-3-F2F+

60

2

-60

13

3

4

Аксиома: F++F++F++F++F++F

Правило: +FF--[F+F]++[F+F]--FF+

30

4

-90

14

Аксиома: F++F-F++F

Правило: FF+[-FF-F+F+F]F-

30

6

-90

15

Результат построения на основе L-систем: пример 1
Рисунок 1. Результат построения на основе L-систем: пример 1
Результат построения на основе L-систем: пример 2 (водоросль)
Рисунок 2. Результат построения на основе L-систем: пример 2 (водоросль)
Результат построения на основе L-систем: пример 3 (куст)
Рисунок 3. Результат построения на основе L-систем: пример 3 (куст)
Результат построения на основе L-систем: пример 4 (ветвь)
Рисунок 4. Результат построения на основе L-систем: пример 4 (ветвь)
Результат построения на основе L-систем: пример 5 (куст)
Рисунок 5. Результат построения на основе L-систем: пример 5 (куст)
Результат построения на основе L-систем: пример 6 (куст)
Рисунок 6. Результат построения на основе L-систем: пример 6 (куст)
Результат построения на основе L-систем: пример 7 (куст)
Рисунок 7. Результат построения на основе L-систем: пример 7 (куст)
Результат построения на основе L-систем: пример 8 (густой куст)
Рисунок 8. Результат построения на основе L-систем: пример 8 (густой куст)
Результат построения на основе L-систем: пример 9 (фрактал)
Рисунок 9. Результат построения на основе L-систем: пример 9 (фрактал)
Результат построения на основе L-систем: пример 10 (фрактал)
Рисунок 10. Результат построения на основе L-систем: пример 10 (фрактал)
Результат построения на основе L-систем: пример 11 (фрактал)
Рисунок 11. Результат построения на основе L-систем: пример 11 (фрактал)
Результат построения на основе L-систем: пример 12 (фрактал)
Рисунок 12. Результат построения на основе L-систем: пример 12 (фрактал)
Результат построения на основе L-систем: пример 13 (фрактал)
Рисунок 13. Результат построения на основе L-систем: пример 13 (фрактал)
Результат построения на основе L-систем: пример 14
Рисунок 14. Результат построения на основе L-систем: пример 14
Результат построения на основе L-систем: пример 15 (ветвь)
Рисунок 15. Результат построения на основе L-систем: пример 15 (ветвь)

Рассмотренные примеры показывают, что хорошо подобранные аксиомы и порождающие правила позволяют получить интересные изображения, в том числе очень похожие на ветви деревьев (или сами деревья) и кустарники.

Читайте также

Список литературы

  1. Дмитриев В.Л., Мухаметова А.К. Популярно о фракталах: исторический экскурс // NovaInfo.Ru. 2015. № 38. [Электронный ресурс]. – Режим доступа: http://novainfo.ru/archive/38/populyarno-o-fraktalakh-istoricheskiy-ekskurs (дата обращения: 17.11.2015).
  2. Дмитриев В.Л., Мухаметова А.К. Популярно о фракталах: новая дробная размерность // NovaInfo.Ru. 2015. № 38. [Электронный ресурс]. – Режим доступа: http://novainfo.ru/archive/38/populyarno-o-fraktalakh-novaya-drobnaya-razmernost (дата обращения: 18.11.2015).
  3. Дмитриев В.Л., Мухаметова А.К. Популярно о фракталах: многообразие фракталов и их классификация // NovaInfo.Ru. 2015. № 38. [Электронный ресурс]. – Режим доступа: http://novainfo.ru/archive/38/mnogoobrazie-fraktalov-i-ikh-klassifikatsiya (дата обращения: 20.11.2015).
  4. Дмитриев В.Л., Мухаметова А.К. Популярно о фракталах: применение фракталов и обзор программ // NovaInfo.Ru. 2015. № 38. [Электронный ресурс]. – Режим доступа: http://novainfo.ru/archive/38/primenenie-fraktalov-i-obzor-programm (дата обращения: 23.11.2015).
  5. Кроновер Р.М. Фракталы и хаос в динамических системах. – М.: Постмар-кет. 2000. – 352 с.
  6. Proceedings of the 5th International Workshop on Functional-Structural Plant Models. Abstracts of Papers and Posters. / Przemyslaw Prusinkiewicz, Jim Hanan, and Brendan Lane. – Napier, New Zealand. 2007. – 333 p.
  7. Пример 12 (фрактал). [Электронный ресурс]. – Режим доступа: https://yadi.sk/i/LaG5kMiymR3C4 (дата обращения: 23.12.2015).
  8. Пример 15 (ветвь). [Электронный ресурс]. – Режим доступа: https://yadi.sk/i/YRlcyt4GmR3E8 (дата обращения: 23.12.2015)

Цитировать

Дмитриев, В.Л. L-системы как средство генерации некоторых природных объектов / В.Л. Дмитриев. — Текст : электронный // NovaInfo, 2015. — № 39. — URL: https://novainfo.ru/article/4075 (дата обращения: 30.09.2022).

Поделиться