Interpolační křivky. Interpolace pomocí spline křivky. f 1. f 2. f n. x... x 2

Interpolační křivky 

Interpolace pomocí spline křivky  dáno: n  1 bodů v rovině 

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

y fn f2 f0 f1

x0 Počítačová geometrie

x1

x2

...

xn

x Petra Surynková


Interpolace pomocí spline křivky  





nevýhodou polynomiální interpolace – změna některého z uzlů má vliv na celkový výsledný polynom už při relativně nízkém počtu uzlů – polynomy značně oscilují

rozdělení daného intervalu na několik podintervalů, na každém z nich konstruujeme obecně různý polynom – konstrukce po částech polynomiální funkce (lze použít i u parametricky popsaných křivek)

Počítačová geometrie

Petra Surynková


Interpolace pomocí spline křivky  

v bodech x0 , x1 , x2 ...xn známe funkční hodnoty y0 , y1 , y2 ... yn dělení intervalu a, b

a  x0  x1  x2  ...  xn  b 

označme délku i-tého intervalu xi 1 , xi

hi  xi  xi 1 



hledáme po částech polynomiální interpolant – S ( x) - tzv. interpolační spline na každém intervalu xi 1 , xi je S ( x) polynom Si ( x)


Petra Surynková


Interpolace pomocí spline křivky  Spline stupně k - S ( x) 

splňuje interpolační podmínky

S  xi   f i , i  0,1...n 

na každém intervalu

xi1 , xi

Si ( x) - je polynom k-tého stupně 

S ( x) má spojité derivace až do řádu (k-1)


Petra Surynková


Interpolace pomocí spline křivky  Kubický interpolační spline S ( x) 

splňuje interpolační podmínky

S  xi   fi , i  0,1...n 

na každém intervalu

xi1 , xi

Si ( x) - je polynom třetího stupně 

platí

Si ( xi )  Si 1 ( xi ), i  1, 2,..., n  1 Si( xi )  Si1 ( xi ), i  1, 2,..., n  1 Si( xi )  Si1 ( xi ), i  1, 2,..., n  1


Petra Surynková


Interpolace pomocí spline křivky  Kubický interpolační spline S ( x) 

dva volné parametry – přidání podmínek, nejčastěji:

S   x0   S   xn   0 přirozený kubický spline


Petra Surynková


Interpolace pomocí spline křivky 

Konstrukce přirozeného kubického splinu

S ( x)

yi



Si ( x ) 

yi 1 xi 1

na každém intervalu xi 1 , xi je spline popsán polynomem třetího stupně polynom budeme hledat v následujícím tvaru

xi Si ( x)  ai  bi  x  xi 1   ci  x  xi 1   di  x  xi 1  2

3

i  1,..., n Počítačová geometrie

Petra Surynková



Konstrukce přirozeného kubického splinu

Si ( x)  ai  bi  x  xi 1   ci  x  xi 1   di  x  xi 1  2

i  1,..., n 

hledáme koeficienty



označme

3

(1)

ai , bi , ci , di hi  xi  xi 1


Petra Surynková



Konstrukce přirozeného kubického splinu 

dosazení

xi 1

do (1)

Si ( xi1 )  ai  fi1 

podmínka spojitosti

- vztahy pro koeficienty

ai

Si1 ( xi1 )  Si ( xi1 ), i  2,..., n

Si1 ( x)  ai1  bi1  x  xi2   ci1  x  xi2   di1  x  xi2  2

Si ( x)  ai  bi  x  xi 1   ci  x  xi 1   di  x  xi 1  2

3

3

Si1 ( xi1 )  ai1  bi1hi1  ci1hi21  di1hi31  fi1  Si ( xi1 ) (2) Počítačová geometrie

Petra Surynková




podmínka spojitosti první derivace

Si1 ( xi1 )  Si( xi1 ),, i  2,..., n

Si1 ( x)  bi1  2ci1  x  xi2   3di1  x  xi2  Si( x)  bi  2ci  x  xi 1   3di  x  xi 1 

2

2

Si1 ( xi1 )  bi1  2ci1hi1  3di1hi21  bi  Si( xi1 )


(3)

Petra Surynková




podmínka spojitosti druhé derivace

Si1 ( xi1 )  Si( xi1 ), i  2,..., n

Si1 ( x)  2ci1  6di1  x  xi2  Si( x)  2ci  6di  x  xi 1 

Si1 ( xi1 )  2ci1  6di1hi1  2ci  Si( xi1 )


(4)

Petra Surynková




ze vztahu (4) vyjádříme

2ci  2ci 1 ci  ci 1 di1   6hi1 3hi1 

(5)

a dosadíme do (2)

ci  ci1 3 ai1  bi1hi1  c h  hi1  fi1 3hi1 2 i 1 i 1



a vyjádříme

fi 1  fi 2 hi 1 bi1    ci  2ci1  hi1 3 Počítačová geometrie

(6) Petra Surynková




do (3) dosadíme (5) a (6)

fi 1  fi 2 hi 1 ci  ci 1 2  hi 1   ci  2ci1   2ci1hi1  3 hi 1 3 3hi 1 fi  fi 1 hi    ci 1  2ci  hi 3



(n-1) rovnic pro (n-1) neznámých


ci Petra Surynková




podmínka pro přirozený kubický spline

S   x0   S   xn   0 S1 x0   0 S1 x   2c1  6d1  x  x0  S1 x0   2c1  0 c1  0 Počítačová geometrie

Petra Surynková




v poslední rovnici soustavy se objeví člen

cn1

Sn  xn   0 Sn  x   2cn  6d n  x  xn1  Sn  xn   2cn  6d n ( xn  xn1 )  2cn  6d n hn

2cn  6dn hn  0 cn dn   3hn Počítačová geometrie

ci  ci1  3di1hi1 cn1  cn  3dn hn  0 Sn  xn  cn1  2

plyne ze (4)

cn1  0 Petra Surynková




(n+1) rovnic pro (n+1) neznámých



maticově

Ax  b

ci

0 0 ... 0 1  h 2h  h   h 0 ... 1 2 2  1  h2 2  h2  h3  h3 0 ... 0   A ...   hn1 2  hn1  hn  hn     ... 0 0 1 0   Počítačová geometrie

Petra Surynková







maticově

Ax  b

 c1   c   2   .  x .   .    c  n  c   n1  Počítačová geometrie

ci

0    a a a a    3 3 2  2 1   h1     h2   .   b .    .     a  a a  a  3  n1 n  n n1     hn hn1     0   Petra Surynková







maticově



soustava je jednoznačně řešitelná



ostatní koeficienty určíme ze vztahů (5), (6) a ze vztahů pro koeficienty ai



Ax  b

ci

lze ukázat, že existuje jediný přirozený kubický spline, který interpoluje zadaná data


Petra Surynková


Fergusonovy kubiky 

nejznámější interpolační křivky používané v počítačové grafice



určení 

dvěma řídícími body

P0 , P1

a 

 

dvěma tečnými vektory v nich

P0, P1

řídící body určují polohu křivky (křivka jimi prochází) směr a velikost tečných vektorů určuje míru vyklenutí křivky 



čím je velikost tečného vektoru větší, tím více se k němu křivka přimyká jsou-li oba vektory nulové, potom křivka degeneruje na úsečku P0 , P1


Petra Surynková



předpis pro výpočet Fergusonovy kubiky

  Q(t )  P0 F1 (t )  PF 1 2 (t )  P0 F3 (t )  PF 1 4 (t ) , kde F1 (t ), F2 (t ), F3 (t ), F4 (t ) jsou tzv. kubické Hermitovské polynomy F1 (t )  2t 3  3t 2  1 F2 (t )  2t 3  3t 2

t  0,1

F3 (t )  t 3  2t 2  t F4 (t )  t 3  t 2 Počítačová geometrie

Petra Surynková



předpis - maticově

 2 2 1 1   P0   3 3 2 1   P   1  Q (t )  T   0 0 1 0   P0   1 0 0 0   P   1  T  t 3 t 2


t 1

t  0,1

Petra Surynková


Fergusonovy kubiky

P0 P1

P0

P1

různé tvary Fergusonovy kubiky


Petra Surynková



výhoda  snadné navazování Fergusonových kubik 0  spojitost C  totožnost posledního bodu jednoho segmentu a prvního bodu dalšího segmentu 

spojitost C

1

 zaručena identitou tečných vektorů v uzlu


Petra Surynková

Interpolační křivky. Interpolace pomocí spline křivky. f 1. f 2. f n. x... x 2

Recommend Documents