ГЛАВА 5

Понятие Л-систем, тесно связанное с самоподобными фракталами появилось в 1968 году благодаря Аристиду Линденмайеру. Изначально Л-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и ковер Серпинского. Некоторые другие классические построения, например кривые Пеано (работы Пеано, Гильберта, Серпинского) также укладываются в эту схему. И конечно Л-системы открывают путь к бесконечному разнообразию новых фракталов, что и послужило причиной их широкого применения в компьютерной графике для построения фрактальных моделей.

Для графической реализации Л-систем в качестве подсистемы вывода используется так называемая turtle-графика (черепаший алгоритм). При этом точка (черепашка) движется по экрану дискретными шагами, как правило, прочерчивая свой след, но при необходимости может перемещаться без рисования. В нашем распоряжении имеются три параметра $(x,y,\alpha)$ , где - координаты черепашки, $\alpha$ - направление, в котором она смотрит. Черепашка обучена интерпретировать и выполнять последовательность команд, задаваемых кодовым словом, буквы которого читаются слева направо. кодовое слово представляет собой результат работы Л-системы и может включать следующие буквы:

F - переместиться вперед на один шаг, прорисовывая след;

b - не прорисовывая след;

[ - открыть ветвь;

] - закрыть ветвь;

+ - увеличить угол $\alpha$ на величину $\theta$ ;

- уменьшить.

Размер шага и величина приращения по углу $\theta$ задаются заранее и остаются неизменными для всех перемещений черепашки. Если начальное направление движения $\alpha$ (угол, отсчитываемый от положительного направления оси ) не указано, то полагаем $\alpha$ равным нулю.

Несколько примеров иллюстрируют применение команд ветвления (обозначаются [, ]) и вспомогательных переменных (обозначаются X, Y и т.д.). Команды ветвления используются для построения деревьев и растений, а вспомогательные переменные заметно облегчают построение некоторых Л-систем.

Формально, детерминированная Л-система состоит из алфавита, слова инициализации, называемого инициатором, и набора порождающих правил (генератора), указывающих как следует преобразовывать слово при переходе от уровня к уровню (от итерации к итерации). К примеру, можно заменять букву F при помощи порождающего правила newF=F-F++F-F, что соответствует Л-системе для снежинки Коха, рассматриваемой ниже. Символы , не обновляются, а просто остаются на тех местах, где они встретились. Обновление букв в данном слове предполагается одновременным, то есть все буквы одного уровня обновляются раньше любой буквы следующего уровня. Л-система, соответствующая снежинке Коха, задается следующим образом:

$\theta=\displaystyle\frac{\pi}3,$

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

Генератор: newF=F-F++F-F.

Графическое представление аксиомы F++F++F - равносторонний треугольник. Черепашка делает один шаг вперед, затем угол $\alpha$ увеличивается на $2\pi/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=newF, b=newb, выглядит следующим образом:

Назначение: реализует правила F=newF, b=newb.

Вход:

axiom (слово инициализациии)

newF (генератор)

level (число итераций)

Выход:

word (слово-результат)

Инициализация:

W=axiom

n=length(W)

T={ } (пустое множество)

Шаги:

while level>0 for j=1 to n

if W(j)=+; T={T +}; end if

if W(j)=-; T={T -}; end if

if W(j)=[; T={T [}; end if

if W(j)=]; T={T ]}; end if

if W(j)=F; T={T newF}; end if

if W(j)=b; T={T newb}; end if

end for

W=T

level=level-1

end while

word=W

Замечание: W(j) - j-я буква в слове W, {T +} строки T, к которой присоединен знак +.

ГЛАВА 4

НАВЕРХ

ГЛАВА 6