Фрактал прямая делится на 3 части. Построение триадной кривой Коха

Фрактал прямая делится на 3 части. Построение триадной кривой Коха

Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Слово фрактал образовано от латинского fractus и в переводе означает состоящий из фрагментов. Оно было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта `The Fractal Geometry of Nature’. В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему.

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

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

Определение фрактала, данное Мандельбротом, звучит так: «Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому» [3].

Для чтобы представить все многообразие фракталов удобно прибегнуть к их общепринятой классификации [2].

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

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


Рис 1. Построение триадной кривой Кох.

Рассмотрим один из таких фрактальных объектов — триадную кривую Кох [3]. Построение кривой начинается с отрезка единичной длины (рис.1) — это 0-е поколение кривой Кох. Далее каждое звено (в нулевом поколении один отрезок) заменяется на образующий элемент, обозначенный на рис.1 через n=1. В результате такой замены получается следующее поколение кривой Кох. В 1-ом поколении — это кривая из четырех прямолинейных звеньев, каждое длиной по 1/3. Для получения 3-го поколения проделываются те же действия — каждое звено заменяется на уменьшенный образующий элемент. Итак, для получения каждого последующего поколения, все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. На рис.1 представлены пять поколений кривой. При n стремящемся к бесконечности кривая Кох становится фрактальным обьектом [3].


Рис 2. Построение «дракона» Хартера-Хейтуэя.

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

В машинной графике использование геометрических фракталов необходимо при получении изображений деревьев, кустов, береговой линии. Двухмерные геометрические фракталы используются для создания объемных текстур (рисунка на поверхности обьекта) [2,3].

Читать еще:  Дополнительные расы для скайрим мод сборка. Другие новые расы

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

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

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


Рис 3. Множество Мандельброта.

В качестве примера рассмотрим множество Мандельброта (см. pис.3 и рис.4). Алгоритм его построения достаточно прост и основан на простом итеративном выражении:

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


Рис 4. Участок границы множества Мандельброта, увеличенный в 200 pаз.

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

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

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

Существуют и другие классификации фракталов, например деление фракталов на детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).

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

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

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

Читать еще:  Самые красивые еврейки и иудейки всех времен. Евреи: характерные черты

Рис. 1.6. Построение триадной кривой Коха

Три копии кривой Коха, построенные (остриями наружу) на сторонах правильного треугольника, образуют замкнутую кривую, называемую снежинкой Коха.

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

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

L-система определяется как кортеж G=(V, w, P), где V – алфавит, представляющий набор символов, содержащих элементы которые могут быть представлены графически, w – аксиома, которая представляет собой строку символов из V, определяющая начальное состояния системы, P — представляет собой набор правил производства новой строки, путем замены символов текущего состояния системы на ряд новых. Правила грамматики L-системы применяются итеративно, начиная с начального состояния.

Рассмотрим L-систему, где алфавит состоит всего из двух символов V=<a,b>. Аксиома w=a. Правила производства описываются как p1: aab, p2: bab. Следуя итеративному принципу, каждое поколение кривой удваивается на каждом этапе: a, ab, abab, abababab. Графически a и b отображаются как два равных отрезка, соединенных под прямым углом (рис. 1.7).

Рис. 1.7. Графическое представление алфавита L-системы

Графическое представление правил p1 и p2, приведено на рис. 1.8. Таким образом, правила описывают замену каждого из отрезков двумя другими, соединенных под прямым углом. При этом, каждый раз, меняется угол поворота новых отрезков относительно исходного.

Рис. 1.8. Графическое представление правил L-системы

На рис. 1.9 изображены пять первых итераций процесса построения фрактала.

Рис. 1.9. Первые итерации построения фрактальной кривой

Такая предельная фрактальная кривая (при числе итераций стремящимся к бесконечности) называется драконом Хартера-Хейтуэя и представлена на рис. 1.10.

Рис. 1.10. Дракон Хартера-Хейтуэя

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

Равносторонний треугольник M делится прямыми, параллельными его сторонам, на 4 равных равносторонних треугольника. Из треугольника удаляется центральный треугольник. Получается множество M1, состоящее из 3 оставшихся треугольников «первого ранга». Поступая точно так же с каждым из треугольников первого ранга, получим множество M2, состоящее из 9 равносторонних треугольников второго ранга. Продолжая этот процесс бесконечно, получим бесконечную последовательность M, M1,…, Mn,…пересечение членов которой есть треугольник Серпинского (рис. 1.11).

Вопрос 19 Геометрические фракталы: триадная кривая Кох.

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

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

Геометрические фракталы: салфетка Серпинского.

Рассмотрим самоподобную фигуру, придуманную польским математиком В.Серпинским (1882–1969).

Она получается из квадрата последовательным вырезанием серединных квадратов. Проследим построения нового квартала более подробно. Разделим данный квадрат на девять равных квадратов и квадрат, расположенный в середине, вырежем. Получим квадрат с пустотой (рис. 10а). Для оставшихся восьми квадратов вновь повторим указанную процедуру. Разделим каждый из них на девять равных квадратов и серединные квадраты удалим (рис. 10б). Повторяя похожие построения, будем получать все более “дырявую” фигуру (рис. 10в). То, что остается после всех вырезаний, и будет ковром Серпинского.

Читать еще:  Что означает писать во сне на бумаге. Мочиться толкование сонника

Поскольку вырезаемые квадраты располагаются все более часто, то в результате на ковре (салфетке) Серпинского не будет ни одного, даже самого маленького, квадрата без «дырки».

Начиная не с квадрата, а с равностороннего треугольника, и вырезая центральные треугольники, получим еще одну самоподобную фигуру, аналогичную ковру Серпинского. Она носит название «салфетки Серпинского» (рис. 11).

Фрактал Кантора.

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

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

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

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

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

Непосредственно с множеством Кантора связана чёртова лестница.

Фрактальная размерность. Примеры вычисления размерности фракталов.

Фрактал – множество с дробной размерностью.

Фрактал – множество, размерность Хайсдорфа-Безиковича которого строго больше топологической размерности.

1) Евклидова: минимальное число координат, необходимых для однозначного определения положения точки;

2) Тополог.: размерность любого множества на 1 больше размерности разреза, делящего его на две несвязнае части (тополог.размерность отрезка-1, топол.разм. квадрата-2, плоскости-2);

3) Размерность самоподобия . Размерность самоподобия – один из частных случаев фрактальной размерности.

Размерность Хаусдорфа — естественный способ определить размерность подмножества в метрическом пространстве.

Размерность Хаусдорфа согласуется с нашими обычными представлениями о размерности в тех случаях, когда эти обычные представления есть. Например, в трёхмерном евклидовом пространстве хаусдорфова размерность конечного множества равна нулю, размерность гладкой кривой — единице, размерность гладкой поверхности — двум и размерность множества ненулевого объёма — трём. Для более сложных (фрактальных) множеств размерность Хаусдорфа может не быть целым числом.

Источники:

http://algolist.manual.ru/graphics/fracart.php

http://megaobuchalka.ru/2/11763.html

http://cyberpedia.su/16xb290.html

Ссылка на основную публикацию
Статьи на тему:

Adblock
detector