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]

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]

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]

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

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

és

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

ahol fi az xi-ben előírt érték.

Másodfokú spline[szerkesztés]

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:

ahol 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ó:

ahol

Harmadfokú spline[szerkesztés]

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]

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:

ha
ha
ha
ha
é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:

Görbék interpolációja[szerkesztés]

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:

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:

és

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

Görbék approximációja[szerkesztés]

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:

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

ha , és 0 különben

ha

ha

ha

ha

  • 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:

ha

ha

ha

  • 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:

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]

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

ahol a folytonosan differenciálható függvényekre

és

Hermite-interpoláció:

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

ahol

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

A csatoláshoz megoldandó egyenletrendszer alakja:

minden i, j-re.

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

Felületek approximációja[szerkesztés]

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:

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

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

Bézier-felületek:

A Bézier-felületek esetén

A csatolási összefüggések:

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

és B:

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

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:

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

Ötödfokú spline[szerkesztés]

Ö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]

Külső hivatkozások[szerkesztés]

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