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

Размещено на http://www.allbest.ru/

Башкирский государственный университет

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

Дмитриев Владислав Леонидович

кандидат наук, доцент, доцент

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

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

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

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

Поэтому фактически, любая 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-системы

Рис. 1. Результат построения на основе L-систем: пример 1

Рис. 2. Результат построения на основе L-систем: пример 2 (водоросль)

Рис. 3. Результат построения на основе L-систем: пример 3 (куст)

Рис. 4. Результат построения на основе L-систем: пример 4 (ветвь)

Рис. 5. Результат построения на основе L-систем: пример 5 (куст)

Рис. 6. Результат построения на основе L-систем: пример 6 (куст)

Рис. 7. Результат построения на основе L-систем: пример 7 (куст)

Рис. 8. Результат построения на основе L-систем: пример 8 (густой куст)

Рис. 9. Результат построения на основе L-систем: пример 9 (фрактал)

Рис. 10. Результат построения на основе L-систем: пример 10 (фрактал)

Рис. 11. Результат построения на основе L-систем: пример 11 (фрактал)

Рис. 12. Результат построения на основе L-систем: пример 12 (фрактал)

Рис. 13. Результат построения на основе L-систем: пример 13 (фрактал)

Рис. 14. Результат построения на основе L-систем: пример 14

Рис. 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).

Размещено на Allbest.ru