Spline

Spline használata egy grafikus programban

Spline-on szakaszosan parametrikus polinomokkal leírt görbét értünk. Az n-edfokú spline-ban legfeljebb n-edfokú polinomszakaszok csatlakoznak egymáshoz úgy, hogy nemcsak a folytonosságot, hanem az n-1-szeri differenciálhatóságot is biztosítják.

A szakaszonként lineáris spline-t lineáris, a másodfokút kvadratikus, és a harmadfokút kubikus spline-nak is nevezik. A gyakorlati alkalmazásokban leginkább a kubikus spline-okat használják. Néha előfordulnak kvadratikus, és ötödfokú spline-ok is.

A számítógéppel segített tervezésben (CAD) és a számítógépes grafikában azért használják őket előszeretettel, mert egyszerű és interaktív szerkesztést tesznek lehetővé, pontosságuk, stabilitásuk és könnyű illeszthetőségük révén igen komplex formákat lehet velük jól közelíteni. A spline angol szó (kiejtése: szplájn), és nevét arról a rugalmasan hajlítható vonalzóról kapta, melyet hajóépítők és rajzolók használtak korábban.

Általában

A spline-okat 1946-ban először Isaac Jacob Schoenberg említette meg.

Spline-okat többnyire interpolációra, approximációra és ábrázolásra használnak. Az így nyert görbék és felületek olyan simák, amennyire csak lehetnek, nincsenek rajtuk nagyobb kilengések, és rugalmasabban módosíthatók, mint a polinomok. Egyes típusaik szakaszonként változtathatók úgy, hogy közben a görbe nagyobb része megmarad.

A spline név a hajóépítésből ered; ott az építéshez használt hajlékony vonalzót nevezték spline-nak.

Peremfeltételek

A spline görbe nem egyértelmű peremfeltételek nélkül. Ezek a feltételek periodikus esetben természetesek, hiszen a görbének simán kell záródnia. Egy másik természetes feltétel, hogy egy elég sokadik derivált nulla.

Nem záródó görbék illesztéséhez két módszer terjedt el: a körérintős és a tükrözési eljárás. Az így megadott érintők szolgáltatják az induló deriváltat.

Jelölje az első három pontot P₁, P₂, P₃. A körérintős eljárásban kört illesztenek az első három P₁, P₂, P₃ pontra azok síkjában. Veszik a kiindulási pontból a körhöz húzott érintőt; ez megadja az induló érintő irányát. Ennek hossza megegyezik a P₁P₂ szakasz hosszával. Ha a három pont egy egyenesre esik, akkor az érintő megegyezik az első pontból a második pontba mutató vektorral.

A tükörérintős eljárásban a P₁P₂ vektor egyenesére tükrözött P₁P₃ vektor iránya adja meg az érintő irányát, aminek hossza megint csak P₁P₂.

Hasonlóan adják meg az utolsó érintőt is.

A két módszer különböző eredményt ad. Ritkább pontsorozatok esetén ez jól látszik; elég sűrű pontsorozatok esetén a különbség szemmel nem látható.

Az egyes koordinátákat külön-külön számítják, és csak a végén teszik össze ismét őket.

Elsőfokú spline

Legyen x₁, x₂, … rendezett pontsorozat. Ekkor az interpoláláshoz használt bázisfüggvények alakja:

$\mathrm{u_i}(x)=\frac{x-x_i}{x_i-x_{i-1}}x_{i-1}+\frac{x_{i+1}-x}{x_{i+1}-x_i}x_i$

Ha i = 0, vagy i = n, akkor a nem értelmezett tag nulla:

$\mathrm{u_0}(x)=\frac{x_1-x}{x_1-x_0}x_0$

és

$\mathrm{u_n}(x)=\frac{x-x_n}{x_n-x_{n-1}}x_{n-1}$

Így kapjuk az elsőfokú dongafüggvényt:

$\mathrm{s_1}(x)=\sum_1^n f_iu_i$

ahol f_i az x_i-ben előírt érték.

Másodfokú spline

A másodfokú spline-nál a peremfeltételek nem szimmetrikusak: meg lehet adni induló deriváltat, de ezzel a végpontban kapott derivált már egyértelmű. A másodfokú taghoz másodrendű osztott differenciát használnak:

$\mathrm{s_2}(x)=f_i+f'_i(x-x_i)+\mathrm f[x_i,x_i,x_{i+1}](x-x_i)^2$

ahol $\mathrm f[x_i,x_i,x_{i+1}]$ az i-edik kétszeres pontban és az i+1-edik pontban vett másodrendű osztott differencia.

Ez a másodrendű osztott differencia így számítható:

$\mathrm f[x_i,x_i,x_{i+1}]=\frac{f'_i-\mathrm f[x_{i+1},x_i]}{x_{i-1}-x_i}$

ahol

$\mathrm f[x_{i+1},x_i]=\frac{f_{i+1}-f_i}{x_{i+1}-x_i}$

Harmadfokú spline

Harmadfokú spline esetén a peremfeltételek szimmetrikusak, a kezdő- és a végpontban is megadható derivált. A gyakorlati alkalmazásokban ezek a legnépszerűbbek, mert elég nagy szabadságot adnak a görbe alakjának megválasztásához.

A következőkben feltesszük, hogy az adott pontsorozat egyenlő közű, ekvidisztáns, vagyis a szomszédos pontok távolságát ugyanakkorának vesszük. Ha az adott pontok távolsága nagy mértékben változik, akkor a kapott görbét át kell paraméterezni.

Bázisfüggvények

A harmadfokú spline függvényeket mind interpolációra, mind approximációra, mind ábrázolásra használják. Az ezekhez használt függvénybázisok:

Hermite-polinomok:

• α₀(v) = 1 - 3v² + 2v³
• α₁(v) = 3v² - 2v³
• β₀(v) = v - 2v² + v³
• β₁(v) = v³ - v²

B-spline:

Definiáljuk a következő függvényt:

$N_4:=$

$\frac{1}{6}v^3$ ha $0\leq v \leq 1$

$\frac{1}{6}(4-3v(v-2)^2)$ ha $1\leq v \leq 2$

$\frac{1}{6}(3v(v^2-8v+20)-44)$ ha $2\leq v \leq 3$

$\frac{1}{6}(4-v)^3$ ha $3\leq v \leq 4$

és 0 egyébként.

Legyen N_r = N_v+4-r. Ekkor az N_r függvények alkotják a bázist.

Bernstein-polinomok:

Az i-edik n-edfokú Bernstein-polinom:

$B_{n,i}={n \choose i}\, v^i\, (1-v)^{n-i}$

Görbék interpolációja

Jelölje rendre x₀, x₁, x₂, … az egyes pontokban előírt értéket, és e₀, e₁, e₂, … az adott pontokban előírt deriváltat. Az egyes szegmensek összeillesztésekor a simasági feltételekből lineáris egyenletrendszer adódik.

Az Hermite-polinomok használatával:

Zárt görbe esetén:

az egyenletrendszer minden egyenlete

e_i-1 + 4e_i + e_{i+ 1} = b_i

alakú, ahol i 0-tól n-ig megy, és e₀ = e_n, e₁ = e_n+1, és e₂ = e_n+2.

A b_i-k így számíthatók:

b_i = 3( x_i+1 - x_i-1 )

Nyílt görbe esetén van két szabad paraméter, az induló és az érkező derivált. Felhasználásukkal a szélső egyenletek:

4e₁ + e₂ = b₁ e_n-2 + 4e_n-1 = b_n-1

a közbülső egyenletek pedig a zárt görbe esetéhez hasonlók.

Az egyenletek jobb oldala csak a szélső esetben különbözik a zárt esettől, ugyanis itt még az ott választott deriváltakat is le kell vonni belőle:

b₁ = 3( x₂ - x₀ ) - e₀

és

b_n-1 = 3( x_n - x_n-2 ) - e_n

Az interpolációval nyert függvény a [0,1] szakaszon:

η(v) = x₀α₀(v) + x₁α₁(v) + e₀β₀(v) + e₁β₁(v)

A függvény többi szakasza hasonlóan határozható meg.

A B-spline segítségével:

A belső egyenletek alakja:

$\frac{1}{6}c_{i+1}+\frac{2}{3}c_{i+2}+\frac{1}{6}c_{i+3}=x_i$

ahol i = 0, …, n.

Ha a görbe nyílt, akkora két szabad paramétert a szélső pontokban felhasználva a szélső egyenletek alakja:

$- \frac{1}{2}c_1+\frac{1}{2}c_3=e_0$

és

$-\frac{1}{2}c_{n+1}+\frac{1}{2}c_{n+3}=e_n$

Az interpolációval kapott függvény:

$\varphi(v)=\sum_{r=1}^{n+3}c_r \mathrm N_r(v)$

Görbék approximációja

A harmadfokú B-spline-bázissal approximálnak is. Az interpolációtól eltérve azonban mások a szélső függvények, mert az approximációhoz az kell, hogy a bázisfüggvények összege azonosan egy legyen. A következőkben az N_i,l jelölésben l jelenti a fokszámot. Ha legfeljebb öt alappont van, akkor a bázis csak a szélső függvényeket tartalmazza. A szélső pontok multiplicitása l + 1.

A szélső függvények:

• n = 3, I = [0,1]:

Ekkor a B-spline függvények éppen a harmadfokú Bernstein-polinomok:

$\mathrm{N}_{0,3}(v)=(1-v)^3$

$\mathrm{N}_{1,3}(v)=3(1-v)^2v$

$\mathrm{N}_{2,3}(v)=3(1-v)v^2$

$\mathrm{N}_{3,3}(v)=v^3$

• n = 4, I = [0,2]:

$\mathrm{N}_{0,3}(v)=(1-v)^3$ ha $0\leq v \leq 1$, és 0 különben

$\mathrm N_{1,3}=$

$\frac{7}{4}v^3-\frac{9}{2}v^2+3v$ ha $0\leq v \leq 1$

$\frac{1}{4}(2-v)^3$ ha $1\leq v \leq 2$

$\mathrm N_{2,3}=$

$\frac{v^2}{2}(3-2v)$ ha $0\leq v \leq 1$

$\frac{1}{2}(v-2)^2(2v-1)$ ha $1\leq v \leq 2$

$\mathrm{N}_{3,3}(v)=(2-v)\mathrm{N}_{0,3}(v)$

• n = 5, I = [0,3]:

Az N_0,3, és az N_1,3 függvények, mint előbb, azonosan nullaként kiterjesztve a [2,3] szakaszra. N_3,3 = N_2,3(3-u), és N_4,3 = N_1,3(3-u).

Már csak az N_2,3 függvényt kell megadni:

$N_{2,3}=$

$\frac{1}{12}(18-11v)$ ha $0\leq v \leq 1$

$\frac{1}{4}v(2-v)^2+\frac{1}{6}(3-u)(-2v^2+6v-3)$ ha $1\leq v \leq 2$

$\frac{1}{6}(3-v)^3$ ha $2\leq v \leq 3$

• n > 5, I = [0,n-2]:

Az N_0,3, az N_1,3 és az N_2,3 függvények, mint előbb, azonosan nullaként kiterjesztve a szakasz további részére. Ezekből az N_n-2,3, az N_n-1,3 és az N_n,3 függvények az (n-v) tényezővel szorozva kaphatók.

A belső függvények a harmadfokú B-spline-bázis megfelelő függvényei, ahol is N_3,3 = N₄. A többi ebből eltolással kapható.

A csatoláshoz úgy kell meghatározni a λ és a μ együtthatókat, hogy:

q₁ = q₀ + λ(p_n - p_n-1), λ > 0

és

q₂ = λ²p_n-2 - (3λ² + 3λ + μ)p_n-1 + (2λ² + 3λ + 1 + μ)p_n ha n > 3

és

q₂ = λ²p₁ - (2λ² + 2λ + μ/2)p₂ + (λ² + 2λ + 1 + μ/2)p₃ ha n = 3

ahol a p_i és a q_i pontok különböző szegmensekhez tartoznak.

Az egyes szegmenseken belül az approximációval kapott függvény:

$u_3=\sum_{i=0}^n\mathrm N_{i,3}\cdot p_i$

Bézier-ívek:

A Bézier-ívek a Bernstein-polinomokkal állíthatók elő, a B-spline-okhoz hasonlóan. A csatolási együtthatók, és a függvényszegmensek ugyanúgy számíthatók.

Felületek interpolációja

Az interpolált felület így számítható:

$r(u,v)=(\varrho _0(u),\varrho _1(u)) \begin{bmatrix} r(0,v)\\ r(1,v)\\ \end{bmatrix}+ (r(u,0),r(u,0)) \begin{bmatrix} \varrho _0(v)\\ \varrho _1(v)\\ \end{bmatrix}- (\varrho _0(u),\varrho _1(u)) \begin{bmatrix} p_{0,0} & p_{0,1} \\ p_{1,0} & p_{1,1} \\ \end{bmatrix} \begin{bmatrix} \varrho _0(v)\\ \varrho _1(u)\\ \end{bmatrix}$

ahol a folytonosan differenciálható $\varrho _0(t),\varrho _1(t)$ függvényekre

$\varrho _0(t)+\varrho _1(t)=1,$

és

$\varrho _0(0)=1$

$\varrho _0(1)=0$

$\varrho _1(0)=0$

$\varrho _1(1)=1$

Hermite-interpoláció:

Az Hermite-felület így számítható:

$r(u,v)=(\alpha _0(u), \alpha _1(u), \beta _0(u), \beta _1(u))M \begin{bmatrix} \alpha _0(v) \\ \alpha _1(v) \\ \beta _0(v) \\ \beta _1(v)\end{bmatrix}$

ahol

$M = \begin{bmatrix} p_{0,0} & p_{0,1} & r _v(0,0) & r _v(0,1)) \\ p_{1,0} & p_{1,1} & r _v(1,0) & r _v(1,1))\\ r _u(0,0) & r _u(0,1) & r _{uv}(0,0) & r _{uv}(0,1) \\ r _u(1,0) & r _u(1,1) & r _{uv}(1,0) & r _{uv}(1,1) \end{bmatrix}$

ahol a vegyes második deriváltaknak a csatolásban van jelentőségük.

A csatoláshoz megoldandó egyenletrendszer alakja:

$r _u(i-1,j)+4r _u(i,j)+r _u(i+2,j)=3(p _{i+1,j}-p _{i-1,j})$

$r _v(i,j-1)+4r _u(i,j)+r _u(i,j+1)=3(p _{i,j+1}-p _{i,j-1})$

$r _{uv}(i-1,j)+4r _{uv}(i,j)+r _{uv}(i+1,j)=3(r _v(i+1,j)-r _v(i-1,j))$

$r _{uv}(i,j-1)+4r _{uv}(i,j)+r _{uv}(i,j+1)=3(r _u(i,j+1)-r _u(i,j-2))$

minden i, j-re.

Ez egy túlhatározott egyenletrendszer, ami mégis megoldható.

Felületek approximációja

A görbékhez hasonlóan felületeket is lehet approximálni.

Az általános eljárás szerint olyan két változós S_i,j(u,v) függvényeket kell venni, hogy:

$\sum_{i=0}^m\sum_{j=0}^n\mathrm S_{i,j}(u,v)=1$

ekkor az approximációval kapott felület egyenlete:

$r(u,v)=\sum_{i=0}^m\sum_{j=0}^n\mathrm S_{i,j}(u,v)p_{i,j}$

ahol p_i,j az approximációhoz megadott két indexes pontsorozat tagja.

Bézier-felületek:

A Bézier-felületek esetén

$\mathrm S_{i,j}(u,v)=\mathrm B_{i,m}(u)\mathrm B_{j,n}(v)$

A csatolási összefüggések:

$\begin{bmatrix} 0 & 1 & 0 & 0 \end{bmatrix} BTB^T \begin{bmatrix} 1 \\ v \\ v^2 \\ v^3 \end{bmatrix}= h_1(v) \begin{bmatrix} 0 & 1 & 2 & 3 \end{bmatrix} BQB^T \begin{bmatrix} 1 \\ v \\ v^2 \\ v^3 \end{bmatrix}+ h_2(v) \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} BQB^T \begin{bmatrix} 0 \\ 1 \\ 2v \\ 3v^2 \end{bmatrix}$

ahol T és Q tartalmazza a két felülethez megadott két paraméteres pontsorozat pontjainak koordinátáit:

$T=\begin{bmatrix} t_{0,0} & t_{0,1} & t_{0,2} & t_{0,3} \\ t_{1,0} & t_{1,1} & t_{1,2} & t_{1,3} \\ t_{2,0} & t_{2,1} & t_{2,2} & t_{2,3} \\ t_{3,0} & t_{3,1} & t_{2,3} & t_{3,3} \end{bmatrix}$

$Q=\begin{bmatrix} q_{0,0} & q_{0,1} & q_{0,2} & q_{0,3} \\ q_{1,0} & q_{1,1} & q_{1,2} & q_{1,3} \\ q_{2,0} & q_{2,1} & q_{2,2} & q_{2,3} \\ q_{3,0} & q_{3,1} & q_{2,3} & q_{3,3} \end{bmatrix}$

és B:

$B=\begin{bmatrix} 1 & 0 & 0 & 0 \\ -3 & 3 & 0 & 0 \\ 3 & -6 & 3 & 0 \\ -1 & 3 & -3 & 1 \end{bmatrix}$

A folytonos differenciálhatóság miatt a peremvonalon:

$\tilde r_u(1,v)=h_1(v)r_u(1,v)+h_2(v)r_v(1,v)$

ahol r_u és r_v a két csatlakozó felületdarab egyenlete.

B-spline felületek:

A B-spline felületek esetén az S_i,j függvények a megfelelő B-spline függvények szorzatai:

$\mathrm S_{i,j}(u,v)=\mathrm N_{i,m}(u)\mathrm N_{j,n}(v)$

A továbbiakban a számolás a Bézier-felületekhez hasonlóan folytatódik.

Ötödfokú spline

Ötödfokú spline-ok használatakor a harmadfokú spline-okhoz hasonló módszerek használhatók ugyanezeknek a spline-családoknak az ötödfokú elemeivel, és más, ötödfokú csatolási együtthatókkal. Ekkor a széleken a második deriváltak is megadhatók. Ez nagyobb szabadságot, de több bonyodalmat jelent.

Források

• Hegedűs: Numerikus analízis II. Első- és másodfokú spline
• Verhóczki László: Spline módszerek görbékre és felületekre Harmadfokú spline

Külső hivatkozások

• Interaktív bevezetés a spline-ok tulajdonságaiba
• Learning by Simulations Harmadfokú spline-ok interaktív szimulációja.
• Másod- és harmadfokú spline görbéket használnak betűtípusok definiálására
• [1] Egy másodfokú spline konkrét leírása
• [2] További feladatok spline illesztésére
• [3] Ötödfokú spline a vasútnál
• [4] Ötödfokú spline-ok a térképészetben