Исследование фракталов: Кривая Леви

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ 

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОСТОЧНО – СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ 

ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ» 

ЭЛЕКТРОТЕХНИЧЕСКИЙ  ФАКУЛЬТЕТ

Кафедра систем информатики 
 
 

Курсовая работа

(Д.ХХХ.Х.Х.ХХ.ХХ.ХХ.ХХ.ПЗ)

по  дисциплине «Программирование на языке высокого уровня С/С++»

Тема: «Исследование фракталов: Кривая Леви» 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Улан-Удэ

2010

 

ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ  ТЕХНОЛОГИЧЕСКИЙ 

УНИВЕРСИТЕТ

___________________________________________________________________________ 

ЭЛЕКТРОТЕХНИЧЕСКИЙ  ФАКУЛЬТЕТ

Кафедра систем информатики

ЗАДАНИЕ

на  курсовую работу

                                    

 

                                    Руководитель работы  _____________________

                                    Исполнитель                 _____________________

                                    Дата выдачи                 "16" февраля 2010 г.

Аннотация

      Работа  посвящена исследованию фракталов. В данной работе рассматривается Кривая Леви- кривая, которая нигде не дифференцируема и не спрямляема. Она строится на отрезке, который заменяется прямоугольным треугольником и сам отрезок удаляется.

      Целью работы является исследование фрактала: Кривой Леви. Для достижения поставленной цели в работе рассмотрены теоретические вопросы в данной предметной области, предложен способ построения Кривой Леви. Разработано программное обеспечение, реализующее предложенный способ. 
 
 
 
 

 

Содержание

Введение  ____________________________________________________________5

1. Теоретический  раздел________________________________________________7

1.1. Понятие  фрактал__________________________________________________7

1.2. Виды  фракталов___________________________________________________7

      1.3. Кривая Леви___________________________________________________9

   1.3.2Построение Кривой Леви_______________________________________10

  1.4 Графика__________________________________________________________11

   1.4.1 Графические средства операционной системы Windows_____________11

      1.4.2 Работа с графикой с использованием  классов, свойств и функций  компонент Borland C++ Builder____________________________________________12

2. Проектный  раздел __________________________________________________16

3. Программный  раздел__________________________________________________17

4. Экспериментальный  раздел____________________________________________ 19

Заключение ____________________________________________________________22

Список  использованных источников_______________________________________23 
Введение

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

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

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

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

      И, поэтому, объектом исследований данной работы является мир фракталов, а именно Кривая Леви.

      Предмет исследований фрактал Кривая Леви 

      Целью работы является исследование фрактала кривой Леви.

      Задачи:

      1) узнать, что такое «фракталы»;

      2) изучить историю возникновения и развития фрактальной геометрии;

      3) изучить способы построения фрактала кривой Леви;

      4) Изучить графические средства языка С/С++

      5) разработать программу создания фракталов на языке программирования.

      Методы  исследования: изучение и анализ источников информации, метод выборки и практический. 

 

      1. Теоретический раздел

      1.1. Понятие фрактал

      В 1975г. Бенуа Мандельброт сформировал  следующее определение фрактала. Фрактал (от лат. fragere – ломать, разламывать) – это множество, размерность Хаусдорфа-Безиковича строго больше его топологической размерности. Но это определение ограничительно при всей своей правильности и точности. Оно исключает многие фракталы, встречающиеся в различных областях знаний. Впоследствии Б. Мандельброт предложил другое определение.

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

невозможна.   
 

1.2. Виды фракталов

      Фракталы  подразделяются на следующие группы:

      1)  Геометрические. Этот  тип фракталов  получается путем простых геометрических  построений: берется набор  отрезков, на  основании  которых  будет  строиться  фрактал,  затем  к этому  набору  применяется  набор  правил,  который преобразует  его  в  какую-нибудь  геометрическую фигуру. Далее к каждой части этой фигуры применяется тот же набор правил, и, произведя бесконечное число  таких  преобразований (по крайней мере, мысленно),  получим  геометрический  фрактал. Примерами  геометрических  фракталов  являются кривая снежинка Леви(рис 1), Коха, ковер Серпинского, кривая Пеано.

      2)  Алгебраические.  Эти  фракталы  строят  на  основании  алгебраических  формул, иногда весьма простых.  Один из  методов построения представляет собой итерационный расчет функции Zn + 1 = f(Zn), где Z – некоторое число, а f(Z) – какая либо  функция.  Расчет  функции  продолжается  до  выполнения  определенного условия.  Иллюстрацией  фракталов  данного  вида  может  служить  множество Мандельброта (рис 2).

      3)  Системы итерируемых функций.  Эта группа фракталов стала известна благодаря  М.  Барнсли . Теория  итерируемых  функций  служит  составной  частью  общей  теории  динамических систем – важного раздела математики.

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

      4)  Стохастические. Типичный представитель  данного класса фракталов – «Плазма» (рис 4).

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

       

             рис.1                      рис. 2.                      рис. 3.                рис. 4. 
 
 

1.3. Кривая Леви

      1.3.1Кривая Леви — фрактал. Предложен французским математиком П. Леви. Получается, если  на отрезке построить два отрезка, которые равны начальной , и в пределе получим кривую Леви (рис. 5).

      

      Рис. 5

      Кривая  Леви нигде не дифференцируема и не спрямляема. На любом интервале кривой Леви есть точки самопересечения. Хаусдорфова размерность кривой Леви приблизительно равна 1,9340. Хотя кривая Леви состоит из двух равных частей, каждая из которых подобна всей кривой с коэффициентом подобия 1/ , из-за наличия самопересечений её размерность меньше чем . 
 
 
 
 
 

      1.3.2 Построение Кривой Леви

      Базовым элементом для кривой Леви является отрезок AB. Первый шаг включает в  себя построение равнобедренного прямоугольного треугольника на отрезке AB как на гипотенузе. При этом сама гипотенуза в дальнейшем построении не участвует и исключается  из кривой. Таким образом, первое поколение  кривой представляет собой ломаную ACB.

На втором шаге с каждым из отрезков AC и CB проделываем  ту же операцию, что и с отрезком AB на первом шаге. Последующие поколения  кривой строятся по тому же алгоритму. Следовательно, задача сводится к определению  координаты точки  С(х,у) по известным координатам точек A и B.

      Для решения данной задачи сперва решим  вспомогательную задачу:

Вектор , и ┴. Найти вектор , е через координаты ,если ||=|.

      Решение. Из условия следует, что ; . Получим систему уравнений с двумя неизвестными:  

После решения этой системы уравнения  вектор с координатами или  .

Вернемся  к построению кривой Леви.

По свойству прямоугольного равнобедренного треугольника точки A, B,C равноудалены от точки О - середины гипотенузы, OC┴AO, OC=AO. Пусть A(x0,y0);B(x1,y1), тогда точка О как середина отрезка AB будет иметь координаты O() . Применяя вспомогательную задачу, имеем ,. Т.к. , то или . Нам для построения кривой Леви необходим вектор, направленный <влево> от , т.е. . Если O() и C(x,y), то

 , .

На основании  проведенных вычислений мы строим программу  вычисления координат точек- вершин фрактальной кривой. 
 
 

1.4 Графика

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

      Необходимо  рассмотреть:

1. Графические средства операционной системы Windows.
2. Графику в языке С++.

 

1.4.1 Графические средства операционной системы Windows

      В Microsoft Windows существует несколько средств для вывода графической информации, включая DirectDraw, OpenGL, GDI и т.д. В данной работе рассмотривается GDI (Graphics Device Interface) - подсистема Windows, ответственная за вывод графики и текста на дисплей и принтер. Именно она занимается выводом большинства "окошек", которые и составляют то, что видит пользователь Windows на экране. Она является базовым и, пожалуй, простейшим способом вывода графики в Windows. Далее рассмотрим систему GDI.

      Функции GDI

      Когда приложения обращаются к GDI для выполнения операций вывода графического изображения, они работают не с реальными (физическими) устройствами вывода, а с логическими. Приложения Windows не определяют тип видеомонитора, а работают с логическим   видеомонитором, который способен отображать любой  цвет и имеет огромное разрешение. Выполняя запрос приложения, GDI обращается к драйверу соответствующего устройства вывода. Драйвер работает непосредственно  с физическим устройством вывода. В процессе выполнения запроса GDI учитывает  ограниченные возможности физического  устройства вывода и его аппаратные особенности, делая необходимые приближения. В зависимости от типа физического устройства, используемого для вывода, GDI может выбрать для отображения цвет, наиболее соответствующий запрошенному и поддерживаемый устройством. Если устройства вывода монохромное, вместо различных цветов могут использоваться градации серого цвета. Поэтому приложение может запросить для вывода любой цвет, но для рисования будет использован только такой, который есть только на данном физическом устройстве. Такая ситуация возникает не только при работе с цветом. Приложение может запросить для вывода шрифт, описав его характеристики, GDI подберёт для вывода наиболее подходящий шрифт, соответствующий описанию, и представит его приложению. Такой механизм удобен для обеспечения аппаратной независимости. Чем лучше используемая аппаратура, чем большими возможностями она обладает, тем ближе будут параметры полученного шрифта и цвета соответствовать запрошенным. 

      1.4.2 Работа с графикой с использованием классов, свойств и функций компонент Borland C++ Builder

В среде  C++Builder существует три рода объектов, которые имеют отношение к графике:

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

      Графика - представляет растровое изображение  некоторого файла или ресурса (битового образа, пиктограммы или метафайла). C++Builder определяет производные от базового класса TGraphic объектные классы: TBitmap, Ticon, TMetafile.

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

      Графические объекты Windows взаимосвязаны. Так - объект TPicture всегда содержит некоторую графику, которой в свою очередь, может потребоваться для отображения канва, а единственный стандартный графический класс канвы - это TBitmap.

      Borland С++ Builder инкапсулирует функции Windows GDI на разных уровнях. Наиболее завершенным является интерфейс, предоставляемый свойством Canvas (канва), объектного класса канвы, его графических компонент. Использование канвы снимает с программиста заботу при выводе изображений об инициализации контекста устройства и его освобождении. Наличия вложенных свойств (характеристик пера, кисти, шрифтов, растровых изображений) также не требует слежения за состояниями ресурсов - основная задача - это определение характеристик для этих графических объектов и грамотное их использование.

      Объектный класс канвы

      Инкапсулированные и перегруженные функции GDI и WinApi объектного класса канвы многие авторы относят к трем различным уровням. В этой условной классификации функции высокого уровня обеспечивают возможность рисования линий, фигур и текста. Определение свойств и методов манипулирования графическими примитивами канвы отнесены к среднему уровню. Нижний уровень обеспечивается доступ к самим функциям Windows GDI. Классификация не бесспорна, но она позволяет ориентироваться в достаточно большом колличестве свойств и методов канвы и, поэтому, приведем эту классификацию.