Изучение средств и способов создания фрактальных кривых, и их применение на практике

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Фрактальная графика

1.1 История появления фракталов

1.2 Основные свойства фракталов

1.3 Классификация фракталов

1.3.1 Геометрические фракталы

1.3.2 Алгебраические фрактал

1.3.3 Стохастические фракталы

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

1.4.1 Самоподобие

1.4.2 Снежинка Коха

1.4.3 Ковер Серпинского

1.5 L-системы

1.6 Фрактальная графика

1.7 Кривые серпинского

Глава 2. Программирование фрактальных кривых

2.1 Рекурсивные алгоритмы как средство создания фрактальных кривых

2.2 Построение снежинки с помощью фракталов

2.3 Одномерное множество кантора

2.4 Ковёр серпинского

2.5 Треугольник серпинского

Заключение

Список литературы

Введение

Фракталы структура, состоящая из частей, которые в каком-то смысле подобны целому (Бенуа Мандельброт) широко применяются в компьютерной графике для построения изображений природных объектов, таких, как деревья, кусты, горные ландшафты, поверхности морей и т.д.

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

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

Для достижения поставленной цели необходимо реализовать следующие задачи:

1. Освоить историю появления фракталов;

2. Рассмотреть основные свойства фракталов;

3. Разобрать классификацию фракталов;

4. Выявить некоторые виды классических фракталов;

5. Изучить виды фракталов;

6. Разобрать применение фрактальных кривых на практике.

фрактал графика рекурсивный кантор

Глава 1. Фрактальная графика

1.1 История появления фракталов

Фракталы - это геометрические объекты с удивительными свойствами: любая часть фрактала содержит его уменьшенное изображение. То есть, сколько фрактал не увеличивай, из любой его части на вас будет смотреть его уменьшенная копия. Первые идеи фрактальной геометрии возникли в 19 веке. Кантор с помощью простой рекурсивной (повторяющейся) процедуры превратил линию в набор несвязанных точек (так называемая Пыль Кантора Классическое множество Кантора или пыль Кантора, названо по имени Георга Кантора, который описал его в 1883 году. Существование пыли кантора отмечалось до этого Генри Смитом в 1875 году или ещё ранее.). Он брал линию и удалял центральную треть и после этого повторял то же самое с оставшимися отрезками. Пеано нарисовал особый вид линии (рисунок №1). Для ее рисования Пеано использовал следующий алгоритм.

Рис.1. Вид линии

На первом шаге он брал прямую линию и заменял ее на 9 отрезков длиной в 3 раза меньшей, чем длина исходной линии (Часть 1 и 2 рисунка 1). Далее он делал то же самое с каждым отрезком получившейся линии. И так до бесконечности. Ее уникальность в том, что она заполняет всю плоскость. Доказано, что для каждой точки на плоскости можно найти точку, принадлежащую линии Пеано. Кривая Пеано и пыль Кантора выходили за рамки обычных геометрических объектов. Они не имели четкой размерности. Пыль Кантора строилась вроде бы на основании одномерной прямой, но состояла из точек (размерность 0). А кривая Пеано строилась на основании одномерной линии, а в результате получалась плоскость. Во многих других областях науки появлялись задачи, решение которых приводило к странным результатам, на подобие описанных выше (Броуновское движение, цены на акции).

Эти удивительные фигуры стали широко известны в 70-х годах прошлого века благодаря Бенуа Мандельброту французский и американский математик, создатель фрактальной геометрии. Лауреат премии Вольфа по физике (1993)., работавшему тогда математическим аналитиком в фирме IBM. Работая в IBM, он изучал шумы в электронных схемах, которые невозможно было описать с помощью статистики. Постепенно сопоставив факты, он пришел к открытию нового направления в математике - фрактальной геометрии. Он придумал и само слово «фрактал», которое образовано от латинского fractus - «дробный». В математике эти необычные объекты встречались то здесь, то там с конца девятнадцатого века. Но именно Мандельброту удалось собрать эти разрозненные сведения, увидеть общее в многообразии и указать на важность этого открытия.

Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «Фрактальная геометрия природы». Фрактальная геометрия -- это один из разделов теории хаоса. Фрактал (лат. fractus -- дроблёный) -- термин, введённый Бенуа Мандельбротом в 1975 году для обозначения нерегулярных самоподобных множеств. В его работах использованы результаты других учёных, работавших в той же области (Пуанкаре, Жюлиа, Кантор, Хаусдорф).

Фрактал - это бесконечно самоподобная геометрическая фигура, каждый фрагмент которой повторяется при уменьшении масштаба. Масштабная инвариантость, наблюдаемая во фракталах, может быть либо точной, либо приближённой.

Ещё один вариант определения: Фрактал - самоподобное множество нецелой размерности. Самоподобное множество - множество, представимое в виде объединения одинаковых непересекающихся подмножеств подобных исходному множеству

Чтобы представить себе фрактал, рассмотрим пример, приведенный в книге Б.Мандельброта "The Fractal Geometry of Nature" ("Фрактальная геометрия природы"), ставший классическим: "Какова длина берега Британии?". Ответ на этот вопрос не так прост, как кажется. Все зависит от длины инструмента, которым мы будем пользоваться. Померив берег с помощью километровой линейки мы получим какую-то длину. Однако мы пропустим много небольших заливчиков и полуостровков, которые по размеру намного меньше нашей линейки. Уменьшив размер линейки до, скажем, 1 метра - мы учтем эти детали ландшафта, и, соответственно длина берега станет больше. Пойдем дальше и измерим длину берега с помощью миллиметровой линейки, мы тут учтем детали, которые больше миллиметра, длина будет еще больше. В итоге ответ на такой, казалось бы, простой вопрос может поставить в тупик кого угодно - длина берега Британии бесконечна.

1.2 Основные свойства фракталов

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

Свойство 2. Они имеют некоторую форму самоподобия, допуская приближённую.

Свойство 3. Они имеют дробную "фрактальную" размерность, называемую также размерностью Минковского (Для самоподобных множеств, типа канторового множества)

Одно из наиболее мощных приложений фракталов лежит в компьютерной графике. Во-первых, это фрактальное сжатие изображений, и во-вторых, построение ландшафтов, деревьев, растений и генерирование фрактальных текстур.

Достоинства алгоритмов фрактального сжатия изображений - очень маленький размер упакованного файла и малое время восстановления картинки. Фрактально упакованные картинки можно масштабировать без появления пикселизации.

Но процесс сжатия занимает продолжительное время и иногда длится часами. Алгоритм фрактальной упаковки с потерей качества позволяет задать степень сжатия, аналогично формату jpeg. В основе алгоритма лежит поиск больших кусков изображения подобных некоторым маленьким кусочкам. И в выходной файл записывается только - какой кусочек, какому подобен.

При сжатии обычно используют квадратную сетку (кусочки - квадраты), что приводит к небольшой угловатости при восстановлении картинки. Шестиугольная сетка лишена такого недостатка, но немного сложнее программируется. Компанией Iterated разработан новый формат изображений "Sting", сочетающий в себе фрактальное и «волновое» (такое как в формате jpeg) сжатие без потерь. Новый формат позволяет создавать изображения с возможностью последующего высококачественного масштабирования по запросу, причем объем графических файлов составляет 15-20% от объема несжатых изображений.

Склонность фракталов походить на горы, цветы и деревья эксплуатируется некоторыми графическими редакторами, например фрактальные облака из 3D studio MAX, фрактальные горы в World Builder. Фрактальные деревья, горы и целые пейзажи задаются простыми формулами, легко программируются и не распадаются на отдельные треугольники и кубики при приближении.

1.3 Классификация фракталов

Фракталы делятся на группы. Самые большие группы - это геометрические, алгебраические и стохастические.

1.3.1 Геометрические фракталы

Фракталы этого класса самые наглядные. В двухмерном случае их получают с помощью некоторой ломаной (или поверхности в трехмерном случае), называемой генератором. За один шаг алгоритма каждый из отрезков, составляющих ломаную, заменяется на ломаную-генератор, в соответствующем масштабе. В результате бесконечного повторения этой процедуры, получается геометрический фрактал. Построение триадной кривой Кох. один из стандартных примеров, приводимых в подтверждение того, что кривая может иметь фрактальную размерность D > 1 Рассмотрим один из таких фрактальных объектов - триадную кривую Кох. Построение кривой начинается с отрезка единичной длины - это 0-е поколение кривой Кох. Далее каждое звено (в нулевом поколении один отрезок) заменяется на образующий элемент, обозначенный через n=1. В результате такой замены получается следующее поколение кривой Кох. В

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

Итак, для получения каждого последующего поколения, все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. При n стремящемся к бесконечности кривая Кох становится фрактальным обьектом. Для получения "дракона" Хартера-Хейтуэя нужно изменить правила построения. Пусть образующим элементом будут два равных отрезка, соединенных под прямым углом. В нулевом поколении заменим единичный отрезок на этот образующий элемент так, чтобы угол был сверху. Можно сказать, что при такой замене происходит смещение середины звена. При построении следующих поколений выполняется правило: самое первое слева звено заменяется на образующий элемент так, чтобы середина звена смещалась влево от направления движения, а при замене следующих звеньев, направления смещения середин отрезков должны чередоваться.

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

1.3.2 Алгебраические фракталы

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

Если фазовым является двухмерное пространство, то окрашивая области притяжения различными цветами, можно получить цветовой фазовый портрет этой системы (итерационного процесса). Меняя алгоритм выбора цвета, можно получить сложные фрактальные картины с причудливыми многоцветными узорами. Неожиданностью для математиков стала возможность с помощью примитивных алгоритмов порождать очень сложные нетривиальные структуры. В качестве примера рассмотрим множество Мандельброта. Алгоритм его построения достаточно прост и основан на простом итеративном выражении: Z[i+1] = Z[i] * Z[i] + C, где Zi и C - комплексные переменные. Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости. Итерационный процесс продолжается до тех пор, пока Z[i] не выйдет за пределы окружности радиуса 2, центр которой лежит в точке (0,0), (это означает, что аттрактор динамической системы находится в бесконечности), или после достаточно большого числа итераций (например 200-500) Z[i] сойдется к какой-нибудь точке окружности. В зависимости от количества итераций, в течении которых Z[i] оставалась внутри окружности, можно установить цвет точки C (если Z[i] остается внутри окружности в течение достаточно большого количества итераций, итерационный процесс прекращается и эта точка растра окрашивается в черный цвет).

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

1.3.3 Стохастические фракталы

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

Однако существуют и другие классификации: рукотворные и природные.

К рукотворным относятся те фракталы, которые были придуманы учёными, они при любом масштабе обладают фрактальными свойствами. На природные фракталы накладывается ограничение на область существования -- то есть максимальный и минимальный размер, при которых у объекта наблюдаются фрактальные свойства.

В компьютерной графике это используется при создании изображений сложных, похожих на природные, объектов: например, облаков, снега, мусорных куч, береговых линий и др.

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

1.4.1 Самоподобие

Разделим отрезок прямой на N равных частей. Тогда каждую часть можно считать копией всего отрезка, уменьшенного в 1/r раз. Очевидно, N и r связанны отношением Nr = 1. Если квадрат разбить на N равных квадратов (с площадью, в 1/r² раз меньше площади исходного), то соотношение запишется как Nr² = 1. Соответственно, общая формула соотношения запишется в виде:

Nr^d = 1. (1)

Множества, построенные выше, обладают целой размерностью. Зададимся вопросом, возможно ли такое построение, при котором показатель d в равенстве (1) НЕ является целым, то есть такое, что при разбиении исходного множества на N непересекающихся подмножеств, полученных масштабированием оригинала с коэффициентом r, значение d не будет выражаться целым числом. Да может, такое множество называется самоподобным фракталом. Величину d называют фрактальной (дробной) размерностью или размерностью подобия. Явное выражение для d через N и r находится логарифмированием обеих частей (1):

logN

d = --------- (2)

log 1/r

Логарифм можно взять по любому основанию, отличному от единицы, например по основанию 10 или по основанию е ~ 2,7183.

1.4.2 Снежинка Коха

Граница снежинки, придуманной Хельгом фон Кохом (швед. Niels Fabian Helge von Koch, 25 января 1870 -- 11 марта 1924) -- шведский математик в 1904 году (рис.2), описывается кривой, составленной их трех одинаковых фракталов размерности d ~ 1,2618. Каждая треть снежинки строится итеративно, начиная с одной из сторон равностороннего треугольника.

Пусть K_o - начальный отрезок. Уберем среднюю треть и добавим два новых отрезка такой же длины, как показано на рис. 2. Назовем полученное множество K₁ . Повторим данную процедуру многократно, на каждом шаге заменяя среднюю треть двумя новыми отрезками. Обозначим через K_n фигуру, полученную после n-го шага.

Интуитивно ясно, что последовательность кривых K_n при n стремящемся к бесконечности сходится к некоторой предельной кривой К. Рассмотрим некоторые свойства этой кривой.

Если взять копию К, уменьшенную в три раза (r = 1/3), То всё множество К можно составить из N = 4 таких копий. Следовательно, отношение самоподобия (1) выполняется при указанных N и r, а размерность фрактала будет:

d = log(4)/log(3) ~ 1,2618

Рис.2. Снежинка Коха

Еще одно важное свойство, которым обладает граница снежинки Коха --- ее бесконечная длина. Это может показаться удивительным, потому что мы привыкли иметь дело с кривыми из курса математического анализа. Обычно гладкие или хотя бы кусочно-гладкие кривые всегда имеют конечную длину (в чем можно убедиться интегрированием). Мандельброт в этой связи опубликовал ряд увлекательных работ, в которых исследуется вопрос об измерении длины береговой линии Великобритании.

Рис. 3. Построение снежинки Коха.

Размещено на http://www.allbest.ru/

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

1.4.3 Ковер Серпинского

Еще один пример простого самоподобного фрактала - ковер Серпинского (рис.4), придуманный польским математиком Вацлавом Серпинским в 1915 году. Сам термин ковер (gasket) принадлежит Мандельброту. В способе построения, следующем ниже, мы начинаем с некоторой области и последовательно выбрасываем внутренние подобласти. Позднее мы рассмотрим и другие способы, в частности с использованием L-систем, а также на основе итерированных функций.

Рис.4. Ковер Серпинского

Пусть начальное множество S₀ - равносторонний треугольник вместе с областью, которую он замыкает. Разобьем S₀ на четыре меньшие треугольные области, соединив отрезками середины сторон исходного треугольника. Удалим внутренность маленькой центральной треугольной области. Назовем оставшееся множество S₁ (рис.5). Затем повторим процесс для каждого из трех оставшихся маленьких треугольников и получим следующее приближение S₂. Продолжая таким образом, получим последовательность вложенных множеств S_n, чье пересечение образует ковер S.

Из построения видно, что весь ковер представляет собой объединение N = 3 существенно не пересекающихся уменьшенных в два раза копий; коэффициент подобия r = Ѕ (как по горизонтали, так и по вертикали). Следовательно, S - самоподобный фрактал с размерностью:

d = log(3)/log(2) ~ 1,5850.

Рис.5. Построение ковра Серпинского

Очевидно, что суммарная площадь частей, выкинутых при построении, в точности равна площади исходного треугольника. На первом шаге мы выбросили ј часть площади. На следующем шаге мы выбросили три треугольника, причем площадь каждого равна (ј)² площади исходного. Рассуждая таким образом, мы убеждаемся, что полная доля выкинутой площади составила:

1/4 + 3_*(1/4²) + 3²_*(1/4³) + … + 3^n-1_*(1/4ⁿ) + … .

Эта сумма равна 1. Следовательно, мы можем утверждать, что оставшееся множество S, то есть ковер, имеет площадь меры нуль. Это выделяет множество S в разряд «совершенного», в том смысле, что оно разбивает свое дополнение на бесконечное число треугольных областей, обладая при этом нулевой толщиной.

1.5 L-системы

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

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

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

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

[ - открыть ветвь (подробнее см. ниже)

] - закрыть ветвь (подробнее см. ниже)

+ -увеличить угол a на величину q

- - уменьшить угол a на величину q

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

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

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

L-система, соответствующая снежинке Коха (рис.2.), задается следующим образом:

p = /3

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

Порождающее правило: newf = F-F++F-F

Графическое представление аксиомы F++F++F - равносторонний треугольник. Черепашка делает один шаг вперед, затем угол а увеличивается на 2/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-F++F-F++F-F++F-F-F-F++F-F

и т.д. Причем, убедившись на собственном опыте программирования L-систем знаю, что для снежинки Коха на 20-й итерации порождающее правило занимает несколько мегабайт текста!

Вот еще некоторые фракталы, построенные с использованием L-системы:

Рис.6. Дракон Хартера-Хатвея после 12-ти итераций

и его L-система:

p = /4

Аксиома: FX

Порождающее правило: newf = F

newx = X+YF+

newy = -FX-Y

Рис.7. Дерево после 5-ти итераций

и его L-система:

p = /7

Аксиома: F

Порождающее правило: newf = F[+F]F[-F]F

Рис.8. Квадрат Госпера после 2-х итераций

и его L-система:

p = /2

Аксиома: -FX

Порождающее правило: newf = F

newx=+FYFY-FX-FX+FY+FYFX+FY-FXFX-FY-FX+FYFXFX-FY-FXFY+FY+FX-FX-FY+FY+FXFX

newy=FYFY-FX-FX+FY+FY-FX-FXFY+FX+FYFYFX-FY+FX+FYFY+FX-FYFX-FX-FY+FY+FXFX

Построение снежинки Коха, дракона Хартера-Хайвея, деревьев производится с помощью L-систем. L-системы часто называются ещё и системами черепашьей графики.

Черепашья графика - это способ рисования линий на экране компьютера. Он состоит в том, что программист как бы управляет движением черепашки. Черепашка, ползая по экрану, оставляет за собой след. При этом цель программиста - управлять черепашкой так, чтобы черепашка нарисовала нужную линию. Команды управления черепашкой просты: сделать шаг вперёд (обозначается F), повернуть направо (обозначается +), повернуть налево (обозначается - ),сделать шаг вперёд без перерисовки (прыжок, обозначается B). Вот из этих команд и составляется сценарий построения линии - строка команд. Величина одного шага и угол одного поворота при движении черепашки всегда остаются постоянными и задаются предварительно.

Например, F++F++F это равносторонний треугольник, если угол поворота равен pi/3, а F+F+F+F - это квадрат, если угол поворота равен pi/2 .

Построение L-системы происходит в три этапа.

Сначала создаётся сценарий поведения черепашки.

Потом подсчитывается размер линии, которая получится, если запустить этот сценарий на исполнение. Линия как бы рисуется в уме, а потом смотрится её размер. На основе этого размера подправляется масштаб, чтобы вся линия уместилась на экране.

На экран запускается черепашка, которая рисует линию.

Фракталы - самоподобные фигуры, значит, и сценарии у них должны быть самоподобные.

Берётся начальная фигура (называется - аксиома), например, F++F++F с углом pi/3 .

Задаётся правило замены F (называется правило newF) , например, newF = F-F++F-F.

В имеющейся фигуре (в сценарии) все F заменяются на newF. В нашем примере получим:

F-F++F-F++F-F++F-F++ F-F++F-F

Повторяем предыдущий шаг 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

Деревья

У деревьев есть ветки. Тут имеющимся набором команд не обойдёшься. Приходится вводить ещё пару команд: начало ветви (обозначается [ ), конец ветви (обозначается ] ). В начале ветви черепашка должна запомнить своё состояние (положение и направление взгляда), а когда ей встретится соответствующий конец ветви, она должна вернуться в то положение, которое запомнила.

Вот, например, данные для построения куста.

axiom = F

newF = -F+F+[+F-F-]-[-F+F+F]

turn = pi / 8

Для трёх шагов получим такую картинку.

1.6 Фрактальная графика

Cреди всех картинок, которые может создавать компьютер, лишь немногие могут поспорить с фрактальными изображениями, когда идет речь о подлинной красоте. У большинства из нас слово "фрактал" вызывает в памяти цветные завитушки, формирующие сложный, тонкий и составной узор. Но на самом деле этот термин имеет гораздо более широкий смысл. Фрактал - объект, обладающий бесконечной сложностью, позволяющий рассмотреть столько же своих деталей вблизи, как и издалека.

Земля - классический пример фрактального объекта. Из космоса она выглядит как шаp. Если приближаться к ней, мы обнаружим океаны, континенты, побережья и цепи гор. Будем рассматривать горы ближе - станут видны еще более мелкие детали: кусочек земли на поверхности горы в своем масштабе столь же сложный и неровный, как сама гора. И даже еще более сильное увеличение покажет крошечные частички грунта, каждая из которых сама является фрактальным объектом.

Компьютеры дают возможность строить модели таких бесконечно детализированных структур. Есть много методов создания фрактальных изображений на компьютере. Два профессора математики из Технологического института штата Джоржия разработали широко используемый метод, известный как Cистемы Итерируемых Функций (СИФ).

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

Комплексная плоскость - как координатная плоскость с осями x и y. По паре координат точка строится на комплексной плоскости так же, как и точка на плоскости Oxy, но числа имеют другой, необычный смысл: они обладают мнимой компонентой, называемой i, которая равна квадратному корню из -1. ( Вот почему i - мнимая единица - в действительности корень из -1 не существует.) Это искажает обычные правила математики, так что такие общепринятые операции как умножение двух чисел, дают необычные результаты.

Наиболее известный фрактал, множество Мандельброта - фрактал с вpеменным поpогом. Для каждой точки на экране компьютер считает координаты серии точек, определяющих мнимый путь, называемый орбитой. Точки, чьи орбиты никогда не выходят за пределы мнимого цилиндра, расположенного в начале координат комплексной плоскости, считаются элементами множества Мандельброта и обычно закрашиваются черным. Точки, чьи орбиты выходят за пределы цилиндра, раскрашиваются в соответствии с быстротой "убегания": пикселя, чья орбита покидает цилиндр, например, на шестой итерации, можно раскрасить голубым, a тот - орбите которого требуется для этого семь итераций - красным. В результате на изображении получим множество Мандельброта и его окружение с "нестабильными" областями фрактала - областями, для которых малые изменения формулы ведут к большой разнице в орбитальном поведении. Это характеризуется густотой закраски рисунка. Меняя формулу для подсчета орбит, получим другие, такие же экзотические фракталы с вpеменным поpогом. Бесконечно детализированная структура множества Мандельброта становится "ясной", когда вы увеличиваете произвольную область. Неважно, сколь маленький участок вы рассматриваете: рисунок, который вы увидите, будет одинаково сложным. Почему? Потому что в двумерной плоскости, на которой строится множество Мандельброта, любая область содержит бесконечное число точек. Когда вы выбираете область для отображения, компьютер точкам из области ставит в соответствие точки на экране. И каждая точка, выбранная как угодно близко к другой, имеет свою характеристическую орбиту, порождающую соответствующий цветовой узор.

Фракталы - не только предмет математического любопытства, они имеют полезные приложения. Фрактальные пейзажи, например, использовались как декорации в научно-фантастических фильмах, например в "Star Trec,The Wrath of Khan

СИФ-фракталы используются для сжатия изображений, и фрактальный метод часто дает лучшие результаты при многократном сжатии чем JPEG и другие методы сжатия, с малыми потерями качества изображения.

Фракталы с вpеменным поpогом используются для моделирования поведения хаотических динамических систем (систем, в которых небольшие изменения входных данных влекут за собой большие изменения в выходе) таких, как поведение погоды.

1.7 Кривые Серпинского

Алгоритм построения Гильбертовых кривых использует одну процедуру для рисования кривых. Кривые Серпинского проще строить с помощью четырех отдельных процедур, работающих совместно, - SierpA, SierpB, SierpC. и SierpD. Эти процедуры косвенно рекурсивные - каждая из них вызывает другие, которые после этого вызывают первоначальную процедуру. Они выводят верхнюю, левую, нижнюю и правую части кривой Серпинского соответственно.

На рис.9. показано, как эти процедуры образуют кривую глубины 1. Отрезки, составляющие кривую, изображены со стрелками, которые указывают направление их рисования. Сегменты, используемые для соединения частей, представлены пунктирными линиями.

Каждая из четырех основных кривых составлена из линий диагонального сегмента, вертикального или горизонтального и еще одного диагонального сегмента.

При глубине рекурсии больше 1 необходимо разложить каждую кривую на меньшие части. Это можно сделать, разбивая каждую из двух линий диагональных сегментов на две подкривые.

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

А. И наконец, второй диагональный отрезок разбивается на кривую типа D, за которой следует кривая типа А. На рис.10. изображен процесс построения кривой 2-го порядка, сформированной из кривых 1-го порядка. Подкривые показанны жирными линиями.

На рис.11. показано, как из четырех кривых 1-го порядка формируется полная кривая Серпинского 2-го порядка. Каждая из подкривых обведена пунктирными линиями.

Рис.9. Части кривой Серпинского. Рис.10. Составление кривой типа А из меньших частей

Рис.11. Кривая Серпинского, образованная из меньших кривых

С помощью стрелок типа --» и <--, отображающих типы линий, которые соединяют части кривых между собой (тонкие линии на рис.11.), можно перечислить рекурсивные зависимости между четырьмя типами кривых, как показано на рис.12.

Все процедуры для построения подкривых Серпинского очень похожи друг на друга, поэтому здесь приведена только одна из них. Зависимости, показанные на рис.12, показывают, какие операции нужно выполнить, чтобы нарисовать кривые различных типов. Соотношени для кривой типа А реализованы в следующем коде. Остальные зависимости можно использовать, чтобы изменить код для вывода других типов кривых.

Рис.12. Рекурсивные зависимости между кривыми Серпинского

A: B < D

А A

В: В С А В

С: С С

D > B

D: D A C D

Глава 2. Программирование фрактальных кривых

2.1 Рекурсивные алгоритмы как средство создания фрактальных кривых

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

Рис.1. Окружность с четырьмя окружностями поменьше

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

Для того, чтобы составить программу построения этого изображения, можно:

• описать процедуру изображения одной окружности с четырьмя окружностями поменьше;

• для изображения каждой окружности следующего уровня использовать эту же процедуру, только с другими значениями параметров -- координат центров, величин радиусов и т. д.

Опишем алгоритм рисования окружности радиуса r с центром в точке (x,y) с четырьмя окружностями вокруг. При этом необходимо знать расстояния (r1) от точки (х,у) до центров окружностей окружения (радиусы орбиты), которые, очевидно, равны. Пусть , где -- радиус окружности окружения,

Procedure Picturel(x,у,r,rl:Integer);

Begin

{изобразить окружность с центром (х,у) и радиусом r} ;

{вычислить r1};

For i:=l То 4 Do

Begin {вычислить координаты центра (х1,у1) i-й окружности};

Picturel(х1,у1,<новое значение r>, r1);

End;

End.

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

Как вычислить значения х1, у1? Они зависят от х и следующим образом: х1=х + dx,

y1= у + dy.

Необходимо выразить значения приращений координат dx, dy. Воспользуемся определениями тригонометрических функций sin и cos:

dx= r1- cos(б)

dy = r1- sin(б), где б = р/2, р, Зр/2, 2р.

Если осуществить вызов этой же процедуры из основной программы с начальными параметрами, то рекурсивные вызовы никогда не закончатся, и программа будет работать бесконечно. Для того, чтобы этого не случилось, можно ввести в качестве аргумента процедуры некоторую величину и, которая при каждом новом вызове процедуры будет уменьшаться на 1, а в тело процедуры включить условие, что его операторы должны выполняться только при n> 0, то есть это условие будет играть роль своеобразной «заглушки», ограничивающей число вызовов процедуры.

Ниже приведена программа, полностью решающая поставленную задачу.

В основной программе запрашиваются радиус r самой большой окружности и число уровней n, а также задаются значения коэффициентов к1 и к2. Центр самой большой окружности располагается в центре экрана.

Program primer1;

Uses Graph;

Var x, у, n,r,rl,cd,gm:Integer;

kl,k2:Real;

Procedure Picture2(x,y,r,rl,n:Integer);

Var xl, yl:Integer;

i:Integer;

Begin

If n>0 Then {"заглушка"}

Begin

circle(x,y,r);{рисование окружности}

rl:=trunc(r*к2); {вычисление радиуса орбиты}

For i:=l To 4 Do Begin

xl:=trunc (x+rl*cos (pi/2*i)); yl:=trunc(y+rl*sin(pi/2*i)); {координаты центра i-й окружности} picture2(xl,yl,trunc(r*kl),rl,n-1);

{вызов процедуры с новыми параметрами}

End;

End;

End:

Begin {задание начальных значений}

Writeln('Введите число уровней n.');

Readln(n); х:=600 Div 2; у:=400 Div 2;

Writeln('Введите радиус первой окружности r');

Readln(r);

kl:=0.3;

к2:=2;

cd:=detect;

gm:=l; {инициализация графики}

initgraph(cd, gm, 'c:\tp7_0\bin'); picture2(x,у,г,rl,n) ; Readln;

closegraph;

End.

Примечания:

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

Изменяя в процессе демонстрации работы программы значения к\, к2, п, можно получать множество привлекательных рисунков.

2.2 Построение снежинки

На рисунке ниже изображена снежинка, состоящая из трех звеньев и восьми ветвей.

Сделаем расчет длины каждого звена по известному значению п -- количеству звеньев и величине экрана. Будем считать, что снежинка строится в квадрате 400 х 400 точек. Центр снежинки совпадает с центром квадрата, а длина отрезка каждого очередного звена в четыре раза меньше предыдущего.

Если через l обозначить длину первого звена, то справедливо следующее равенство:

l + + =200

Пусть снежинка состоит из одного звена и р ветвей, тогда соответствующая программа проста. Основная ее часть имеет вид

For i:=l То р Do

Begin

х1:=trunc (x+l*cos(2*pi*(i-1)/р));

yl:=trunc(y+l*sin(2*pi*(i-1)/p)); {координаты конца очередного звена}

line(х,у,xl,yl); {рисование звена}

End;

Здесь x,y -- координаты точки центра снежинки. Наща снежинка рисуется как бы много раз, при этом длины звеньев изменяются, поэтому их надо просчитать один раз и запомнить в массиве L из n элементов. Длина каждого звена уменьшается в четыре раза по отношению к предыдущему. Длина первого звена определяется из того, что в квадрате из 400 х 400 точек необходимо построить снежинку из п звеньев. Если мы дошли до этапа рисования самого маленького звена (самой маленькой снежинки), то наша программа должна работать как приведенный набросок.

Итак, логика решения задачи.

Начинаем рисовать из центра, точки А, нарисовали первый отрезок АВ , если это не последнее звено, то будем рисовать отрезок следующего звена ВС, звено не последнее, поэтому продолжим. Предположим, что нарисовали СЕ, это первая ветвь самой маленькой снежинки, наша программа должна работать как набросок, то есть рисовать все ветви этой снежинки. После этого мы должны вернуться в точку В.

Так как это не последняя ветвь этой снежинки, то мы снова должны нарисовать следующую ветвь -- отрезок BD, а затем снова полностью самую маленькую снежинку. Что необходимо для реализации этой логики? Пусть значение переменной к будет равно текущему номеру звена снежинки, в начальный момент оно равно п. Тогда при переходе от точек С, D к точке В мы должны «вспомнить» координаты точки В и номер ветви снежинки, рисуемой из точки В. При переходе от точки В к точке А мы должны «вспомнить» координаты точки А и номер ветви снежинки, рисуемой из точки А. Эта логика легко реализуется с помощью рекурсии.

Примечание. Для вычисления значения показательной функции а" используется тождество а"=

Program primer2;

Uses Graph;

Const p=8; n=4;

Var X, y, i,cd, gm: Integer;

L: Array[l..n] Of Integer;

Procedure Pictures (x, y, k: Integer);

Var xl, yl: Integer;

i: Integer;

Begin

If k>0 Then {«заглушка»}

Begin

For i:=l To p Do

Begin {координаты конца очередного звена}

xl:=trunc(x+L[k]*cos(2*pi*(i-1) /p) ) ; yl:=trunc(y+L[k]*sin (2*pi*(i-1)/p)); line(x,y,xl,yl); {рисование звена} pictures (xl,yl,k-1);

End;

End;

End;

Begin

L[n]:= trunc (200*3*exp ( (n-1)*ln (4))/(exp(n*ln(4))-l)); {***}

For i:=2 To n Do L[n-i+1]:=trunc(L[n]/exp((i-1)*ln (4)));

x:=300; y:=200; {координаты центра снежинки}

cd:=detect;

gm:=l; {инициализация графики}

Initgraph(cd,gm,'с:\tp7_0\bin');

Pictures (x, y, n) ;

Readln; {задержка на экране}

Closegraph;

End.

2.3 Одномерное множество Кантора

Георг Кантор (1845-1918) явился одним из основателей теории множеств. Он также придумал один из старейших фракталов - множество Кантора (описано им в 1883). На Западе подобные множества называют иногда пылью. Заметим, что существование этого фрактала отмечалось до этого Генри Смитом в 1875 году или еще ранее. Это множество хорошо известно как пример множества нулевой меры Лебега, чья мощность равна мощности континуума. Фрактальные свойства пыли Кантора имеют огромное значение, особенно учитывая тот факт, что многие известные фракталы являются близкими родственниками этого фрактала.

Способ построения этого множества следующий. Берётся отрезок прямой единичной длины. Затем он делится на три равные части, и вынимается средний отрезок. Это первый шаг итерационной процедуры. На втором шаге подобной процедуре деления на три равные части и последующего удаления середины подвергается каждый из двух оставшихся отрезков. Так продолжая до бесконечности, получим множество Кантора. Нетрудно заметить, что суммарная длина получившихся в пределе отрезков равна нулю, так как мы исключили в результате длину, равную 1:

program primer3;

uses CRT, Graph;

const min = 1;

var gd, gm : Integer;

procedure Draw(x, y : Real; Size : Real);

var s : Real;

begin

if size > min then

begin

s := size / 3;

Draw(x, y + 20, s);

Draw(x + s * 2, y + 20, s);

end;

Bar(Round(x), Round(y), Round(x + size), Round(y + 5));

end;

begin

gd := Detect;

InitGraph(gd,gm,'');

Draw(10,30,500);

ReadKey;

CloseGraph;

end.

2.4 Ковёр Серпинского

Строится ковер Серпинского следующим образом. Вначале берётся квадрат со стороной равной единице, затем каждая сторона квадрата делится на три равные части, а весь квадрат, соответственно, на девять одинаковых квадратиков со стороной равной . Из полученной фигуры вырезается центральный квадрат. Затем такой же процедуре подвергается каждый из 8 оставшихся квадратиков и т. д.



program primer4;

uses CRT, Graph;

var gd, gm: Integer;

x1, y1, x2, y2, x3, y3: Real;

procedurue Serp(x1, y1, x2, y2: Real; n: Integer);

var x1n, y1n, x2n, y2n: Real;

begin

if n > 0 then

begin

x1n := 2*x1/3 + x2 / 3;

x2n := x1/3 + 2*x2 / 3;

y1n := 2*y1/3 + y2 / 3;

y2n := y1/3+2*y2 / 3;

Rectangle(Round(x1n), Round(y1n), Round(x2n), Round(y2n));

Serp(x1, y1, x1n, y1n, n-1);

Serp(x1n, y1, x2n, y1n, n-1);

Serp(x2n, y1, x2, y1n, n-1);

Serp(x1, y1n, x1n, y2n, n-1);

Serp(x2n, y1n, x2, y2n, n-1);

Serp(x1, y2n, x1n, y2, n-1);

Serp(x1n, y2n, x2n, y2, n-1);

Serp(x2n, y2n, x2, y2, n-1)

end

end;

begin

gd := Detect;

InitGraph(gd, gm, 'c:\bp\bgi');

Rectangle(20, 20, 460, 460);

Serp(20, 20, 460, 460, 4);

ReadLn;

CloseGraph;

end.

2.5 Треугольник Серпинского

В 1915 году польский математик Вацлав Серпинский придумал занимательный объект, известный как решето Серпинского. Этот треугольник один из самых ранних известных примеров фракталов. Существует несколько способов построения этого фрактала. Один из них представляет следующий процесс. Берётся сплошной равносторонний треугольник, на первом шаге из центра удаляется перевёрнутый треугольник. На втором шаге удаляется три перевёрнутых треугольника из трёх оставшихся треугольников. Продолжая этот процесс, на -ом шаге удаляем перевёрнутых треугольников из центров оставшихся треугольников. Конца этому процессу не будет, и в треугольнике не останется живого места, но и на части он не распадётся - получится объект состоящий из одних только дырок. Это и есть треугольник Серпинского. Треугольник Серпинского также называют салфеткой Серпинского.

program primer5;

uses CRT, Graph;

var gd, gm : Integer;

const iter = 5;

procedure tr(x1, y1, x2, y2, x3, y3: Real);

begin

Line(Round(x1), Round(y1), Round(x2), Round(y2));

Line(Round(x2), Round(y2), Round(x3), Round(y3));

Line(Round(x3), Round(y3), Round(x1), Round(y1));

end;

procedure draw(x1, y1, x2, y2, x3, y3: Real; n: Integer);

var

x1n, y1n, x2n, y2n, x3n, y3n : Real;

begin

if n > 0 then

begin

x1n := (x1 + x2) / 2;

y1n := (y1 + y2) / 2;

x2n := (x2 + x3) / 2;

y2n := (y2 + y3) / 2;

x3n := (x3 + x1) / 2;

y3n := (y3 + y1) / 2;

tr(x1n, y1n, x2n, y2n, x3n, y3n);

draw(x1, y1, x1n, y1n, x3n, y3n, n - 1);

draw(x2, y2, x1n, y1n, x2n, y2n, n - 1);

draw(x3, y3, x2n, y2n, x3n, y3n, n - 1);

end;

end;

begin

gd := Detect;

InitGraph(gd, gm, '');

tr(320,10,600,470,40,470);

draw(320,10,600,470,40,470,iter);{}

ReadKey;

CloseGraph;

End.

Заключение

В данной работе мы изучили средства и способы создания фрактальных кривых, их применение на практике. Рассмотрели свойства, классификацию фракталов, некоторые виды и примеры фрактальных кривых.

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

1. Сжатие изображений и информации;

2. Сокрытие информации на изображении, в звуке и т.д.;

3. Шифрование данных с помощью фрактальных алгоритмов;

4. Создание фрактальной музыки;

5. Моделирование систем и т.д.

Список литературы

1. А.В. Могилев, Н.И. Пак, Е.К.Хеннер. Практикум по информатике. Москва, 2008. - 607с.

2. А.В. Могилев, Н.И. Пак, Е.К.Хеннер. Информатика. Москва, 2009. - 687с.

3. Ричард М. Кроновер.- Фракталы и хаос в динамических системах. Основы теории. Москва: Постмаркет, 2010. - 352 с.

4. А.Д. Морозов, Т.Н. Драгунов. - Визуализация и анализ инвариантных множеств динамических систем. - Москва-Ижевск, 2007. - 305с.

5. А.Д. Морозов, Введение в теорию фракталов. - Москва-Ижевск: Институт компьютерных исследований, 2009. - 160 с.

6. Ногих С.Р., Дурнин М.К., Шестопалов А.В. Процессовые фракталы и фрактально подобные процессы / Моделирование процессов в синергетических системах. / Международная конференция "Байкальские чтения II по моделированию процессов в синергетических системах" (18-23 июля 2002, ИВТ, Максимиха - восточное побережье озера Байкал). - Улан-Удэ - Томск: Изд-во ТГУ, 2007. - с.277-279.

7. Уэлстид, С. Фракталы и вейвлеты для сжатия изображений в действии: Учебное пособ. - М.: Издательство «Триумф», 2008. - 320 с.: ил.