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}}_{\mathrm{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}}_{\mathrm{0}}(x)=\frac{x_1-x}{x_1-x_0}{x}_0$

és

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

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

${\mathrm{s}}_{\mathrm{1}}(x)=\sum _1^n{f}_i{u}_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}}_{\mathrm{2}}(x)=f_i+f{\text{'}}_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{\text{'}}_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\le v\le 1$

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

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

$\frac{1}{6}(4-v{)}^3$ ha $3\le v\le 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}=(\genfrac{}{}{0ex}{}{n}{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:

$\phi (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{)}^{2}v$

${\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\le v\le 1$, és 0 különben

${\mathrm{N}}_{1,3}=$

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

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

${\mathrm{N}}_{2,3}=$

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

$\frac{1}{2}(v-2{)}^2(2v-1)$ ha $1\le v\le 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\le v\le 1$

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

$\frac{1}{6}(3-v{)}^3$ ha $2\le v\le 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))\left[\begin{array}{c}r(0,v)\\ r(1,v)\end{array}\right]+(r(u,0),r(u,0))\left[\begin{array}{c}{\varrho }_0(v)\\ {\varrho }_1(v)\end{array}\right]-({\varrho }_0(u),{\varrho }_1(u))\left[\begin{array}{cc}{p}_{0,0}& p_{0,1}\\ p_{1,0}& p_{1,1}\end{array}\right]\left[\begin{array}{c}{\varrho }_0(v)\\ {\varrho }_1(u)\end{array}\right]$

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\left[\begin{array}{c}{\alpha }_0(v)\\ {\alpha }_1(v)\\ {\beta }_0(v)\\ {\beta }_1(v)\end{array}\right]$

ahol

$M=\left[\begin{array}{cccc}{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{array}\right]$

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:

$\left[\begin{array}{cccc}0& 1& 0& 0\end{array}\right]BT{B}^T\left[\begin{array}{c}1\\ v\\ v^2\\ v^3\end{array}\right]=h_1(v)\left[\begin{array}{cccc}0& 1& 2& 3\end{array}\right]BQ{B}^T\left[\begin{array}{c}1\\ v\\ v^2\\ v^3\end{array}\right]+h_2(v)\left[\begin{array}{cccc}1& 1& 1& 1\end{array}\right]BQ{B}^T\left[\begin{array}{c}0\\ 1\\ 2v\\ 3v^2\end{array}\right]$

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

$T=\left[\begin{array}{cccc}{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{array}\right]$

$Q=\left[\begin{array}{cccc}{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{array}\right]$

és B:

$B=\left[\begin{array}{cccc}1& 0& 0& 0\\ -3& 3& 0& 0\\ 3& -6& 3& 0\\ -1& 3& -3& 1\end{array}\right]$

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] Sablon:Wayback 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