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

Введение

фрактал математика геометрический программирование

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

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

Фракталы - подходящее средство для исследования поставленных вопросов. Термин фрактал относится к некоторой статичной геометрической конфигурации, такой как мгновенный снимок водопада.

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

Изучение фракталов открывает замечательные возможности, как в исследовании бесконечного числа приложений, так и в области математики. Но в то же время, как это часто случается в математике, открытия опираются на работы великих математиков прошлого. Сэр Исаак Ньютон понимал это, говоря: «Если я и видел дальше других, то только потому, что стоял на плечах гигантов».

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

Объектом для данной работы будет являться геометрический фрактал, а предметом - моделирование геометрическим фракталом на языке программирования Pascal.

Цель работы - реализация геометрических фракталов в среде программирования Pascal.

Задачи:

· провести научно-теоретический анализ литературы по теме работы;

· выделить классы фракталов;

· разработать программы реализации в среде программирования Pascal.

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

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

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

Рис.1. Кривая Пеано

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

Эти удивительные фигуры стали широко известны в 70-х годах прошлого века благодаря Бенуа Мандельброту, работавшему тогда математическим аналитиком в фирме IBM. Работая в IBM, он изучал шумы в электронных схемах, которые невозможно было описать с помощью статистики. Постепенно сопоставив факты, он пришел к открытию нового направления в математике - фрактальной геометрии.

Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «Фрактальная геометрия природы». Фрактальная геометрия -- это один из разделов теории хаоса. Фрактал (лат. Fractus -- дроблёный) -- термин, введённый Бенуа Мандельбротом в 1975 году для обозначения нерегулярных самоподобных множеств. Мандельброт решил, что для обозначения размерностей, образов и геометрии, ими созданных, нужно имя. Он перелистал словарь латинского языка, принадлежащий его сыну, и нашел в нем слово fractus, являвшееся прилагательным, полученным от глагола frangere, что значит ломать. Мандельброт счел подходящим созвучие найденного слова с однокоренными словами английского языка fraction и fracture. Так появилось слово «фрактал». Бенуа Мандельброт не сформулировал окончательно определение фрактала, считая, что понятие должно получить определенную выдержку. Мандельброт пояснял, что исследованные и названные им фракталами фигуры имели свойство нерегулярности притом, что они являлись самоподобными. «Подобный» в классическом представлении значит уменьшенный или увеличенный, при этом согласуется с таким широким понятием, как «похожий». Такое толкование дало возможность отнести к фракталам такие математические множества, как известные множества Коха, Жюлиа, Пеано, Кантора, Серпинского и другие. Такие конструкции были интуитивно противоречивыми, их принимали за досадные, непохожие на других исключения. Математики при встрече с ними предпочитали закрывать глаза, так как евклидова геометрия не в силах была справиться с этими нерегулярными, почти хаотичными монстрами. Хаотичность в границах самоподобия и была тем, что выражалось в понятии, введенном Мандельбротом. Он писал, что атакуя новую область, хотел провести деление на части такого понятия, как хаос. Одна из частей осталась неисследованной, так как неизвестно, как ее можно исследовать. Другая же часть, достаточно внушительная, должна быть выделена и изучена, т.к. поддается вполне изучению из-за обладания свойством самоподобия. Лишь после того, как в 1982 году была опубликована новая научная работа Мандельброта, эссе «Фрактальная геометрия природы», ученые, наконец, признали рождение новой науки. Фрактальная геометрия начала бурно развиваться. Фракталы были найдены буквально во всех природных явлениях и естественных процессах. В настоящий момент анализ, основанный на фрактальных множествах, имеет такое же развитие, как и анализ, в основе которого лежат гладкие многообразия. Идеи новой науки нашли применение в самых разных областях. Фрактальные модели используют в медицине, диагностируя на ранней стадии раковые опухоли, в почвоведении, в геологии. С их помощью изучают процессы разрушения различных материалов, элементарные частицы в ядерной физике, галактические распределения и солнечные процессы в астрономии, информационные сжатия и оптимизация интернет-трафика в информатике. Фракталы используются в экономике для анализа ценовых колебаний, в кардиологии -- для анализа сердечных ритмов, в метеорологии -- для анализа изменений погоды и т.д. И все это благодаря разработкам Бенуа Мандельброта.

Вспоминая о том, как создавалась фрактальная геометрия, Бенуа Мандельброт отметил 3 периода. Первый период, 1952-1964 годы, когда ученый буквально на ощупь искал, а затем вынашивал идею. Второй период, 1965-1975 годы, Мандельброт считает очень интересным во многом, но самым разочаровывающим в личном плане. Тогда прошла целая серия манифестов по поводу фракталов, включая участие и выступление на конгрессе, проходившем в Иерусалиме, лекции в Колледже Франс в Париже и в Йельском университете. Мандельброт пытался тогда, по его словам, дать формулировку широкому замыслу, который не делает различия между науками естественными и социальными. К несчастью, тогда он не смог добиться от других ученых понимания его идей, что стало причиной отчуждения. Третий свой период Мандельброт называет временем, когда идеи консолидировались, бурно расширялись и развивались, успешно объединяя аспекты философского и технического характера.

1.2 Классификация, виды фракталов

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

Геометрические фракталы. Именно с них и начиналась история фракталов. Этот тип фракталов получается путем простых геометрических построений. Обычно при построении этих фракталов поступают так: берется "затравка" -- аксиома -- набор отрезков, на основании которых будет строиться фрактал. Далее к этой "затравке" применяют набор правил, который преобразует ее в какую-либо геометрическую фигуру. Далее к каждой части этой фигуры применяют опять тот же набор правил. С каждым шагом фигура будет становиться все сложнее и сложнее, и если мы проведем бесконечное количество преобразований -- получим геометрический фрактал.

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

Zn+1=f(Zn),

где Z - комплексное число, а f некая функция. Расчет данной функции продолжается до выполнения определенного условия. И когда это условие выполнится -- на экран выводится точка.

Системы итерируемых функций. Два профессора математики из Технологического института штата Джорджия в середине 80-х годов разработали широко используемый метод, известный как Системы Итерируемых Функций (“Iterated Functions System” - IFS). С помощью этого метода создаются реалистичные изображения природных объектов, таких, например, как листья папоротника, деревья, при этом неоднократно применяются преобразования, которые двигают, изменяют в размере и вращают части изображения. В IFS используется самоподобие, которое есть у творений природы, и объект моделируется как композиция множества мельчайших копий самого себя.

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

Рассмотрим более подробно виды геометрических фракталов.

1.2.1 Триадная кривая Коха

В 1904 году математик Коха дал пример кривой, которая нигде не имеет касательной. Кривая, состоящая из частей, каждая из которых бесконечной длины. Кривые Коха демонстрируют новое и весьма интересное сочетание простоты и сложности. На первый взгляд они выглядят гораздо более сложными, чем любая стандартная евклидова кривая. Однако теория математических алгоритмов Колмогорова-Чайтина утверждает обратное: кривая Коха ничуть не сложнее окружности! Эта теория оперирует некоторым набором «букв» или «атомных операций», причем длина кратчайшего известного алгоритма построения искомой функции принимается за объективный верхний предел сложности этой функции.

Условимся изображать буквы или «атомы» графического процесса прямыми «штрихами». При использовании такого алфавита построение правильного многоугольника требует конечного числа штрихов, каждый из которых можно описать с помощью конечного числа инструкций, и, как следствие, является задачей конечной сложности. В построении же окружности, напротив, участвует «бесконечное количество бесконечно коротких штрихов», и поэтому окружность представляется нам как кривая бесконечной сложности. Однако если производить построение окружности рекурсивно, можно видеть, что необходимо лишь конечное число инструкций, и значит, построение окружности также является задачей конечной сложности. Начнем, например, с правильного многоугольника, число сторон которого равно , затем заменим каждый штрих длины двумя штрихами длины ; далее процесс повторяется снова и снова. Для построения кривых Коха применяется тот же подход, но с использованием более простых операций: длину каждого штриха нужно всего лишь умножить на r, причем относительное расположение штрихов остается неизменным на протяжении всего построения. Отсюда и следует парадоксальное заявление: когда сложность определяется длиной лучшего на настоящий момент алгоритма, выраженного средствами данного алфавита, кривая Коха оказывается проще окружности.

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

На рис.2 показано как построить триадную кривую Коха. Триадная кривая Коха -- один из стандартных примеров, проводимых в подтверждении того, что кривая может иметь фрактальную размерность D>1.

Построение кривой Коха начинается с прямолинейного отрезка единичной длины L(1)=1. Этот исходный отрезок называется затравкой и может быть заменен некоторым многоугольником, например, равносторонним треугольником, квадратом. Построение кривой Коха продолжается: каждое звено затравки мы заменяем образующим элементом, обозначенным через n=1. В результате такой замены мы получаем 1-е поколение -- кривую из четырех прямолинейных звеньев, каждое длиной по 1/3. Длина всей кривой первого поколения составляет величину L(1/3)=4/3. Следующее поколение получается при замене каждого прямолинейного звена уменьшенным образующим элементом. В результате мы получаем кривую второго поколения, состоящую из звеньев, каждый длиной . Длина кривой второго поколения равна L(1/9)==16/9. Заменяя все звенья предыдущего поколения кривой уменьшенным образующим элементом, получаем новое поколение кривой. Кривая n-го поколения при любом конечном n называется предфракталом.



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

В виде исключения проследим во всех подробностях за тем, как получается выражение для D. Длина предфрактала n-го поколения определяется формулой

Длина каждого звена составляет Замечая, что число поколений n представимо в виде запишем длину предфрактала в виде

Данная формула имеет вид приближенной формулы

Число сегментов равно

и может быть записано в виде

Как будет показано дальше, D -- фрактальная размерность кривой Коха. Прежде всего, заметим, что построение Коха позволяет в любом поколении получать нормальную кривую конечной длины. Мандельброт называет такие кривые предфракталами. Но при увеличении числа поколений стремится к нулю и длина кривой расходится. Ясно, что множество точек, которое получает как предел бесконечно большого числа итераций процедуры Коха, не является кривой, для которого длина является удобной мерой. Но если мы выберем пробную функцию , равна D. Мы заключаем, что критическая размерность и, следовательно, размерность Хаусдорфа-Безиковича для триадной кривой Коха равна . На каждой стадии построения предфракталы Коха могут быть растянуты в прямую линию, поэтому топологическая размерность триадной кривой Коха равна Так как размерность Хаусдорфа-Безиковича D для кривой Коха больше ее топологической размерности , мы заключаем, что кривая Коха есть фрактальное множество с фрактальной размерностью .

Квадратичный остров Коха (размерность береговой линии 3/2=1,5000). Инициатором здесь служит квадрат (отсюда название квадратичные). Одним из преимуществ таких построений является то, что с ними можно экспериментировать даже на слабых графических системах. Еще одно преимущество -- квадратичные фракталы ведут непосредственно к оригинальной кривой Пеано. Генератор выглядит следующим образом (см. рис. 3):

Рис. 3. Генератор кривой Пеано

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

Квадратичный остров Коха (размерность береговой линии ). В качестве инициатора снова возьмем квадрат, а генератором будет следующая ломаная (см. рис. 4):

Рис. 4. Квадратичный остров Коха

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

Свой вклад в сходство внешних форм вносит тот факт, что кривые Коха обладают весьма интересным свойством максимальности. Расположим все генераторы Коха, порождающие кривые без самопересечений, на квадратной решетке, образованной прямыми, параллельными и перпендикулярными отрезку [0, 1]. Допустим также, что все эти генераторы можно использовать с любыми инициаторами на нашей квадратной решетке. Определим как максимальные те генераторы, которые характеризуются наибольшим значением N и, как следствие, D.

Нетрудно заметить, что

при четных b и

при нечетных b.

При увеличении B возрастает как максимальное значение N, так и число альтернативных максимальных многоугольников. Таким образом, на предельную кривую Коха все большее влияние оказывает исходный генератор. Кроме того, кривая выглядит все более изощренной, поскольку стремление достичь максимальной размерности, избежав при этом самопересечения, налагает определенные требования, которые лишь ужесточаются с ростом D. Этот процесс достигает кульминации с пределом Пеано D=2.

1.2.2 Различные варианты построения кривой Коха

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



Параметр t здесь любое действительное число. Если изменить масштаб длины в одно и то же число раз r для всех компонент радиус-вектора x, точки x отобразятся в новые точки , и мы получим новое множество точек r(), определяемое соотношением

Здесь снова любое действительное число. Если сдвинуть новое множество точек r(), подвергнув все его точки параллельному переносу на величину (1-r), то в результате мы получим исходное множество точек : прямая инвариантна относительно изменения масштаба длины. Прямая инвариантна и относительно параллельного переноса

где n - любое действительное число.

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

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

Полезно рассмотреть ограниченные множества, такие, как конечный отрезок прямой. Отрезок прямой не обладает трансляционной симметрией -- любой сдвиг его всегда порождает новое множество точек. Но если изменить длины в r раз, где r<1, то получится новое множество точек которое составит небольшую часть прямой. Этим отрезком прямой, подвергнув его параллельному переносу, можно покрыть часть исходного прямолинейного отрезка При надлежащем выборе числа r мы можем однократно покрыть исходный отрезок N непересекающимися отрезками. Можно сказать, что множество самоподобно с коэффициентом подобия r. Для отрезка прямой единичной длины мы можем выбрать r(N)=1/N, где N -- любое целое число. Прямоугольный участок можно покрыть его уменьшенными копиями, если их длины изменить в раз. Аналогично прямоугольный параллелепипед можно покрыть его уменьшенными копиями, если выбрать . В общем случае масштабный множитель следует выбирать равным .

Размерность подобия d для прямых, плоскостей и кубов равна соответственно 1, 2 и 3.

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



С размерностью подобия d, равной размерности Хаусдорфа-Безиковича .

В общем случае размерность подобия определяется выражением

Для самоподобных фракталов размерность Хаусдорфа-Безиковича D равна , и для таких фракталов мы будем опускать индекс S у размерности подобия.

Размерность подобия легко поддается определению для различных фракталов, получающихся с помощью различных вариантов построения Коха. Рассмотрим предфрактал Коха, построенный с единичным квадратом в качестве затравки и образующим элементом, состоящим из N=8 ломанных длиной r=1/4 (см. рис. 5).

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



Эта кривая имеет размерность подобия и равна размерности Хаусдорфа-Безиковича множества, получающегося после бесконечно большого числа итераций. Заметим, однако, что поскольку в качестве затравки мы используем единичный квадрат, фигура в целом не выдерживает квадрат подобия. Каждый фрагмент «береговой линии» самоподобен, но, уменьшив всю кривую в r раз, мы получим уменьшенную копию оригинала, и вполне возможно, что оригинал нельзя будет покрыть такими уменьшенными множествами. Дело в том, что фрактальная скейлинговая инвариантность достигается только в пределе при , и мы заключаем, что фрактальная природа кривых Коха есть, строго говоря, локальное свойство.

Рис.6. Треугольный невод

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

Замечательная кривая Коха изображена на рис. 6. Эта кривая без самопересечений заполняет прямоугольный равнобедренный треугольник. Затравкой служит единичный интервал, а образующий элемент, показанный на рис. 6, состоит из N=2 звеньев длиной r=0.99*. Мы выбрали коэффициент 0,99 для того, чтобы нам легче было проследить за структурой кривой, так как при r= каждое поколение выглядит просто как бумага «в клеточку».

Определяемое этим построением фрактальное множество имеет размерность . Как видно из рис. 6, образующий элемент используется в двух вариантах: один сдвигает середину отрезка прямой влево, другой вправо. Кроме того, каждое новое поколение предфракталов начинается с чередующихся левых и правых образующих элементов. На рис.7 каждое новое поколение показано в увеличенном виде. Это сделано для того, чтобы прямолинейные отрезки имели заданную длину и за структурой кривой можно было следить без ухудшения разрешающей способности.

Попытаемся теперь слегка изменить правила построения. Пусть при первом использовании образующего элемента середина образующего отрезка смещается влево. Каждое последующее поколение начинается с образующего элемента, смещенного вправо, а затем смещения середины вправо и влево чередуются. Несколько первых поколений и 11-е поколение показаны на рис. 7. Предельная фрактальная кривая называется драконом Хартера-Хейтуэя.

1.2.3 Кривые Пеано

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

Большая часть кривых Пеано, включая и полученные путем рекурсивного построения Коха, поддается естественной параметризации с помощью скалярной величины t, которую можно назвать «временем». Имея дело с такими кривыми, мы вполне можем использовать термины «движения Пеано», «заполняющие плоскость движения», «движения, проходящие по всем плиткам» или просто «прохождения по плиткам».

Возьмем оригинальную кривую Пеано и представим величину t как число в системе исчисления с основанием N=9 вида 0, … значения времени с одинаковым первым «знаком» после запятой отобразятся на одну и ту же девятую часть исходного квадрата, значения с одинаковым вторым «знаком» отобразятся на одну и ту же восемьдесят первую () часть исходного квадрата и т. д. Таким образом, покрытие отрезка [0, 1], отображается на покрытие квадрата. Последовательные девятые доли линейных плиток отображаются на последовательные подплитки плоскости. А свойство отрезка, именуемое пертайлинг, то есть рекурсивная и бесконечная разбиваемость на меньшие плитки, подобные целому отрезку [0, 1], отображается на аналогичное свойство квадрата. Различные движения Пеано, коими мы обязаны Э. Чезаро и Д. Пойа, отображают это свойство также и на всевозможные самоподобные покрытия треугольников.

В более общем смысле большинство движений Пеано порождают самоподобные покрытия плоскости. В простейшем случае существует некое основание N, и мы начинаем с линейного пертайлинга, заключающегося в последовательном разбиении целого на N-е доли. Однако прохождение снежинки подразумевает неравномерное разбиение интервала времени t[0,1] сначала на четыре подынтервала длиной 1/9, затем на четыре подынтервала длиной 1/9, один - 1/9, два - 1/9 и два - 1/9.

Заполняющая плоскость, представленная на рисунке, является оригинальной кривой Пеано невероятно краткий алгоритм Джузеппе Пеано был графически воплощен в работе Мура. На нашем рисунке (см. рис. 8) кривая Пеано развернута на -- тем самым эта «блудная» конструкция оказывается возвращенной в лоно кривых Коха, т. е. теперь генератор всегда одинаково размещается на сторонах терагона, полученного на предыдущем этапе построения.

Инициатором здесь выступает единичный квадрат (черный внутри), а генератор (см. рис. 8) выглядит следующим образом:

Рис. 8. Кривая Пеано

Рис. 9. Примеры кривых Пеано

Поскольку генератор - самокасающаяся кривая, получаемые в результате построения конечные острова Коха представляют собой скопление черных квадратов, словно вырезанных из бесконечной шахматной доски. После n-го этапа построения терагон Коха выглядит как решетка из прямых с шагом ; эта решетка заполняет квадрат, площадь которого равна 2, причем плотность линий быстро возрастает по мере того, как .

На трех верхних картинках двусмысленность самокасаний устранена путем срезания соответствующих углов с сохранением общей площади.

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

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

Квадратичные построения Коха с размерностью D=2: прохождения треугольника по Чезаре и по Пойа и их варианты.

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

Рис. 10. Троичную кривую Коха

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

Прохождение треугольника по Пойа. Инициатор -- отрезок [0, 1], генератор -- как на рисунке вверху. Генератор поочередно занимает правое и левое положение относительно терагона, причем его положение относительно начального отрезка также поочередно меняется. Ниже показаны третий и четвертый этап построения (см. рис. 11):

Рис. 11. Прохождение треугольника по Пойа

Терагоны напоминают квадратные куски диаграммной бумаги, запихнутые внутрь прямоугольного равнобедренного треугольника, один из катетов которого и есть исходный отрезок [0, 1]. Предельная кривая проходит по всей внутренней области треугольника.

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

Рис. 12. Прохождение треугольника по Чезаро

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

Каждый отрезок в решетках, покрываемых терагонами Чезаро, покрывается дважды. Конструкция содержит не только самокасания, но и самоперекрытия.

Глава 2. Реализация геометрических фракталов с помощью языка программирования Pascal

2.1 Алгоритм построения кривой Коха

Кривая Коха является типичным геометрическим фракталом. Процесс её построения выглядит следующим образом.

program kroha; // начало программы

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

uses crt,graph; // подключение графических модулей

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

var Hu,Hv,rx,ry,Sx,Sy,fi:real; // раздел описания переменных, вещественные числа

dr,mode:integer; // целые числа

Procedure Init;

Begin // секция инициализации

fi:=pi/2;

Задаем команду ПК для самостоятельного выбора значений переменных: detect - драйвер сам определяет лучший режим.

dr:=detect;

Инициализируем графический режим. С этого момента все графические средства доступны пользователю.

initgraph(dr,mode,'');// переход в графический режим

Hu:=3; // точка на экране, в которой располагается центр декартовой системы

Hv:=getmaxy-3; // точка на экране, в которой располагается центр декартовой системы

rx:=3.5;

ry:=3.5;

Sx:=getmaxx/rx; // масштабный множитель

Sy:=getmaxy/ry; // масштабный множитель

end;

Процедура OutLine является рекурсивной, она строит кривую Коха. Параметрами этой процедуры являются x1,y1,x2,y2. эти числа задают единичный вектор в направлении очередного смещения.

Procedure OutLine(x1,y1,x2,y2:real;color:word);

var u1,v1,u2,v2:word; // целочисленный тип

begin // начало раздела операторов программы

u1:=round(x1*Sx+Hu);

v1:=round(-y1*Sy+Hv);

u2:=round(x2*Sx+Hu);

v2:=round(-y2*Sy+Hv);

setcolor(5);// делает пятый цвет в палитре цветом текущего рисунка

line(u1,v1,u2,v2);

end; // Конец раздела операторов программы

Procedure Draw(x1,y1,x2,y2:real;n:word);

var x3,y3,x4,y4,x5,y5,x6,y6,dx,dy:real;

begin // Начало раздела операторов программы

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

if n>0 then begin

dx:=(x2-x1)/3; // длина одного отрезка по оси X

dy:=(y2-y1)/3; // по оси Y

x3:=x1+dx; // отодвигаемся от начальной точки по оси X

y3:=y1+dy; // по оси Y

x6:=x2-dx;

y6:=y2-dy;

x4:=dx*cos(fi)-dy*sin(fi)+x3; //вычисляем координату вершины треугольника по оси X

y4:=dx*sin(fi)+dy*cos(fi)+y3; // по оси Y

x5:=x4+dx; // вычисляем координату вершины 3 -ей ломанной по оси X

y5:=y4+dy; // по оси Y

В результате образуется ломаная, состоящая из четырех звеньев длины 1/3. Они имеют следующие координаты, которые кладем в стек:

Draw(x1,y1,x3,y3, n-1); // первой ломанной;

Draw(x3,y3,x4,y4, n-1); // второй ломанной;

Draw(x4,y4,x5,y5, n-1); // третьей ломанной;

Draw(x5,y5,x6,y6, n-1); // четвертой ломанной;

Draw(x6,y6,x2,y2, n-1);

End

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

else

OutLine(x1,y1,x2,y2,5);

end; // конец раздела операторов программы

Begin

clrscr;

init;

Draw(0,0,3,0,5);

repeat until keypressed; // пустой цикл, продолжающийся до нажатия любой клавиши

closegraph; // завершить работу в графической системе

end. // конец программы

2.2 Алгоритм построения Дракона

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

program dragon; // начало программы

uses graph; // подключение графических модулей

var k,d,m:integer; // раздел описания переменных, целые числа

procedure ris(x1,y1,x2,y2,k:integer);

var xn,yn:integer; // раздел описания переменных процедуры

begin // секция инициализации

if k>0 then

begin

xn:=(x1+x2) div 2 +(y2-y1) div 2; // вычисляем координату ломанной по оси X

yn:=(y1+y2) div 2 -(x2-x1) div 2; // по оси Y

В стек кладем координаты:

ris(x1,y1,xn,yn,k-1); // - первой ломанной

ris(x2,y2,xn,yn,k-1); // - второй ломанной

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

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

end

else begin line(x1,y1,x2,y2);

end; // конец раздела операторов программы

end;

begin

readln(k); // задаем порядок кривой

d:=detect;

initgraph(d,m,' '); // переход в графический режим

ris(200,300,500,300,k);

readln;

end. // конец программы

Заключение

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

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

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

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

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

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

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

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

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

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

1. Варламов С. Снежинки и ледяные узоры на стекле. -- М.: Квант. -- 2002. -- №5 -- 29 -- 30 с.

2. Мандельброт Б. Фрактальная геометрия природы. -- М.: Институт компьютерных исследований, 2002 -- 656 с.

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

4. Фадер Е. Фракталы. Пер. С англ. -- М.: Мир, 1991. -- 254 с.

5. Штейнберг В.Э. Семантические фракталы Штейнберга. -- М: Школьные технологии, 2002 -- №1 -- 204 -- 210 с.

Приложение

В приложении представлена программа построения кривой Коха и Дракона в среде программирования Pascal.

// Кривая Коха

program krm;

uses crt,graph;

var Hu,Hv,rx,ry,Sx,Sy,fi:real;

dr,mode:integer;

Procedure Init;

begin

fi:=pi/2;

dr:=detect;

initgraph(dr,mode,'');

Hu:=3;

Hv:=getmaxy-3;

rx:=3.5;

ry:=3.5;

Sx:=getmaxx/rx;

Sy:=getmaxy/ry;

end;

Procedure OutLine(x1,y1,x2,y2:real;color:word);

var u1,v1,u2,v2:word;

begin

u1:=round(x1*Sx+Hu);

v1:=round(-y1*Sy+Hv);

u2:=round(x2*Sx+Hu);

v2:=round(-y2*Sy+Hv);

setcolor(5);

line(u1,v1,u2,v2);

end;

Procedure Draw(x1,y1,x2,y2:real;n:word);

var x3,y3,x4,y4,x5,y5,x6,y6,dx,dy:real;

begin

if n>0 then begin

dx:=(x2-x1)/3;

dy:=(y2-y1)/3;

x3:=x1+dx;

y3:=y1+dy;

x6:=x2-dx;

y6:=y2-dy;

x4:=dx*cos(fi)-dy*sin(fi)+x3;

y4:=dx*sin(fi)+dy*cos(fi)+y3;

x5:=x4+dx;

y5:=y4+dy;

Draw(x1,y1,x3,y3, n-1);

Draw(x3,y3,x4,y4, n-1);

Draw(x4,y4,x5,y5, n-1);

Draw(x5,y5,x6,y6, n-1);

Draw(x6,y6,x2,y2, n-1);

end

else

OutLine(x1,y1,x2,y2,5);

end;

Begin

clrscr;

init;

Draw(0,0,3,0,5);

repeat until keypressed;

closegraph;

end.

// Кривая дракона

program dragon;

uses graph;

var

k,d,m:integer;

procedure ris(x1,y1,x2,y2,k:integer);

var xn,yn:integer;

begin

if k>0 then

begin

xn:=(x1+x2) div 2 +(y2-y1) div 2;

yn:=(y1+y2) div 2 -(x2-x1) div 2;

ris(x1,y1,xn,yn,k-1);

ris(x2,y2,xn,yn,k-1);

end

else begin line(x1,y1,x2,y2);

end;

end;

begin

readln(k);

d:=detect;

initgraph(d,m,'c:\lang\tp\bgi');

ris(200,300,500,300,k);

readln;

end.

Размещено на Allbest.ru

...