План работы. Введение История фракталов - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
История фракталов 1 11.51kb.
План Введение: история рождения фотографи 1 128.5kb.
Познавательные психические процессы. Введение. Ощущение и восприятие. 1 168.2kb.
План стр. Введение ······································· 2 2 722.2kb.
Рефераты, курсовые, дипломные работы План Введение Система антропометрической... 1 105.88kb.
Фрактальная графика и ее практическое применение 1 47.19kb.
Программа дисциплины «Введение в профессию» 1 99.95kb.
Теория йоги. Введение в фундаментальную аксиоматику йоги. Введение... 1 317.44kb.
Становление социальной работы Введение 2 813.9kb.
Тематический план изучения дисциплины тематический план № Тема недели... 1 144.77kb.
Рабочая учебная программа по дисциплине История социальной работы... 1 169.65kb.
Образовательная программа по предмету технология для 6 класса «Технология... 3 355.07kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

План работы. Введение История фракталов - страница №1/1



Комитет по образованию г. Улан-Удэ

Муниципальный центр оценки качества образования

XVI городская научно-практическая конференция «Шаг в будущее»

Муниципальное образовательное учреждение «гимназия №33»


Фракталы.


Выполнил: Бутуханов Б.Ю. Ученик 11 класса

гимназии №33

Научный руководитель: Балдано Алёна Викторовна,

Учитель алгебры и геометрии высшей

квалификационной категории

гимназии №33

Улан-Удэ


2008

План работы.

Введение………………………………………………………………………………………...3

§1.История фракталов………………………………………………………………………….4

§2.Размерность………………………………………………………………………………….6

§3.Виды фракталов……………………………………………………………………………..7

§4.Использование фракталов в компьютерной графике……………………………………..9

Заключение…………………………………………………………………………………….10

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

Приложения……………………………………………………………………………………12

Введение.

Актуальность.

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


Основным источником информации послужила глобальная сеть.

Основными методами исследования являются: чтение и анализ литературы по фракталам.



Цель работы.

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

Задачи работы.

-ознакомиться с литературой о фракталах.

-ознакомиться с историей фракталов.

-изучить какую роль играют фракталы в компьютерной графике.



§1.История фракталов.
Геометрия, которую мы изучали в школе и которой пользуемся в повседневной жизни, восходит к Эвклиду (примерно 300 лет до нашей эры). Треугольники, квадраты, круги, параллелограммы, параллелепипеды, пирамиды, шары, призмы - типичные объекты, рассматриваемые классической геометрией. Предметы, созданные руками человека, обычно включают эти фигуры или их фрагменты. Однако в природе они встречаются не так уж часто. Действительно, похожи ли, например, лесные красавицы ели на какой-либо из перечисленных предметов или их комбинацию? Легко заметить, что в отличие от форм Эвклида природные объекты не обладают гладкостью, их края изломаны, зазубрены, поверхности шероховаты, изъедены трещинами, ходами и отверстиями. "Почему геометрию часто называют холодной и сухой? Одна из причин заключается в ее неспособности описать форму облака, горы, дерева или берега моря. Облака - это не сферы, горы - не конусы, линии берега - это не окружности, и кора не является гладкой, и молния не распространяется по прямой. Природа демонстрирует нам не просто более высокую степень, а совсем другой уровень сложности", - этими словами начинается "Фрактальная геометрия природы", написанная Бенуа Мандельбротом. Именно он в 1975 году впервые ввел понятие фрактала - от латинского слова fractus, сломанный камень, расколотый и нерегулярный. Оказывается, почти все природные образования имеют фрактальную структуру. Что это значит? Если посмотреть на фрактальный объект в целом, затем на его часть в увеличенном масштабе, потом на часть этой части и т. п., то нетрудно увидеть, что они выглядят одинаково. Фракталы самоподобны - их форма воспроизводится на различных масштабах. Открытие фракталов произвело революцию не только в геометрии, но и в физике, химии, биологии. Фрактальные алгоритмы нашли применение и в информационных технологиях, например, для синтеза трехмерных компьютерных изображений природных ландшафтов, для сжатия (компрессии) данных. Первые идеи фрактальной геометрии возникли в 19 веке. Кантор с помощью простой рекурсивной (повторяющейся) процедуры превратил линию в набор несвязанных точек (так называемая Пыль Кантора). Он брал линию и удалял центральную треть и после этого повторял то же самое с оставшимися отрезками. Пеано нарисовал особый вид линии (рисунок №1). Для ее рисования Пеано использовал следующий алгоритм. На первом шаге он брал прямую линию и заменял ее на 9 отрезков длинной в 3 раза меньшей, чем длинна исходной линии (Часть 1 и 2 рисунка 1). Далее он делал то же самое с каждым отрезком получившейся линии. И так до бесконечности. Ее уникальность в том, что она заполняет всю плоскость. Доказано, что для каждой точки на плоскости можно найти точку, принадлежащую линии Пеано. Кривая Пеано и пыль Кантора выходили за рамки обычных геометрических объектов. Они не имели четкой размерности. Пыль Кантора строилась вроде бы на основании одномерной прямой, но состояла из точек (размерность 0). А кривая Пеано строилась на основании одномерной линии, а в результате получалась плоскость. Во многих других областях науки появлялись задачи, решение которых приводило к странным результатам, на подобие описанных выше (Броуновское движение, цены на акции).

Отец фракталов.

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

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

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



§2.Размерность.

В евклидовой геометрии есть понятие размерности: размерность отрезка — единица, размерность круга — два, шара — три (или: прямая — 1, плоскость — 2, …). Например, если мы будем измерять длину отрезка, то, например, метровых отрезков в нём будет N, полуметровых 2N, дециметровых — 10N и так далее. В данном случае наблюдается прямая пропорциональная зависимость. В случае измерения площади мы уже получим следующие значения: 4N, 100N, то есть здесь зависимость уже квадратичная. Объём трёхмерных фигур пропорционален кубу их линейных размеров.


Если попытаться применить эти правила к фрактальным объектам, возникает парадоксальная ситуация — их размерность окажется дробным числом. Так как фрактал состоит из бесконечного числа повторяющихся элементов, невозможно точно измерить его длину. Это означает, что чем более точным инструментом мы будем его измерять, тем большей окажется его длина. В то время как гладкая евклидова линия заполняет в точности одномерное пространство, фрактальная линия выходит за пределы одномерного пространства, вторгаясь в двумерное. Таким образом, фрактальная размерность кривой Коха или «колбасы» Минковского будет находиться между 1 и 2.
Размерность фрактала можно вычислить, пользуясь размерностью Хаусдорфа-Безиковича, определение которой исходит из простого факта. Если мы приблизим отрезок так, что его длина увеличится в 2 раза, его размер увеличится в 2 раза. Если мы приблизим квадрат таким же образом (так, чтобы его линейные размеры выросли в 2 раза), его размер увеличится в 4 раза. При аналогичном приближении куба, его размер вырастет в 8 раз.
Тогда для вычисления размерности Хаусдорфа-Безиковича можно воспользоваться следующей формулой: размерность = log(s) / log(z), где s — изменение размера, z — изменение приближения
Для отрезка размерность будет равна log2 / log2 = 1, для квадрата: log4 / log2 = 2, для куба: log8 / log2 = 3.
Теперь, если вычислить размерность Хаусдорфа-Безиковича для снежинки Коха, она и вправду окажется дробной. Снежинка Коха строится путём последовательного разбиения отрезка на 4 новых, причём каждый из них будет в 3 раза меньше исходного. Получается, что приблизив какую-либо часть фигуры так, что длина отрезка увеличится в 3 раза, размер фигуры вырастет в 4 раза. Подставив эти числа в формулу, получим: log4 / log3 = 1.261.
Самым удивительным оказывается то, что и многие природные объекты обладают как бы дробной размерностью, хотя, строго говоря, для природных объектов такую размерность вычислить невозможно. Правильнее сказать, что в определённых диапазонах наблюдения природные объекты, возникшие в результате долгой диффузии и абсорбции, похожи на фрактальные множества. Например, размерность побережья лежит между 1,01 и 1,6. А фрактальная размерность кровеносной системы человека может быть рассчитана как приблизительно 3,4. Это не противоречит факту трехмерной топологической размерности пространства, в которое она вписана.

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

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



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

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

  • стохастические фракталы.

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

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

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

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



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

Вторая большая группа фракталов - алгебраические. Свое название они получили за то, что их строят, на основе алгебраических формул иногда весьма простых. Методов получения алгебраических фракталов несколько. Один из методов представляет собой многократный (итерационный) расчет функции Zn+1=f(Zn), где Z - комплексное число, а f некая функция. Расчет данной функции продолжается до выполнения определенного условия. И когда это условие выполнится - на экран выводится точка. При этом значения функции для разных точек комплексной плоскости может иметь разное поведение:



  1. С течением времени стремится к бесконечности.

  2. Стремится к 0

  3. Принимает несколько фиксированных значений и не выходит за их пределы.

  4. Поведение хаотично, без каких либо тенденций.

Пример алгебраического фрактала см. на рис. 3 в приложении. Функция F(zi)=-0.0542452+0.6891191i

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

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

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

§4.Использование фракталов в компьютерной графике.

L - системы


Существуют два основных способа построения фракталов. Первый способ - использование L-систем (от имени Lindenmayer), второй способ - применение системы IFS (iterated function systems). L-система - это грамматика некоторого языка (достаточно простого), которая описывает инициатор и преобразование, выполняемое над ним, при помощи средств, аналогичных средствам языка Лого (аксиоматическое описание простейших геометрических фигур и допустимых преобразований на плоскости и в пространстве). (рис. 5)

Системы итерирующих функций (IFS)


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


Заключение.
В своей работе я кратко изложил информацию о фракталах их истории и роли в современной компьютерной графике.

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

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

Теория фракталов используется и при изучении структуры Вселенной. Появляются теории о том, что наша Вселенная - фрактал. Возможно, именно фракталы раскроют тайну бесконечности нашей Вселенной.



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

1. Шабаршин А.А. “Введение во фракталы” – Екатеринбург, 1998.

2. Шредер М., “Фракталы, хаос, степенные законы”

3.Ватолин Д. Применение фракталов в машинной графике.

4. Шабаршин А.А “Фракталы”

5. Михалёв А.«Фракталы»


Интернет–источники.

www.ru.wikipedia.org статья “Фракталы”

5.www.fractal.narod.ru

6. www.fractal.nsu.ru

7. www.mathworld.com



mailto:sakva@narod.ru

Приложения.

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

рис 2.


Рис. 3 Пример алгебраического фрактала. Функция F(zi)=-0.0542452+0.6891191i



Рис. 4 Стохастический фрактал.


Рис. 5 Пример построения дерева с помощью L - системы



Рис. 6 Изображение листа папоротника, полученное с помощью IFS.



Рис. 7 Пример фрактального морфинга "дерева" в "лист папоротника"



Схема построения множеств Жюлиа и Мандельброта в программе Pascal.

Все сводится к вычислению одной единственной формулы.

Zi+1=Zi2+C

Здесь Z и C - комплексные числа. Как видно, формулы, по сути, представляет собой обычную рекурсию (или что-то вроде многократно примененного преобразования). Зная правила работы с комплексными числами данную формулу можно упростить и привести к следующему виду.

xi+1=xi2-yi2+a

yi+1=2*xi*yi+b

Построение множества Мандельброта сводится к следующему. Для каждой точки (a,b) проводится серия вычислений по вышеприведенным формулам, причем x0 и y0 принимаются равными нулю, т.е. точка в формуле выступает в качестве константы. На каждом шаге вычисляется величина r=sqrt(x2+y2 ). Значением r ,как ни трудно заметить, является расстояние точки с координатами (x,y) от начала координат ( r=sqrt[ (x-0)2+(y-0)2] ). Исходная точка (a,b) считается принадлежащей множеству Мандельброта, если она никогда не удаляется от начала координат на какое-то критическое число. Для отображения можно подсчитать скорость удаления от центра, если например точка ушла за критическое расстояние, и в зависимости от нее окрасить исходную точку в соответствующие цвет. Полное изображение множества Мандельброта можно получить на плоскости от -2 до 1 по оси x и от -1.5 до 1.5 по оси y. Также известно, что для получения приемлимой точности достаточно 100 итераций (по теории их должно быть бесконечно много). Ниже представлен листинг функции реализующей выполнение итераций и определение принадлежности точки множеству Мандельброта, точнее на выходе мы получаем цвет для соответствующе точки. В качестве критического числа взято число 2. Чтобы не вычислять корень, мы сравниваем квадрат расстояния (r2) с квадратом критического числа, т.е. сравниваем (x2+y2) и 4.

function MandelBrot(a,b: real): TColor;

var

x,y,xy: real;



x2,y2: real;

r:real;


k: integer;

begin


r:=0;

x:=0; y:=0;

k:=100;

while (k>0)and(r

begin

x2:=x*x;


y2:=y*y;

xy:=x*y;


x:=x2-y2+a;

y:=2*xy+b;

r:=x2+y2;

dec(k)


end;

k:=round((k/100)*255);

result:=RGB(k,k,k);

end;


Множество Жюлиа получается, если зафиксировать в формуле значение комплексной константы (a+ib), которая будет одинакова для всех точек, а начальные значения x0 и y0 принимать равными значениям координатам вычисляемой точки. Листинг для множества Жюлиа приведен ниже.

function Julia(x0,y0: real): TColor;

var

a,b,x,y,x2,y2,xy: real;



r:real;

speed,k: integer;

begin

r:=1;


a:=-0.55; b:=-0.55;

x:=x0; y:=y0;

k:=100;

while (k>0)and(r

begin

x2:=x*x;


y2:=y*y;

xy:=x*y;


x:=x2-y2+a;

y:=2*xy+b;

r:=x2+y2;

dec(k)


end;

k:=round((k/100)*255);

result:=RGB(k,k,k);

end;


Ниже приведен листинг функции отображающий данные множества.

procedure TForm1.BitBtn2Click(Sender: TObject);

var

x_min,y_min,x_max,y_max,hx,hy,x,y: real;



i,j,n: integer;

color: TColor;

begin

x_min:=-1.5; x_max:=2;



y_min:=-1.5; y_max:=1.5;

n:=300;


y:=y_min;

hx:=(x_max-x_min)/n;

hy:=(y_max-y_min)/n;

for j:=0 to n do

begin

x:=x_min;



for i:=0 to n do

begin


if rbM.Checked then color:=MandelBrot(x,y);

if rbJ.Checked then color:=Julia(x,y);

imPict.Picture.Bitmap.Canvas.Pixels[i,j]:=color;

x:=x+hx;


end;

y:=y+hy;


end;

end;