Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Реалізація алгоритму фрактальної кривої
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2009
Тип роботи:
Розрахункова робота
Предмет:
Інформаційні технології
Група:
КН- 411
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Розрахункова робота
з дисципліни “ Комп`ютерна графіка ”
Тема: «Реалізація алгоритму фрактальної кривої»
Теоретичні відомості
Поняття фрактал, фрактальна геометрія і фрактальна графіка, з'явилися в кінці 70-х. Слово фрактал утворено від латинського fractus і в перекладі означає той, що «складається з фрагментів». Воно було запропоноване математиком Бенуа Мандельбротом в 1975 році для позначення нерегулярних, але самоподібних структур. Народження фрактальної геометрії прийнято пов'язувати з виходом в 1977 році книги Мандельброта «The Fractal Geometry of Nature». У його роботах використані наукові результати інших учених, що працювали в 1875 - 1925 роках в тій же області (Пумнкаре, Фату, Жюліа, Кантор, Хаусдорф). Але тільки у наш час вдалося об'єднати їх роботи в єдину систему. Визначення фрактала, дане Мандельбротом: фракталом називається структура, що складається з частин, які в якомусь сенсі подібні до цілого. Самоподібність - одна з основних властивостей фракталів. Об'єкт називають самоподібним, коли збільшені частини об'єкту схожі на сам об'єкт і один на одного.
Розрізняють геометричні і алгебраїчні фрактали. Геометричні фрактали найпоширеніші. У двомірному випадку їх отримують за допомогою деякої ламаної (або поверхні в тривимірному випадку), званої генератором. За один крок алгоритму кожне з відрізків, складових ламаної, замінюється на ламану-генератор, у відповідному масштабі. В результаті багатократного повторення цієї процедури, виходить геометричний фрактал.
Фрактали - об'єкти, що володіють нескінченною складністю, дозволяють розглянути стільки ж своїх деталей поблизу, як і здалеку. Будь-які їх фрагменти, як нескінченно малі, так і нескінченно великі, по будові нічим не відрізняються один від одного. Фрактали можливі не тільки на площині, але і в просторі. Фрактальні структури зустрічаються і в природі. Прикладами фракталів можуть служити крона дерева, прикордонні і берегові лінії, пори в хлібі, дірки в деяких сортах сираі т.д. Поверхня Місяця, виявляється, поблизу виглядає так само, як і здалеку, тільки розміри кратерів інші. Земля - класичний приклад фрактального об'єкту. З космосу вона виглядає як куля. Якщо наближатися до неї, ми виявимо океани, континенти, побережжя і ланцюги гір. Розглядатимемо гори ближче стануть видні ще дрібніші деталі: шматочок землі на поверхні гори в своєму масштабі такий же складний і нерівний, як сама гора. І навіть ще сильніше збільшення покаже крихітні частинки грунту, кожна з яких сама є фрактальним об'єктом. Фрактальну структуру має також Всесвіт.
Для побудови геометричних фрактальних кривих використовуються рекурсивні алгоритми. Рекурсія використовується при вирішенні завдань, які можуть бути розкладені на декілька підзадач. Таким чином, застосування рекурсії доцільне при побудові фрактальних кривих, оскільки вони володіють такою властивістю як самоподібність. Алгоритми побудови фрактальних кривих рекурсивні за своєю природою, і їх набагато простіше вивчати в рекурсивному уявленні.
Алгоритм побудови кривої «Дракона Хартера-Хейтуея»
Для отримання фрактального об'єкту потрібно ввести правила побудови. Хай створюючим елементом будуть два рівні відрізки, сполучених під прямим кутом. У нульовому поколінні замінимо одиничний відрізок на цей створюючий елемент так, щоб кут був зверху. Можна сказати, що при такій заміні відбувається зсув середини ланки. При побудові наступних поколінь виконується правило: найперша зліва ланка замінюється на створюючий елемент так, щоб середина ланки зміщувалася ліворуч від напряму руху, а при заміні наступних ланок напряму зсуву середин відрізань повинні чергуватися. На рис.1 представлено декілька перших поколінь кривої, побудованої за вищеописаним принципом. Гранична фрактальна крива (при n прагнучому до нескінченності) називається драконом Хартера-хейтуея.
Рис. 1
У комп'ютерній графіці використання геометричних фракталів необхідне при отриманні зображень дерев, кущів, берегової лінії. Двомірні геометричні фрактали використовуються для створення об'ємних текстур (малюнка на поверхні об'єкту).
Крива дракона просто і витончено описується в так званій L-системі (запропонованою Лінденмауером). Про цю систему, яку також називають черепашачою. У L-системі дракон Хартера-Хейтуея описується за допомогою однієї “аксіоми” FX і двох “теорем”: +FX--FY+ і -FX++FY-. Кут повороту (який, нагадаємо, використовується в командах + і -) рівний .
Природні ж фрактали мають чітко обмежений інтервал масштабів, в якому зберігається принцип фрактальності і в якому вони проявляють свою фрактальну природу. У реальності будь-який фрактал має деякий мінімальний і максимальний масштаб довжини, при менших або більших значеннях цієї довжини самоподібність пропадає або порушується. Коли у формі фрактала з'являються елементи випадковості, говорять про "випадкові фрактали". Говорити про самоподібність в цих випадках можна, але тільки в статистичному сенсі, тобто коли не можна говорити про точні копії, а тільки про збіг статистичних характеристик (коли проводиться усереднювання по всіх статистично незалежних реалізаціях об'єкту).
Для наочності побудуємо один з фрактальних геометричних об'єктів, відомий під назвою кривої Коха. Візьмемо відрізок прямої одиничної довжини, назвемо його ініціатором () і розділимо на три рівні частини. Тепер середню частину викинемо і замінимо її двома такими ж відрізками, рівними 1/3 від первинного і сполученими один з одним і відрізками, що залишилися, отримавши, таким чином, друге наближення - ламану лінію, складену з чотирьох відрізань рівної довжини і назвемо її генератором (). Далі кожен прямий відрізок ламаної лінії, що вийшла, перетворюватимемо згідно цьому алгоритму. Повторюватимемо цю операцію до безкінечності, оскільки в математиці немає поняття межі подільності матерії. Кожного разу ми ділимо відрізок на 3 частини, середньої викидаємо і додаємо ламану лінію, внаслідок чого спочатку прямий ініціатор поступово перетворюється на все довшу витонченого характеру ламану лінію, як показано на малюнку.
Алгоритм побудови кривої Коха
Оскільки на кожному кроці кожен відрізок розбивався на три частини (а міг би і на чотири і більш), то у результаті отримуємо фігуру, названу Мандельбротом тріадний терагон (від грецького слова терос - чудовисько, дивне створення) Коха, довжина сторони якого е при кожному кроці зменшується, прагнучи в межі до нескінченно малої величини, але число таких сторін адекватно збільшується, прагнучи до нескінченно великої величини.
При цьому при кожному кроці довжина кривого Коха L(е) збільшується на третину і при нескінченному числі кроків довжина лінії нескінченна. На першому кроці алгоритму довжина відрізання 8 складає 1/3 від первинної. Тоді довжина кривого Коха обчислюється просто:
L= 4*1/3=4/3=1,33
На другому кроку алгоритму довжина елементарного відрізка е = 1/9, відповідно довжина кривої:
L = 16* 1 /9 = 16/9 = 1,777
На третьому кроку алгоритму е = 1/27. І довжина кривої:
L=64* 1/27=64/27=2,370370
Процес цей можна продовжити до безкінечності, відмітивши, що із збільшенням числа кроків n довжина елементарного відрізання е прагне до 0, а довжина кривої L прагне до нескінченності:
L = (4/3)n
е = (1/3)n
де n = 1,2,3... і з цих виразів отримуємо:
n = (1/1nз)*ln(1/е).
Підставляючи n отримаємо:
L= exp[n*ln(4/3)]=exp[(ln(4/3) /ln3]*ln(l/e)
Позначивши D=ln4/ln3, отримуємо:
L(е)=е1-D
З останнього співвідношення видно, що постійним показником при будь-якому кроці залишається тільки величина D, оскільки вона не залежить від масштабу вимірювання і є характеристикою лінії "крива Коха". Вона називається фрактальною розмірністю. З геометричної точки зору фрактальна розмірність є показником того, наскільки щільно ця лінія заповнює площину або простір. Аналогічним чином можна розрахувати фрактальну розмірність інших регулярних фракталів, наприклад, плоского регулярного фрактала - серветки Серпінського і множини інших, вигаданих математиками.
Текст програми:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Spin, Buttons, ExtCtrls, ComCtrls;
type
TForm1 = class(TForm)
PageControl1: TPageControl;
TabSheet2: TTabSheet;
Panel3: TPanel;
Image2: TPaintBox;
Panel4: TPanel;
SpeedButton2: TSpeedButton;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label13: TLabel;
SpinEdit2: TSpinEdit;
SpinEdit3: TSpinEdit;
SpinEdit4: TSpinEdit;
SpinEdit7: TSpinEdit;
TabSheet3: TTabSheet;
Panel6: TPanel;
Image3: TPaintBox;
Panel5: TPanel;
SpeedButton3: TSpeedButton;
Label8: TLabel;
SpinEdit6: TSpinEdit;
TabSheet4: TTabSheet;
Label6: TLabel;
Label7: TLabel;
Label9: TLabel;
Label10: TLabel;
procedure SpeedButton2Click(Sender: TObject);
procedure SpeedButton3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
rnd,x1,x2,x3,y1,y2,y3,FinalAge:integer;
c:char;
ot:string;
cc,AngleR,AngleL,StartAngle,ConCoef:Real;
implementation
{$R *.dfm}
{Treugolnik Serpinskogo}
procedure Line(x1,y1,x2,y2:real; C:TCanvas);
begin
c.Moveto(round(x1),round(y1));
c.lineto(round(x2),round(y2));
end;
Procedure drawtree(age,kx,ky,r:integer; naklon:real);
var
sx,sy:integer;
begin
r:=round(r-0.2*r);
inc(AGe);
if age=FinalAge then
begin
Line(kx,ky,round(kx + R * cos(naklon)), round(ky + R * sin(naklon)),form1.Image2.Canvas);
sx:=round(kx + R * cos(naklon));
sy:=round(ky + R * sin(naklon));
Line(sx,sy,round(sx + R * cos(naklon-angleL)), round(sy + R * sin(naklon-angleL)), form1.Image2.Canvas);
Line(sx,sy,round(sx + R * cos(naklon+angleR)), round(sy + R * sin(naklon+angleR)),form1.Image2.Canvas);
end
else
begin
sx:=round(kx + R * cos(naklon));
sy:=round(ky + R * sin(naklon));
drawtree(age,sx,sy,r+random(rnd),naklon-angleL);
drawtree(age,sx,sy,r+random(rnd),naklon+angleR);
Line(kx,ky,round(kx + R * cos(naklon)), round(ky + R * sin(naklon)),form1.Image2.Canvas);
end;
end;
procedure TForm1.SpeedButton2Click(Sender: TObject);
var
StartX,StartY,StartHeight:integer;
ot,tm:string;
i,j,iter,Total:longint;
StartH,StartM,StartS,StartS1,StopH,StopM,StopS,StopS1:word;
begin
ConCoef:=(pi/180);
AngleL:=spinedit3.value*ConCoef; AngleR:=Spinedit4.value*ConCoef;
StartHeight:=spinedit7.Value;
StartAngle:=3/2*pi;
StartX:=320;
StartY:=480;
Color:=15;
Image2.canvas.CleanupInstance;
image2.Canvas.Brush.Color:=clWhite;
image2.Canvas.rectangle(0,0,image2.Width,image2.Height);
if (spinedit2.Value>0) then
begin
FinalAge:=Spinedit2.Value;
drawtree(0,StartX,StartY,StartHeight,StartAngle);
end;
end;
Procedure DrawDragon(age:integer;x1,y1,x2,y2:real;n:real);
var
dx,dy,AC,CD,AD,cx,cy:real;
begin
inc(age);
if Age=FinalAge then
begin
line(x1,y1,x2,y2, form1.image3.canvas);
end
else
begin
cx:=(x2+x1)/2;
cy:=(y2+y1)/2;
AC:=sqrt(sqr(cx-x1)+sqr(cy-y1));
dx:=cx + AC * (cos(n+pi/2));
dy:=cy + AC * (sin(n+pi/2));
drawdragon(age,x1,y1,dx,dy,n+45*cc);
drawdragon(age,x2,y2,dx,dy,n+90*cc+45*cc);
end;
end;
procedure TForm1.SpeedButton3Click(Sender: TObject);
begin
x1:=145;
y1:=160;
x2:=560;
y2:=160;
CC:=(pi/180);
FinalAge:=spinedit6.Value;
image3.Canvas.Brush.Color:=clWhite;
image3.Canvas.rectangle(0,0,image3.Width,image3.Height);
DrawDragon(0,x1,y1,x2,y2,0);
end;
end.
Результат роботи програми:
Висновок: В даній розрахунковій роботі я ознайомився з поняттям фрактал та алгоритмами побудови фрактальних кривих. Реалізував алгоритм побудови фрактальної кривої під назвою Дракона Хартера-Хейтуея на мові програмування Delphi. Програма є простою у користуванні, а параметром для побудови є вибір покоління кривої. Також реалізував алгоритм побудови нескінченого дерева, в якому параметрами є покоління, кути нахилу гілок і висота.
22.11.2012 03:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора