Въведение в понятието "итерация"
Изобразяването на фрактали е тясно свързано с програмирането. За хора, които имат дори бегла представа от програмиране, тези понятия са ясни. За другите:
Итерация в програмирането е такава организация на обработката на данни, при която действието се повтаря няколко пъти, без това да доведе до положение, при което функцията да извика сама себе си (това вече е рекурсия).
Когато някои действия трябва да се повторят няколко пъти, се използват цикъл. Най-лесно ще ви стане с някой пример
|
n=1; for i=0 to i<5 step=1 {n=n+i;} |
Този прост фрагмент от неопределен език за програмиране (принципът е един и същ, само синтаксисът е различен) може да се тълкува така: n приема начална стойност 1. После влиза в цикъл, който се определя от параметъра i с начална стойност 0 , като след всяка стъпка увеличава стойността си с 1, докато i остава по-малко от 5, в случая. Действието в тялото на цикъла върху операцията n=n+i, за всяка една стъпка от цикъла се нарича всъщност итерация. Трябва да се отбележи, че изразите в програмирането се извършват от дясно наляво. |
|
Резултатът от този прост пример за n ще е: n=1; n=2; n=3; n=4; |
Най-общо, итерация може да се преведе като "повторение".
Във всеки фрактал има безкрайно повтаряща се форма. При създаване такъв фрактал, най-простият начин се състои в това, да се повторят няколко действия, които създават тази форма. Вместо думата "повторение" използваме "итерация". Фактически всеки фрактал може да бъде създаден с итерации на някакво правило. За да се създаде истински фрактал, трябва да се извърши итерацията безкрайно количество пъти. Но бихме могли да я изпълним краен брой пъти, но достатъчно много, за да си създадем представа за "истинския" фрактал. Естествено с помощта на компютър. Увеличението на броя на итерациите прави фракталите по-точни.
Съществуват три основни вида итерации:
1. Заместваща итерация - създава фрактали, заменяйки едни геометрични фигури с други.
2. Итерация IFS - създава фрактали, прилагайки геометрични преобразувания (тип завъртане и отражение).
3. Итерация с формули — включва няколко начина за създаване на фрактали, повтаряйки някаква математическа формула или няколко формули.
Съществуват и други видове итерации. Например, фрактали може да се създават като се сгъва хартия. Обаче същите тези фрактали могат да се образуват и с някои от изброените стандартни методи.
Заместваща итерация
Започваме с фигура, наречена основа. След това всяка част от основата заместваме с друга фигура, наречена мотив. Извършваме това заместване безкрайно количество пъти, докато завършим фрактала.
| Например, да опитаме да направим фрактал | с тази основа |  |
и мотив: |  |
 |
|||||
| 1 | 2 | 3 | 4 | 5 | 6 |
Започвайки с триъгълник, заменяме всяка негова страна с мотива. Отново заменяме всяка от 12-те отсечки с мотива и продължаваме процеса. Накрая получаваме фрактал, наречен Снежинката на Кох. Може да разгледате развитието на фрактала за всеки етап като минете с мишката по бутоните.
Тази фигура е един от първите фрактали изследвани от учените. Тя се получава от три еднакви криви на Кох:
 |
|||
| 1 | 2 | 3 | 4 |
Кривата на Кох се появява за първи път в статията на шведския математик Нилс Фабиан Хелге фон Кох през 1904. Тази крива е замислена като пример за непрекъсната линия, към която не може да се прекара допирателна във всяка точка. Линии с подобни свойства са били известни и преди (Карл Вайерщрас, 1872 г.), но кривата на Кох е забележителна с простотата си.
С различни основи, мотиви и начини на заместване на мотивите могат да се получат много разнообразни фрактали.
L-системи
Заместващата итерация е много проста. Но за компютър, не е достатъчно да имаш изображението на основата и мотива. Необходим е ясен и точен начин за съхранение на данните за фракталите, който да позволява да се създават прости алгоритми за изчертаване на фрактали.
Един добър и прост начин са L-системите. Разработени са от А. Линденмайер ("L" в думата "L-система" ). Те са съставени от ъгъл, аксиома и поне едно правило. Аксиома наричаме началната форма (основа), която ще се използва в процеса на създаване на фрактала. Правилата указват, какви символи в аксиомата трябва да бъдат заменени с други символи.
| СИМВОЛИ | ||||||
| Общи символи | Сложни символи | Символи за цветяване | ||||
| F | Движение напред, със следа | @n | Да се умножи дължината на отсечката на n | Cn | Да се установи цвят номер n | |
| G | Движение напред, без следа | I | Пред число означава делене вместо умножение | <n | Да се намали номера на цвета с n | |
| + | Завъртане против часовата стрелка | Q | Пред число дава квадратен корен | >n | Да се увеличи номера на цвета с n | |
| - | Завъртане по часовата стрелка | ! | Променя знака от + на - | |||
| | | Завъртане на 180 о | [ | Да се вкара сегашната позицията на курсора в паметта | |||
| ] | Да се извади последната записана позиция на курсора от паметта | |||||
Същността на L-кодирането е проста:
Представете си програмируемо устройство, от писец, контролиращ механизъм и лист хартия. Управляващият механизъм на писеца има набор от няколко команди:
- да смъкне писалката върху хартията
- да начертае отсечка с дадена дължина с направление на текущата ориентация на писалката (команда F).
- да промени ориентацията на писалка спрямо текущата на даден относителен ъгъл спрямо часовниковата стрелка или обратно на часовниковата стрелка (команда + и -).
- да запомни (вкарва в стека) текущото състояние (команда [) и да си спомни (да извади от стека) предварително запаметено състояние (команда ]).
Под състояние се разбират трите числа (x, y, a), където x и y са координатите на писалката, а a е ъгълът, който определя посоката на ориентация на писалката. По този начин, задавайки някаква първоначална посока a0 , ъгъл на относително завъртане от 900 и дължината на отсечката, като се използва последователността от команди, F + F + F + F, можем да начертаем квадрат. Ако определим относителния ъгъл на завъртане на 600, използвайки серията от команди F ++ F ++ F ще начертаем един равностранен триъгълник.
| Ето още един пример, Снежинката на Кох, Тя използва следната | основа | |
и мотив: | |
Използвайки L-система, можем да запишем Снежинката на Кох по следния начин:
|
Koch { Angle 60 |
L-системата започва с названието, следва скоба ; това е ъгъла, на който се отклонява линията на фрактала; три страни с две завъртания по часовата стрелка на 120 градуса; всяка страна се заменя с мотива (F +F- -F + F); скобата означава повторение |
Повечето фрактали с фрактална размерност от 0 до 2 могат да бъдат изразени като се използват L-системи. С комбинация от няколко символа и правила могат да се създадат много сложни фрактали. Такива L-системи се използват, за да се създават реалистични модели на растения.
 |
 |
 |
| F = FF-[-F+F+F]+[+F-F-F] |
X -> F-[[X]+X]+F[+FX]-X |
F= G[+F][-F]GF |
Възможно е да се постигне и по-голям реализъм като се внесе параметър, добавящ случайни числа. Колкото е по-голям диапазона им, толкова формите ще изглеждат по-естествени и далече от симетрията.
 |
 |
 |
 |
 |
 |
Системи Итеративни Функции (Iterated Functions System - IFS)
IFS (итеративни функционални системи) представят още един начин за създаване на фрактали. Този метод е основан на точка или фигура, която се заменя с няколко по-малки фигури.
Например, съществува много прост начин за изчертаване на Триъгълника на Серпински. Започвайки с триъгълник, заменяме го с три малки триъгълници: Продължавайки този процес на итерация, ние заменяме всеки от тези три триъгълника с други триъгълници и продължаваме много пъти:
докато стигнем до:
Замяната на една форма с друга форма се нарича геометрично преобразование .
В горния пример има два вида преобразувания: транслация (движение на триъгълниците) и изменение на размера на триъгълниците.
Третият вид преобразование е въртенето. То може да се използва за създаване на фрактали, в които самоподобните части са разместени под различни ъгли. Например, за да се създаде реалистичен модел на дърво, има нужда от въртенето за клоните.
Другите видове преобразувания, тип огледално отражение и инверсия могат да се използват за създаване на огромно разнообразие от фрактали. IFS значително облекчават алгоритмите за изчертаване на фракталите. За двумерни фрактали всичко, което трябва да сложите в паметта на компютъра, е списък с всички преобразувания с 6 параметри за всяко.
X' = A*X + B*Y + C
Y' = D*X + E*Y + F
- Хоризонтално движение
- Вертикално движение
- Въртене около вертикалната ос на изображението
- Въртене около хоризонталната ос на изображението
- Мащабиране по вертикалната ос на изображението
- Мащабиране по хоризонталната ос на изображението.
За 3-мерните фрактали са необходими допълнително още 3 параметъра за третата ос.
Повече подробности - в темата: Системи Итеративни Функции (Iterated Functions System - IFS)
Формулна итерация
Формулната итерация е най-простия вид итерация, но е най-важния и дава най-сложни резултати. Алгебричните фрактали се построяват чрез формулна итерация, т.е. чрез математически формули. Ще ги разгледаме в темата за Алгебричните фрактали.
Продължение:
Основни понятия и лексика
- Фрактали
- дърво на Питагор
- снежинка на Кох
- крива на Кох
- триъгълник на Серпински
- Итерация
- в програмирането
- в построяването на фрактали
- Заместваща итерация
- L-системи
- Итерация IFS
- Итерация с формули
- Нилс Фабиан Хелге фон Кох
- Вацлав Франциск Серпински
- Беноа Манделброт
Източници:
Фрактальная геометрия природы, Мандельброт Б.
Фрактальный рост, Л.М. Сандер (doc)
Принцип Кюри и ограниченная диффузией агрегация © Л.М. Мартюшев, Л.Г. Горбич
Коментари
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!
Няма коментари към тази новина !
Последни коментари