L-системы тертл-графики

Классические фракталы

 

Примерами классических фракталов являются снежинка Коха, ковер Серпинского, губка Менгера, пыль Кантора и множество других.

Снежинка Коха представляет собой замкнутую кривую, составленную из трех одинаковых фракталов, каждый из которых строится на стороне равностороннего треугольника. Процедуру построения рассмотрим на примере одной из сторон треугольника. Она выполняется для каждой из сторон.

Пусть – исходный отрезок (одна сторона треугольника). Разделим его на 3 части и уберем среднюю часть. Вместо средней части добавим два новых отрезка той же длины так, чтобы в центре отрезка образовался новый (маленький) равносторонний треугольник, но без основания. В результате получим новое множество (см. рис. 2.4). Данную процедуру можно выполнять многократно над каждым из отрезков, получая все новые и новые множества ,и т.д. В результате на п-м шаге итерационного процесса получим снежинку Кох (рис. 2.5).

Рисунок 2.4 – Построение снежинки Кох:

 

Рисунок 2.5 – Снежинка Кох

Поскольку N = 4, а , то размерность фрактала:

 

.

 

Особенностью данного фрактала является бесконечная длина предельной кривой, описывающей его границу. Действительно, длина кривой , длина кривой , на –ом шаге итерационного процесса длина кривой . При длина предельной кривой для одной стороны фрактала .

Алгоритмы построения таких фракталов, как ковер Серпинского, пыль Кантора и других, во многом сходны с алгоритмом построения снежинки Коха.

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

 

 

Рисунок 2.6 – Ковер Серпинского

 

Пусть исходным множеством S_o является равносторонний треугольник вместе с областью, которую он замыкает. Разобьем его на четыре меньших треугольника и удалим внутренний треугольник без замыкающих его сторон. Получим множество . Выполним аналогичную операцию над оставшимися треугольниками. В результате будет иметь место множество . Продолжая итерационный процесс, на -м шаге получим множество (рис. 2.7). Предельное множество и образует ковер Серпинского. Так как коэффициент подобия , а количество элементов, участвующих в итерационном процессе, N = 3, то размерность фрактала (ковра), построенного на основе треугольника, равна:

.

 

Рисунок 2.7 – Построение ковра Серпинского

Так же как и снежинка, данный ковер имеет свою особенность, а именно то, что предельное множество S имеет площадь нулевой меры.

Действительно, на первом шаге удаляется 1/4 площади треугольника, на втором шаге 3 треугольника площадью l/4² от исходного и т.д.

Поскольку площадь в пределе равна

 

,

 

то мера равна нулю.

К множествам нулевой меры относится и пыль Кантора (фрактальная пыль). Принцип построения этого множества состоит в следующем. На первом шаге отрезок единичной длины [0,1] разбивается на три части и удаляется средний, открытый интервал. На последующих шагах вновь удаляются центральные части оставшихся отрезков, не включая их концы (рис. 2.8). Предельным множеством является пыль Кантора.

 

Рисунок 2.8 – Построение пыли Кантора

Так как N = 2, а коэффициент подобия , то размерность фрактала равна:

 

Подсчитаем длину выбрасываемых интервалов. На первом шаге выбрасывается интервал длиной 1/3. На втором шаге выбрасываются два интервала длиной 1/3² с длины исходного единичного отрезка. На п-м шаге выбрасываются интервалов каждый длиной . Таким образом, общая длина выбрасываемых интервалов для предельного множества составит:

 

.

 

 

Для рассмотренных выше классических фракталов характерен единый принцип построения – добавляются либо выбрасываются отдельные линии или области. Процесс повторяется многократно (итерационно). Этот процесс лег в основу L-систем, позволяющих создавать отдельную, достаточную большую группу самоподобных фракталов. С помощью L-систем, использующих подсистему графического вывода под названием тертл-графика (от английского turtle – черепаха), обычно строят связанные и несвязанные фрактальные множества – снежинки, ковры, кривые, а также фрактальные деревья, растения, русла рек и т д.

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

Изображающая точка движется по командам, задаваемым кодовыми словами. В каждой точке экрана положение изображающей точки задается тремя параметрами х, у, (х,у – координаты точки; – направление движения). Кодовое слово состоит из указаний перемещения на один шаг с оставлением или неоставлением следа, увеличением или уменьшением направления движения на некоторый угол , открытием ветви, закрытием ветви.

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

Алфавит состоит из набора отдельных символов. Каждый символ представляет собой микрокоманду, предписывающую определенное действие, выполняемое изображающей точкой.

Например:

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

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

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

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

+ – увеличить угол на величину ;

– – уменьшить угол на величину .

Из элементов алфавита можно создавать слова инициализации (аксиомы). Например, L -система, позволяющая нарисовать на экране равносторонний треугольник, следующая:

,

 

аксиома: F + +F + +F.

Изображающая точка имеет первоначальное направление движения под углом . Согласно команде выполняется движение на один шаг. По команде + и + осуществляется поворот на угол . Следующая команда F предписывает движение еще на один шаг. Команды + и + поворачивают изображающую точку вновь в положительном направлении на угол . Окончательная команда F замыкает треугольник.

Порождающее правило предназначено для замены микрокоманды в аксиоме группой микрокоманд. Например, если в приведенной выше аксиоме команду F заменить порождающим правилом , то изображающая точка при движении по экрану нарисует снежинку Кох. Порождающее правило – это разновидность рекурсивной процедуры. Глубина рекурсии показывает, какое количество итераций по замене микрокоманд группой микрокоманд необходимо выполнить.

С помощью микрокоманды ветвления осуществляется построение деревьев и растений. Порождающие правила позволяют многократно выполнять ветвления не только от линии основного направления движения изображающей точки, но и от построенных ранее ветвей. На рисунках 2.13–2.14 изображены фракталы, построенные с помощью микрокоманды ветвления.

Рисунок 2.13 – Куст после 4-х итераций

 

Рисунок 2.14 – Цветок после 3-х итераций