Spline

A Wikipédiából, a szabad enciklopédiából
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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 P1, P2, P3. A körérintős eljárásban kört illesztenek az első három P1, P2, P3 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 P1P2 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 P1P2 vektor egyenesére tükrözött P1P3 vektor iránya adja meg az érintő irányát, aminek hossza megint csak P1P2.

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[szerkesztés | forrásszöveg szerkesztése]

Legyen x1, x2, … 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 fi az xi-ben előírt érték.

Másodfokú spline[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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:

  • α0(v) = 1 - 3v2 + 2v3
  • α1(v) = 3v2 - 2v3
  • β0(v) = v - 2v2 + v3
  • β1(v) = v3 - v2

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 Nr = Nv+4-r. Ekkor az Nr 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[szerkesztés | forrásszöveg szerkesztése]

Jelölje rendre x0, x1, x2, … az egyes pontokban előírt értéket, és e0, e1, e2, … 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

ei-1 + 4ei + ei+ 1 = bi

alakú, ahol i 0-tól n-ig megy, és e0 = en, e1 = en+1, és e2 = en+2.

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

bi = 3( xi+1 - xi-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:

4e1 + e2 = b1 en-2 + 4en-1 = bn-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:

b1 = 3( x2 - x0 ) - e0

és

bn-1 = 3( xn - xn-2 ) - en

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

η(v) = x0α0(v) + x1α1(v) + e0β0(v) + e1β1(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[szerkesztés | forrásszöveg szerkesztése]

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 Ni,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 N0,3, és az N1,3 függvények, mint előbb, azonosan nullaként kiterjesztve a [2,3] szakaszra. N3,3 = N2,3(3-u), és N4,3 = N1,3(3-u).

Már csak az N2,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 N0,3, az N1,3 és az N2,3 függvények, mint előbb, azonosan nullaként kiterjesztve a szakasz további részére. Ezekből az Nn-2,3, az Nn-1,3 és az Nn,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 N3,3 = N4. A többi ebből eltolással kapható.

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

q1 = q0 + λ(pn - pn-1), λ > 0

és

q2 = λ2pn-2 - (3λ2 + 3λ + μ)pn-1 + (2λ2 + 3λ + 1 + μ)pn ha n > 3

és

q2 = λ2p1 - (2λ2 + 2λ + μ/2)p2 + (λ2 + 2λ + 1 + μ/2)p3 ha n = 3

ahol a pi és a qi 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 Si,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 pi,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 ru és rv a két csatlakozó felületdarab egyenlete.

B-spline felületek:

A B-spline felületek esetén az Si,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[szerkesztés | forrásszöveg szerkesztése]

Ö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[szerkesztés | forrásszöveg szerkesztése]

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

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