Понятие L-систем тесно связанное с самоподобными фракталами, появилось только в 1968 году благодаря Аристриду Линденмайеру. Изначально L-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и ковер Серпинского. Некоторые другие классические построения, например кривые Пеано (работы Пеано, Гильберта, Серпинского), также укладываются в эту схему. И конечно, L-системы открывают путь к бесконечному разнообразию новых фракталов, что и послужило причиной их широкого применения в компьютерной графике для построения фрактальных деревьев и растений. Наше изложение L-систем следует
Для графической реализации L-систем в качестве подсистемы вывода используется так называемая тертл-графика (turtle — черепаха). При этом точка (черепашка) движется по экрану дискретными шагами, как правило, прочерчивая свой след, но при необходимости может перемещаться без рисования. В нашем распоряжении имеются три параметра (x, у, alpha), где (x, у) — координаты черепашки, аlpha — направление, в котором она смотрит. Черепашка обучена интерпретировать и выполнять последовательность команд, задаваемых кодовым словом, буквы которого читаются слева направо. Кодовое слово представляет собой результат работы L-системы и может включать следующие буквы:
F - переместиться вперед на один шаг, прорисовывая след.
b- переместиться вперед на
один шаг, не прорисовывая след.
[ - открыть ветвь (подробнее см. ниже)
] закрыть ветвь (подробнее см. ниже)
+
увеличить угол аlpha на величину teta
уменьшить угол аlpha на величину teta
Размер шага и величина приращения по углу teta задаются заранее и остаются неизменными для всех перемещений черепашки. Если начальное направление движения аlpha (угол, отсчитываемый от положительного направления оси X) не указано, то полагаем о равным нулю.
Несколько примеров иллюстрируют применение команд ветвления (обозначаются ], [) и вспомогательных переменных (обозначаются X, У и т. д.). Команды ветвления используются для построения деревьев и растений, а вспомогательные переменные заметно облегчают построение некоторых L-систем.
Формально, детерминированная L-система состоит из алфавита, слова инициализации, называемого аксиомой или инициатором, и набора порождающих правил, указывающих, как следует преобразовывать слово при переходе от уровня к уровню (от итерации к итерации). К примеру, можно заменять букву F при помощи порождающего правила newf = F—F++F—F, что соответствует L-системе для снежинки Коха, рассматриваемой ниже. Символы +, —, ], [ не обновляются, а просто остаются на тех местах, где они встретились. Обновление букв в данном слове предполагается одновременным,то есть все буквы слова одного уровня обновляются раньше любой буквы следующего уровня.
L-система, соответствующая снежинке Коха, задается следующим образом:
teta=pi/3Графическое представление аксиомы F++F++F — равносторонний треугольник. Черепашка делает один шаг вперед, затем угол аlpha увеличивается на 2pi/3 и черепашка делает еще один шаг вперед, угол о снова увеличивается на 2pi/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 = newf, b = newb, выглядит следующим образом:
Алгоритм 2.2.1. (L-СИСТЕМЫ)
Назначение: реализует правила F = newf, b = newb.
Вход:
axiom (слово инициализации) newf (порождающее правило) newb (порождающее правило) level (число итераций)
Выход:
word (слово-результат)
Инициализация:
W = axiom
n = length(W)
Т = { } (пустое множество)
Шаги:
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[}, endif
if W(j)=] ,T={T ]}, endif
if W(j) =F, T={T newf}, end if
if W(j)
= b, Т = {Т newb}, end if
end for W =T
level = level
- 1
end while
word
= W
Замечание: W{j) — j-ая буква в слове W, {Т +} — строка T, к которой присоединен знак +.
График на рис. 2.10 не имеет разрывов, так как черепашка движется единичными шагами и каждый раз прорисовывает свой след. Разрывные графики можно получать, применяя в L-системе команду «Ь», то есть команду «переместиться на один шаг вперед без рисования».
При построении фракталов с использованием только одного порождающего правила возникает следующая трудность. Мы не можем изменить направление чтения правила на некоторых шагах, то есть читать его не слева направо, а справа налево.
Например, для того чтобы построить фрактал под названием «дракон Хартера-Хайтвея», необходимо иметь возможность менять направление чтения порождающего правила, изображенного на рис. 2.13. В качестве инициатора, или аксиомы, используется кривая слева. Порождающее правило в данном случае заключается в том, чтобы нарисовать инициатор сначала в прямом, а затем в обратном направлении. Подобная схема не вписывается в рамки L-систем, использующих только одно порождающее правило. Эту проблему можно решить, введя две различных команды для передвижения вперед, например Х и Y. Будем считать, что черепашка интерпретирует Х и Y одинаково, то есть как один шаг вперед.
С помощью этих двух букв порождающее правило для дракона можно записать следующим образом:
axiom = X
newx
= X+Y+, newy = -X-Y.
Однако, нам не хотелось бы отказываться от первоначального подхода, при котором имеется только одна буква интерпретируемая как один шаг вперед. Чтобы вернуться в рамки этого подхода, будем считать буквы Х и Y вспомогательными переменными, игнорируемыми черепашкой, и заменим их в порождающем правиле на FX и FY соответственно. Получим:
axiom = FX
FX =FX+YF+,
YF =
-FX-YF.
Далее замечаем, что того же результата можно добиться при помощи следующих порождающих правил:
axiom = FX,
newf = F, newx = X+YF+, newy =
-FX-Y.
Ниже приведены несколько шагов построения дракона с использованием этих порождающих правил:
1-ый шаг: FX+YF+
2-ый шаг: FX+YF++-FX-YF+
3-ый шаг: FX+YF++-FX-YF++-FX+YF+--FX-YF+
4-ый шаг: FX+YF++-FX-YF++-FX+YF+—FX-YF++ -FX+YF++-FX-YF+—FX+YF+—FX-YF+
На рис. 2.14 изображен дракон после 12 итераций. Заметьте, что дракон состоит из нескольких похожих частей.
В заключение остановимся на операции ветвления. Когда мы встречаем символ [ (открыть ветвь), мы запоминаем положение и направление черепашки, то есть переменные (x, у, аlpha), и возвращаемся к этим установкам позднее. Для хранения триплетов (x, у, аlpha) используется стек
причем новые данные записываются в конец стека. Когда ветвь закрывается, переменным (x, у, аlpha) присваиваются значения, считанные из конца стека. Затем эти значения из стека удаляются. Таким образом, ветвление задается двумя символами:
[ Открыть ветвь. Сохранить (x, у, аlpha) в
конце стека.
] Закрыть ветвь. Присвоить переменным (x, у, аlpha) значения,
считанные из конца стека, после чего удалить их из стека.
На рис. 2.15 и 2.16 изображены фракталы, построенные с помощью операции ветвления.
Ниже приведен алгоритм, который позволяет получать графическое представление слова при помощи тертл-графики.
Алгоритм 2.2.2. (ТЕРТЛ-ГРАФИКА)
Назначение: реализует тертл-графику для кодового слова, состоящего из букв F, Ь, [, ], + и —.
Вход:
word (результат работы L-системы)
teta (приращение по углу)
аlpha (начальное направление)
Выход:
Графическое представление word.
Инициализация:
графический режим (подробнее см. ниже) W = word
x0=0
y0=0
n = length(word)
stack =
{ } (пустое множество)
Шаги:
for j = 1 to n
if W{j) = +, alpha = alpha + teta, end if
if W(j) = —, alpha = alpha -teta, end if
if W(j) = F, x = x0 + cos(alpha), у =
у0 + sin(alpha),
провести
линию из точки (х0,у0) в точку (x, у),
x0 = x,
y0 = y
end if
if W(j) = b,
x0 =
x0 + cos(alpha), у0
= у0 + sin(alpha),
end if
ifW(j)=[,
l = length(stack),
stack (l + 1,1) = x0
stack (l+1,2)= у0
stack(l+l,3)= alpha
end if
ifW(j)=],
l =length(stack),
x0= stack (l,1)
y0 =stack (l,2)
alpha = stack (l,3)
удалить l-тую запись из stack
end if
end for
Можно написать специальную программу для определения размеров графического окна. Для этого достаточно выполнить в точности те же шаги, что и в алгоритме 2.2.2, но вместо вывода на экран надо отслеживать наименьшее и наибольшее значения х и у. Вначале положим эти значения равными нулю:
Каждый раз, когда появляется новая точка (x,y), размеры окна обновляются:
Значения xmin,xmax,ymin,ymax, полученные по окончании работы алгоритма, используются для инициализации окна вывода тертл-графики.
Дракон Хартера-Хайтвея
axiom=FX
newf=F
newx=X+YF+
newy=-FX-Y
teta=pi/2
Ковер Cерпинского
axiom=FXF--FF--FF
newf=FF
newx=--FXF++FXF++FXF--
teta=pi/3
Кривая Гильберта
axiom=X
newf=F
newx=-YF+XFX+FY-
newy=+XF-YFY-FX+
teta=pi/2
Кривая Госпера
axiom=XF
newf=F
newx=X+YF++YF-FX--FXFX-YF+
newy=-FX+YFYF++YF+FX--FX-Y
teta=pi/3
Кривая Пеано
axiom=F
newf=F-F+F+F+F-F-F-F+F
alpha=pi/4
teta=pi/2
Кривая Серпинского
axiom=F+XF+F+XF
newf=F
newx=XF-F+F-XF+F+XF-F+F-X
alpha=pi/4
teta=pi/2
Куст
axiom=F
newf=-F+F+[+F-F-]-[-F+F+F]
teta=pi/8
Мозаика
axiom=F-F-F-F
newf=F-b+FF-F-FF-Fb-FF+b-FF+F+FF+Fb+FFF
newb=bbbbbb
Остров
axiom=F+F+F+F
newf=F+F-F-FFF+F+F-F
teta=pi/2
Снежинка
axiom=[F]+[F]+[F]+[F]+[F]+[F]
newf=F[++F][--F]FF[+F][-F]FF
teta=pi/3
Снежинка Коха
axiom=F++F++F
newf=F-F++F-F
teta=pi/2
Сорняк
axiom=F
newf=F[+F]F[-F]F
teta=pi/7
Цветок
axiom=F[+F+F][-F-F][++F][--F]F
newf=FF[++F][+F][F][-F][--F]
alpha=pi/2
teta=pi/16
Цепочка
axiom=F+F+F+F
newf=F+b-F-FFF+F+b-F
newb=bbb
teta=pi/2