Интерполация с криви на Оверхаузер



Дата31.12.2017
Размер48.77 Kb.
Интерполация с криви на Оверхаузер
Това е интерполацията с параметрични криви.Множеството от точки,което се интерполира (и за което се предполага че са сражнително отдалечени една от друга) се разделя на групи от по три съседни точки,като всяка точка участва точно в три различни групи.За всяка от тези групи които се припокриват се съставя параметрична квадратична крива,която ги интерполира.Получените квадратични криви-сегменти се комбинират в една общта крива чрез линейна функция спрямо параметрите на сегментите.Тази линейна функциа се избира такава че да е единица в средата на всеки сегмент и 0 в краищата му.
Ще разгледаме две застъпващи се групи от точки КLM и LMN.Квадратичните сегменти които интерполират тези две групи са:

x(s)= a11+b11s+c11s2

q(s): 0<=s<=1 в КLM

y(s)= a12+b12s+c12s2’


като s=0 в т.К, s=0,5 в т.L и s=1 в т.М и

x(t)= a21+b21t+c21t2

r(t): 0<=t<=1 в LMN

y(t)= a22+b22t+c22s2’


като t=0 в т.L, s=0,5 в т.M и t=1 в т.N.
Резултатната крива от смесването на горните два сегмента в интервала между точките L и M ще се задава параметрично така:

x=a(a11+b11s+c11s2) + ( a21+b21t+c21t2)

y=a (a12+b12s+c12s2’)+ (a22+b22t+c22s2’)
Параметрите на джата сегмента са свързани с равенството s=t+0.5, а коефицентите можем да определим от условията:

в т.L  = 1 =0

в т.M  = 0 =1

Да изразим  и  чрез параметъра t (защото изискжането беше да функциите на смесване да бъдат линейни по отнишение на параметрите на сегментите).В участъка между точките L и M от кривата t се мени в интервала [0.1/2],което означава че стойностите на коефицентите са:

=1-2t = 2t.

Ясно е че в участъците между парвата и втората точки,както и между последната и предпоследната точки от множеството няма смесване на сегменти.Във всички останали участъци резултатната крива на Оверхаузер е от трета степен.

Предимство на тази форма е, че промяна на някоя от интерполираните точки води до промяна само на ограничена част от кривата.Кривата на Оверхаузер има гарантирана непрекаснатост само на парвата производна,но това е достатаяно.

Алгоритъм на порциите

Ако разгледаме една отсечка в тази част от 1-ви квадрант,в която x>y, ще видим че растерният и образ се състои от поредица от хоризонтални участъци.Тези хоризонтални участъци Брезенхам нарича порции.Един друг подход към растеризирането на отсечка е да се получат всички такива порции като на всяка итерация в алгоритъма се намира съответната поредица от пиксели,а не само един единствен.

Ще разгледаме отсечка от първи октант с начало точката (0,0) и крайна точка(H,V).Алгоритъма на средната точка на практика решава системата от H+1 неравенства:

y- 1 < V .x <=y + 1 x=0,1,2,….H


2 H 2


относно неизвестните y.Нека да модифицираме тази система като я решим относно x.Тя ще се преобразува в система от V+1 неравенства спрямо x:
H (2y-1) H (2y+1), y=0,1,2,….V,

2V 2V


което може да се запише и като:

2H y – H < x<= 2H y + H y=0,1,2,….V

2V 2V 2V 2V


Нека да представим дробите в горната система от неравенства като цяла част и остатък по модул 2V, за да можем да изжаршим нейното решаване в цели числа.Ще получим следното:



H = c0 + r­0 , 2H = c1 + r1

2V 2V 2V (H,V)
























































































































































































((0,0)


Ако разгледаме фигурата ще видим че тази x за които за които десните неравенства в тази система се превръщат в равенства са точно крайните десни пиксели във всяка хоризонтална порция.Те често се наричат преходни пиксели.Растеризирането ще изваршим като на всяка итерация намираме преходния пиксел в съответния ред.Можем да че най-малкото x,което удоволетворявя неравенствата за y=j+1,се получава чрез прибавяне на единица към x – координатата на преьодния пиксел в неравенството за y=j.

Сега ще разгледаме кога се получава равенство в дясното неравенсто за y=0.При решаване на уравнението

x= c1y + c0 + r1y+r0

2V

в цели числа ще видим че първия преходен пиксел има координати точно(c0,0).



Всеки следващ преходен пиксел може да бъде получен използвайки същото уравнение след предварително изчисляване на коефицентите в целочисленото разлагане .За целта е необходимо само да въведем една променлива,в която да съхраняваме стойността на числителя r1y+r0 на дробта в споменатото уравнение и да коригираме циалата част на x всеки пат когато тази дроб стане по-голяма от единица.



База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница