základním prvkem teorie křivek v počítačové grafice křivky polynomiální n

Modelování křivek 

základním prvkem teorie křivek v počítačové grafice – křivky polynomiální Q(t )  a0  a1t  ...  ant n



polynomiální křivky   



můžeme snadno vyčíslit snadno diferencovatelné lze z nich skládat křivky po částech polynomiální – tj. takové křivky, jejichž segmenty jsou polynomiálními křivkami nejčastěji používané – křivky třetího stupně (kubiky)    

dostatečně široká škála tvarů nenáročný výpočet lze s nimi dobře manipulovat 2 je možné zaručit spojitost C

Počítačová geometrie

Petra Surynková

Modelování křivek 

polynomiální křivky 



křivky vyšších stupňů mohou způsobovat nežádoucí vlnění a oscilace a jsou náročnější na výpočet

modelování  

definováno několik řídících bodů (řídící polygon) určíme průběh křivky  

je možné zadávat tečné vektory křivky je možné klást podmínky na spojitost a hladkost navázaní

Počítačová geometrie

Petra Surynková

Modelování křivek 

parametricky zadaná kubika v prostoru

x(t )  axt 3  bxt 2  cxt  d x y (t )  a y t 3  by t 2  c y t  d y z (t )  az t 3  bz t 2  cz t  d z  

dvanáct koeficientů ovládání tvaru křivky pomocí jednotlivých koeficientů není intuitivní, ze změny koeficientu nelze jednoduše odhadnout změnu tvaru křivky 

při definici křivek s určitými vlastnostmi – výhodné oddělit charakteristiky, které jsou pro danou křivku individuální, od vlastností, které jsou společné pro všechny křivky modelované shodným způsobem

Počítačová geometrie

Petra Surynková

Modelování křivek 

maticově

Q(t )  TC   t 3 t 2 C  MG Q(t )  TC  TMG

Q(t )  TC   t 3 t 2

Počítačová geometrie

 ax b x t 1   cx   dx

 m11 m12 m m22 21  t 1  m31 m32   m41 m42

ay by cy dy

m13 m23 m33 m43

az  bz   cz   dz  m14  G1  m24  G2    m34  G3    m44   G4  Petra Surynková

Modelování křivek 

existují dva základní způsoby interpretace řídících bodů  

interpolace aproximace

interpolační křivka – prochází danými body

Počítačová geometrie

aproximační křivka – neprochází danými body, řídící body určují tvar křivky

Petra Surynková

Modelování křivek 

Nejčastěji požadované vlastnosti 

Invariance k afinním transformacím a projekcím, která zaručuje, že například rotace řídicího polygonu a následné generování křivky má stejný výsledek, jako rotace každého bodu z vygenerované křivky



Vlastnost konvexní obálky 



silná podmínka - celá křivka leží v konvexní obálce všech svých řídicích bodů slabá podmínka - část křivky leží v konvexní obálce některých řídicích bodů (typicky segment - v obálce svého generujícího polygonu)



Lokalita změn - změnou polohy (u racionálních křivek i váhy) řídicího bodu se mění jen část křivky, nikoli křivka celá



Křivka může procházet krajními body svého řídicího polygonu

Počítačová geometrie

Petra Surynková

Interpolace polynomem 

Formulace problému   

dáno: tabulka hodnot  xi , f i  , xi , f i  , i  0,.., n, n  pro funkci f definovanou na uzavřeném intervalu [ a, b] uvažujme dělení intervalu a  x0  x1  x2 ...  xn  b, n   hledáme funkci z jisté třídy, která nabývá v zadaných bodech stejných hodnot – nejčastěji polynom, trigonometrický polynom, racionální funkce, exponenciální funkce y fn

f2 f0 f1

Počítačová geometrie

fi  f  xi 

x0

x1

x2

...

xn

x

Petra Surynková

Interpolace polynomem 

Formulace problému  dáno: n  1 bodů v rovině 

úkol: nalézt takovou křivku, která danými body prochází 

y fn

řešení: 

f2 f0 f1

nalezení polynomiální funkce f(x) stupně nejvýše n, která v zadaných bodech x0  x1  x2 ...  xn nabývá hodnot

f0  f ( x0 ), f1  f ( x1 ), f 2  f ( x2 )... f n  f ( xn ) 

x0

x1

x2

...

xn

x

interpolace pomocí spline křivky, která se skládá z n dílčích interpolačních polynomů, které platí jako náhrada v dílčích intervalech

x0 , x1 , x2 , x3 ... xn1 , xn Počítačová geometrie

Petra Surynková

Interpolace polynomem  

hledáme polynom f ( x)  a0  a1 x  a2 x 2 ...  an x n v bodech x0 , x1 , x2 ...xn známe funkční hodnoty f 0 , f1 , f 2 ... f n  body x0 , x1 , x2 ...xn tzv. uzly, které jsou navzájem různé



soustava

n  1 lineárních rovnic pro n  1 neznámých

f 0  f ( x0 )  a0  a1 x0  a2 x02 ...  an x0n f1  f ( x1 )  a0  a1 x1  a2 x12 ...  an x1n f 2  f ( x2 )  a0  a1 x2  a2 x22 ...  an x2n

zapsat maticově

... f n  f ( xn )  a0  a1 xn  a2 xn2 ...  an xnn Počítačová geometrie

Petra Surynková

Interpolace polynomem 

metoda neurčitých koeficientů – řešení soustavy lineárních rovnic pro ai , i  1,2.., n

f 0  f ( x0 )  a0  a1 x0  a2 x02 ...  an x0n f1  f ( x1 )  a0  a1 x1  a2 x12 ...  an x1n f 2  f ( x2 )  a0  a1 x2  a2 x22 ...  an x2n ... f n  f ( xn )  a0  a1 xn  a2 xn2 ...  an xnn 

Věta: Úloha polynomické interpolace je jednoznačně řešitelná. 

pro určení interpolačního polynomu existuje mnoho postupů, všechny postupy určí stejný polynom

Počítačová geometrie

Petra Surynková

Interpolace polynomem 

Jiné techniky konstrukce interpolačního polynomu (explicitní formule) 

Lagrangeův interpolační polynom (Lagrangeův tvar interpolačního polynomu) n

Ln ( x)   li ( x) f  xi  , kde li ( x)  i 0

n

x  xj

j 0,i  j

xi  x j



xi  x j  0 

pro x0 , x1 , x2 ...xn navzájem různé uzly existuje právě jeden interpolační polynom Ln ( x) stupně nejvýše n 

důkaz

Počítačová geometrie

Petra Surynková

Interpolační křivky 

Lagrangeův interpolační polynom (Lagrangeův tvar interpolačního polynomu) 

vlastnosti 



li ( x) - Lagrangeovy polynomy platí

li ( x)

- jsou polynomy nejvýše stupně n

li ( x j )   ij 

Počítačová geometrie

0,i  j 1,i  j

Petra Surynková

Interpolační křivky 

Položme

n1 ( x)  ( x  x0 )( x  x1 )...( x  xn ) 

potom platí

li ( x) 

Počítačová geometrie

n1 ( x) ( x  xi ) 

n

 (x  x )

j 0,i  j

i

j

Petra Surynková

Interpolační křivky 

Chyba Lagrangeovy interpolace n1

Nechť f  C ( I ), kde I je nejmenší interval obsahující x0 , x1 ,...xn , x a x0 , x1 ,...xn jsou navzájem různé uzly. Nechť Ln ( x) je Lagrangeův interpolační polynom pro funkci f , pak existuje   I

f  x*   Ln  x*  

f ( n1)    n1  x*  (n  1)!

- chyba Lagrangeovy interpolace v bodě

Počítačová geometrie

*

x*

Petra Surynková

Interpolační křivky 

Lagrangeova interpolace 

výhody  



explicitní zadání význam především při teoretickém zkoumání vlastností interpolačních polynomů

nevýhody 



 

při větším počtu bodů (vyšší stupeň polynomu) – značné ,,rozkmitání‘‘ křivky u krajních bodů změna nebo přidání bodu – vše se musí znovu přepočítat velký počet operací neplatí – čím více bodů je zadáno, tím přesnější funkci dostaneme

Počítačová geometrie

Petra Surynková

Interpolační křivky 

Newtonův interpolační polynom (Newtonův tvar interpolačního polynomu)  v bodech x0 , x1 , x2 ...xn známe funkční hodnoty y0 , y1 , y2 ... yn i 1

n

N n ( x)   ni ( x)  ai

, kde

i 0



ni ( x)    x  x j  j 0

poměrné diference – nultého až n-tého řádu

 y0   y0

y1  y0  y1 , y0   x1  x0

 y2 , y1 , y0  Počítačová geometrie

 yn , yn1 ,..., y0 

yn , yn1 ,..., y1    yn1 ,..., y1 , y0    xn  x0

y2 , y1    y1 , y0    x2  x0

Petra Surynková

Interpolační křivky 

Newtonův interpolační polynom (Newtonův tvar interpolačního polynomu)

ai :  yi , yi1 ,..., y0  N n ( x)   y0    y1 , y0    x  x0     y2 , y1 , y0    x  x0   x  x1   ... ...   yn , yn1 ,..., y0    x  x0   x  x1  ... x  xn1  

nejprve se spočítá tabulka poměrných diferencí

Počítačová geometrie

Petra Surynková

Interpolační křivky 

Newtonova interpolace 

výhody  





snadná úprava polynomu výpočetně méně náročné přidat další bod (oproti Lagrangeově interpolaci) – některé výpočty zůstanou beze změny (předchozí koeficienty ak se nemění) častější použití

nevýhody 

při větším počtu bodů (vyšší stupeň polynomu) – značné ,,rozkmitání‘‘ křivky u krajních bodů (stejné)

Počítačová geometrie

Petra Surynková