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_{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_{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)^{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\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

A Wikimédia Commons tartalmaz Spline témájú médiaállományokat.

• 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] Archiválva 2010. május 9-i dátummal a Wayback Machine-ben 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