L-системы
Построение снежинки Коха, дракона Хартера-Хайвея, деревьев производится с помощью L-систем. L-системы часто называются ещё и системами черепашьей графики.
Черепашья графика - это способ рисования линий на экране компьютера. Он состоит в том, что программист как бы управляет движением черепашки. Черепашка, ползая по экрану, оставляет за собой след. При этом цель программиста – управлять черепашкой так, чтобы черепашка нарисовала нужную линию. Команды управления черепашкой просты: сделать шаг вперёд (обозначается F), повернуть направо (обозначается +), повернуть налево (обозначается -), сделать шаг вперёд без перерисовки (прыжок, обозначается B). Вот из этих команд и составляется сценарий построения линии – строка команд. Величина одного шага и угол одного поворота при движении черепашки всегда остаются постоянными и задаются предварительно.
Например, F++F++F это равносторонний треугольник, если угол поворота равен pi/3, а F+F+F+F – это квадрат, если угол поворота равен pi/2 .
Построение L-системы происходит в три этапа.
o Сначала создаётся сценарий поведения черепашки.
o Потом подсчитывается размер линии, которая получится, если запустить этот сценарий на исполнение. Линия как бы рисуется в уме, а потом смотрится её размер. На основе этого размера подправляется масштаб, чтобы вся линия уместилась на экране.
o На экран запускается черепашка, которая рисует линию.
Фракталы – самоподобные фигуры, значит, и сценарии у них должны быть самоподобные.
o Берётся начальная фигура (называется - аксиома), например, F++F++F с углом pi/3 .
o Задаётся правило замены F (называется правило newF) , например, newF = F-F++F-F ;
o В имеющейся фигуре (в сценарии) все F заменяются на newF. В нашем примере получим
F-F++F-F++F-F++F-F++ F-F++F-F
o Повторяем предыдущий шаг N раз. На втором шаге мы получим
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
Деревья.
У деревьев есть ветки. Тут имеющимся набором команд не обойдёшься. Приходится вводить ещё пару команд: начало ветви (обозначается [ ), конец ветви (обозначается ] ). В начале ветви черепашка должна запомнить своё состояние (положение и направление взгляда), а когда ей встретится соответствующий конец ветви, она должна вернуться в то положение, которое запомнила.
Рассмотрим пример, иллюстрирующий применение команд ветвления в L-системах, при построении фрактала «Куст». Запишем построение данного фрактала в виде таблицы.
Вход | |
Аксиома (axiom) | ‘F’ |
Порождающее правило (newf) | ‘FFF[+F[+++F][-F][+F]][-F[---F][-F][+F]]’ |
Начальный угол (α) | π/2 |
Угол поворота (θ) | π/4 |
Построение аксиомы.
Будем считывать каждый символ, и наблюдать за действиями черепашки.
Символ | F | F | F | [ | + | F | [ | + | + | + | F | ] | [ | - | F | ] | [ | + | F | ] | ] | [ |
Номер символа | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
Символ | - | F | [ | - | - | - | F | ] | [ | - | F | ] | [ | + | F | ] | ] |
|
|
|
|
|
Номер символа | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
|
|
|
|
|
То, как «двигается» черепашка при прочтении символов
F, –, +, описано выше.
Запишем построение первой итерации данного фрактала в виде таблицы.
Состояние | Действие | Стек |
начальное | Находится в (x0, y0) | пустой |
1-й симв. | Переход в (x1, y1) | пустой |
2-й симв. | Переход в (x2, y2) | пустой |
3-й симв. | Переход в (x3, y3) | пустой |
4-й симв. | Записать в стек | (x1, y1, α) |
5-й симв. | Поворот | (x1, y1, α) |
6-й симв. | Переход в (x4, y4) | (x1, y1, α) |
7-й симв. | Записать в стек | (x1, y1, α) |
8-й симв. | Поворот | (x1, y1, α) |
9-й симв. | Поворот | (x1, y1, α) |
10-й симв. | Поворот | (x1, y1, α) |
11-й симв. | Переход в (x5, y5) | (x1, y1, α) |
12-й симв. | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
13-й симв. | Записать в стек | (x1, y1, α) |
14-й симв. | Поворот | (x1, y1, α) |
15-й симв. | Переход в (x6, y6) | (x1, y1, α) |
16-й симв. | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
17-й симв. | Записать в стек | (x1, y1, α) |
18-й симв. | Поворот | (x1, y1, α) |
19-й симв. | Переход в (x7, y7) | (x1, y1, α) |
20-й симв. | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
21-й симв. | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
22-й симв. | Записать в стек | (x1, y1, α) |
23-й симв. | Поворот | (x1, y1, α) |
24-й симв. | Переход в (x8, y8) | (x1, y1, α) |
25-й симв | Записать в стек | (x1, y1, α) |
26-й симв | Поворот | (x1, y1, α) |
27-й симв | Поворот | (x1, y1, α) |
28-й симв | Поворот | (x1, y1, α) |
29-й симв | Переход в (x9, y9) | (x1, y1, α) |
30-й симв | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
31-й симв | Записать в стек | (x1, y1, α) |
32-й симв | Поворот | (x1, y1, α) |
33-й симв | Переход в (x10, y10) | (x1, y1, α) |
34-й симв | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
35-й симв | Записать в стек | (x1, y1, α) |
36-й симв | Поворот | (x1, y1, α) |
37-й симв | Переход в (x11, y11) | (x1, y1, α) |
38-й симв | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
39-й симв | Считать из стека, переход в считанные координаты, удаление считанной записи (вернулись в координаты (x1, y1)) | пустой |
В результате получаем:
Пример художественной композиции:
