ГЛАВА 5
|
СИСТЕМЫ ЛИНДЕНМАЙЕРА (L-SYSTEM)
|
|
Понятие Л-систем, тесно связанное с самоподобными фракталами появилось в 1968 году благодаря Аристиду Линденмайеру. Изначально Л-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и ковер Серпинского. Некоторые другие классические построения, например кривые Пеано (работы Пеано, Гильберта, Серпинского) также укладываются в эту схему. И конечно Л-системы открывают путь к бесконечному разнообразию новых фракталов, что и послужило причиной их широкого применения в компьютерной графике для построения фрактальных моделей.
Для графической реализации Л-систем в качестве подсистемы вывода
используется так называемая turtle-графика (черепаший алгоритм).
При этом точка (черепашка) движется по экрану дискретными шагами,
как правило, прочерчивая свой след, но при необходимости может
перемещаться без рисования. В нашем распоряжении имеются три
параметра F - переместиться вперед на один шаг, прорисовывая след; b - не прорисовывая след; [ - открыть ветвь; ] - закрыть ветвь;
+ - увеличить угол
Размер шага и величина приращения по углу Несколько примеров иллюстрируют применение команд ветвления (обозначаются [, ]) и вспомогательных переменных (обозначаются X, Y и т.д.). Команды ветвления используются для построения деревьев и растений, а вспомогательные переменные заметно облегчают построение некоторых Л-систем.
Формально, детерминированная Л-система состоит из алфавита, слова
инициализации, называемого инициатором, и набора порождающих
правил (генератора), указывающих как следует преобразовывать слово
при переходе от уровня к уровню (от итерации к итерации). К
примеру, можно заменять букву F при помощи порождающего правила
newF=F-F++F-F, что соответствует Л-системе для снежинки Коха,
рассматриваемой ниже. Символы
Аксиома: F++F++F, Генератор: newF=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, выглядит следующим образом: Назначение: реализует правила 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, к которой присоединен знак +.
|
|
|
Copyright © 2002-2004
|