Итерации

Ваня Милева Последна промяна на 27 януари 2015 в 17:28 111274 0

Фракталът Дървото на Питагор
Фракталът Дървото на Питагор

Въведение в понятието "итерация"

Изобразяването на фрактали е тясно свързано с програмирането. За хора, които имат дори бегла представа от програмиране, тези понятия са ясни. За другите:

Итерация в програмирането е такава организация на обработката на данни, при която действието се повтаря няколко пъти, без това да доведе до положение, при което функцията да извика сама себе си (това вече е рекурсия).

Когато някои действия трябва да се повторят няколко пъти, се използват цикъл. Най-лесно ще ви стане с някой пример

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. Итерация с формули — включва няколко начина за създаване на фрактали, повтаряйки някаква математическа формула или няколко формули.

Съществуват и други видове итерации. Например, фрактали може да се създават като се сгъва хартия. Обаче същите тези фрактали могат да се образуват и с някои от изброените стандартни методи.

Заместваща итерация

Започваме с фигура, наречена основа. След това всяка част от основата заместваме с друга фигура, наречена мотив. Извършваме това заместване безкрайно количество пъти, докато завършим фрактала.

Например, да опитаме да направим фрактал с тази основа итерация  и мотив:  итерация
Von Koch curve
1 2 3 4 5 6

Започвайки с триъгълник, заменяме всяка негова страна с мотива. Отново заменяме всяка от 12-те отсечки с мотива и продължаваме процеса. Накрая получаваме фрактал, наречен Снежинката на Кох. Може да разгледате развитието на фрактала за всеки етап като минете с мишката по бутоните.

Тази фигура е един от първите фрактали изследвани от учените. Тя се получава от три еднакви криви на Кох:

Play
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
Axiom F - - F - - F
F = F + F - - F + F }

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 -> FF

F= G[+F][-F]GF
G = GG

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

Системи Итеративни Функции (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УК!
Ако вече имате регистрация, натиснете ТУК!

Няма коментари към тази новина !