2. Interpolációs görbetervezés Gondoljunk arra, hogy egy grafikus tervez˝o húz egy „vonalat” (szabadformájú görbét), ezt a vonalat nekünk „számítógép által feldolgozhatóvá” kell tennünk. Ennek egyik módja, hogy megpróbáljuk ezt a vonalat paraméterezni. Megelégszünk azzal is, ha az eredeti szabadformájú görbét valamilyen értelemben jól közelít˝o görbét állítunk el˝o paraméterezéssel. A problémát alapvet˝oen két f˝o megközelítésben lehet kezelni, az egyiket interpolációs görbetervezésnek, a másikat approximációs görbetervezének nevezzük. Az interpolációs görbetervezés alapötlete: kijelölünk az eredeti szabadformájú görbén néhány pontot (kontrollpontok), s ezeket algebrai görbeívekkel kötjük össze, a kontrollpontokban ügyelve a görbék „jó” csatlakozására. A „jó” csatlakozás a gyakorlatban például azt jelenti, hogy - a csatlakozó görbék sebességvektora a csatlakozási pontban egyirányú (G1 osztályú csatlakozás), - a csatlakozó görbék sebességvektora a csatlakozási pontban egyenl˝o (C1 osztályú csatlakozás), - a csatlakozó görbék sebesség és gyorsulásvektora a csatlakozási pontban megegyezik (C2 osztályú csatlakozás), - a csatlakozó görbék görbülete a csatlakozási pontban megegyezik (görbületfolytonos csatlakozás). Reguláris görbék C2 osztályú csatlakozása mindig görbületfolytonos is, mert a görbület a sebességb˝ol és a gyorsulásból kifejezhet˝o: κ=
kp0 × p00 k . kp0 k3
A kapott parametrizált görbe persze nagymértékben függ a kiválasztott kontrollpontoktól, azok számától, a használt algebrai görbe fokszámától.
2.1. Harmadfokú görbeívek A továbbiakban parametrizált harmadfokú görbeíven, röviden harmadfokú görbén egy p : [0, 1] → RN , u 7→ p(u) = u3 a + u2 b + uc + d parametrizált görbét értünk. (a, b, c, d) a görbe algebrai együtthatói. 2.1. Tétel. A p harmadfokú görbeívet egyértelm˝uen meghatározzák a görbe geometriai együtthatói, azaz (p(0), p(1), p0 (0), p0 (1)). 1
Bizonyítás. p0 (u) = 3u2 a + 2ub + c. A geometriai együtthatók egyszer˝uen kifejezhet˝ok az algebrai együtthatókkal: p(0) = d, p0 (0) = c,
p(1) = a + b + c + d, p0 (1) = 3a + 2b + c.
Innen az algebrai együtthatókat kifejezve: a = 2p(0) − 2p(1) + p0 (0) + p0 (1), b = −3p(0) + 3p(1) − 2p0 (0) − p0 (1), c = p0 (0), d = p(0). Tehát p(u) = (2u3 − 3u2 + 1)p(0) + (−2u3 + 3u2 )p(1)+ + (u3 − 2u2 + u)p0 (0) + (u3 − u2 )p0 (1). v A továbbiakban: F03 (u) = 2u3 − 3u2 + 1,
F13 (u) = −2u3 + 3u2 ,
F23 (u) = u3 − 2u2 + u,
F33 (u) = u3 − u2 ,
azaz p(u) = F03 (u) · p(0) + F13 (u) · p(1) + F23 (u) · p0 (0) + F33 (u) · p0 (1).
v0 p0 p1
v1
1. ábra. Harmadfokú görbeív a geometriai együtthatókkal. (Az ábrán a sebességvektorok skálázva láthatók.)
2.2. Három pont interpolációja harmadfokú görbeívvel Keressünk olyan harmadfokú görbeívet, melynek adottak végpontjai, a végpontokban az érint˝ok, valamint a görbe egy bels˝o pontja. 2
p0
p1
p0
p1
2. ábra. A harmadfokú görbeív függése a végpontjaiban adott sebességvektorok irányától és nagyságától. Jelölje a végpontokat p0 és p1 ; a bels˝o pontot pedig pb . Az érint˝o egységvektorok legyenek t0 és t1 . A problémában három ismeretlen van: a v0 , v1 pályasebességek a kezd˝o és végpontban valamint a bels˝o pont t paramétere. Ezeket az ismeretleneket úgy keressük, hogy pb = F03 (t)p0 + F13 (t)p1 + F23 (t)v0 t0 + F33 (t)v1 t1 teljesüljön. Fölhasználva, hogy F03 (t) + F13 (t) = 1: (2.1)
pb − p0 = F13 (t)(p1 − p0 ) + F23 (t)v0 t0 + F33 (t)v1 t1 .
Tekintsük az el˝oz˝o sort, mint az F13 (t), F23 (t)v0 , F33 (t)v1 ismeretlenekre fölírt lineáris egyenletrendszert, ahol az egyenleteket a koordináták adják. Vizsgáljuk el˝oször a problémát térben, azaz legyen rang(p1 − p0 , t0 , t1 ) = 3. (Ha az el˝obbi rang kett˝ovel egyenl˝o, akkor a végpontok és az érint˝ok egy síkban vannak, és a problémának nem lehet megoldása, ha a bels˝o pont nem ebben a síkban van.) A (2.1) lineáris egyenletrendszer megoldhatóságának szükséges és elégséges feltétele, hogy rang(pb − p0 , p1 − p0 , t0 , t1 ) = rang(p1 − p0 , t0 , t1 ) teljesüljön, azaz feltételünk mellett az egyenletrendszer egyértelm˝uen megoldható. El˝oször megoldjuk az egyenletrendszert F13 (t)-re. Jelöljük a megoldást ξ -vel. ta −2t 3 + 3t 2 = ξ harmadfokú egyenlet megoldása. Amennyiben t ∈ [0, 1], az egyenletrendszer F23 v0 és F33 v1 ismeretlenekre adódó megoldásaiból v0 és v1 is meghatározható. Síkban a (2.1) lineáris egyenletrendszer csak két egyenletb˝ol áll. A t paramétert tetsz˝olegesen megválaszthatjuk. Legyen pl. t = 0, 5: pb − p0 − F13 (0, 5)(p1 − p0 ) = F23 (0, 5)v0 t0 + F33 (0, 5)v1 t1 . 3
pb
p0
p1
3. ábra. Három pont interpolációja harmadfokú görbeívvel. Ha a két érint˝o egységvektor lineárisan független, akkor az egyenletrendszer v0 -ra és v1 -re egyértelm˝uen megoldható. A bal oldalt l-lel jelölve, és a megoldásokat Cramer szabály segítségével kifejezve: (2.2)
v0 = 8 ·
|l, t1 | , |t0 , t1 |
v1 = 8 ·
|t0 , l| . |t0 , t1 |
1. Feladat. A három pont interpolációs problémában jelüljük a megadott érint˝ok metszéspontját q-val. A pb bels˝o pont legyen a p0 p1 q háromszög q-ból induló súlyvonalának felez˝opontja. Bizonyítsuk be, hogy ilyenkor a probléma el˝obbi megoldása parabolaív.
2.3. Görbeillesztés Hermite-eljárással Az interpolációs görbeillesztés alapfeladata: Adottak a p0 , p1 , . . . , pn ∈ RN kontrollpontok. Keressünk olyan p : [0, n] → RN legalább C2 osztályú parametrizált görbét, hogy ∀i ∈ {0, . . . , n} : p(i) = pi , továbbá a (2.3)
pi : [0, 1] → RN ,
pi (u) = p(u + i) (i ∈ {0, . . . , n − 1})
parametrizált görbék harmadfokú görbeívek. 2.2. Tétel. Az interpolációs alapfeladatnak p0 (0) = v0 és p0 (n) = vn tetsz˝oleges rögzítése esetén egyértelm˝uen létezik megoldása. Bizonyítás. A (2.3) feltételnek eleget tév˝o p görbe akárhányszor differenciálható az (i, i + 1) intervallumon. Ha p legalább C2 osztályú, az azt jelenti, hogy: (2.4)
p0i (1) = p0i+1 (0),
p00i (1) = p00i+1 (0), 4
(i = 0, . . . , n − 2).
A p görbe sebességvektorát adjuk meg tetsz˝olegesen a rögzített kontrollpontokban a v0 , v1 , . . . , vn vektorokkal, azaz ∀i ∈ {1, . . . , n − 1} : p0 (i) = p0i−1 (1) = p0i (0) = vi ; és
p0 (0) = p0 (0) = v0 , p0 (n) = pn−1 (1) = vn .
A második deriváltakra vonatkozó (2.4) feltételt használva: F03 00 (1)pi−1 + F13 00 (1)pi + F23 00 (1)vi−1 + F33 00 (1)vi = = F03 00 (0)pi + F13 00 (0)pi+1 + F23 00 (0)vi + F33 00 (0)vi+1 . A deriváltakat kiszámítva, behelyettesítve a 0 és 1 értékeket, valamint rendezve: vi−1 + 4vi + vi+1 = 3(pi+1 − pi−1 ) (i = 1, . . . , n − 1). Ez koordinátánként n − 1 egyenlet v0 , . . . , vn koordinátáira, azaz a v0 és vn vektorokat szabadon megválasztva koordinátánként egy (n − 1) × (n − 1) típusú lineáris egyenletrendszert kapunk: 4v1 + v2 = 3(p2 − p0 ) − v0 v1 + 4v2 + v3 = 3(p3 − p1 ) .. . vi−1 + 4vi + vi+1 = 3(pi+1 − pi−1 ) .. . vn−2 + 4vn−1 = 3(pn − pn−2 ) − vn . Az el˝obbi lineáris egyenletrendszer alapmátrixa: 4 1 0 0 0 ... 0 1 4 1 0 0 . . . 0 0 1 4 1 0 . . . 0 (2.5) Mn−1 = .. . . 0 0 . . . 0 1 4 1 0 0 ... 0 0 1 4 Belátható, hogy det Mn−1 6= 0, tehát v0 és vn tetsz˝oleges megválasztása esetén az egyenletrendszer a (v1 , . . . , vn−1 ) vektorokra egyértelm˝uen megoldható, és a görbeillesztési feladatnak egyértelm˝uen van megoldása. v 5
p1
p0
p2
p2
p4
p3 p0
p3
p1
4. ábra. Görbeillesztés Hermite eljárással: nyílt és zárt összetett Hermite görbe. (A sebességvektorok az ábrán skálázva láthatók.) v0 és vn megválasztására a mérnöki gyakorlatban különböz˝o, itt nem részletezett eljárásokat alkalmaznak. 2. Feladat. Határozzuk meg a (2.5) mátrix determinánsát. (Belátva ezzel, hogy a determináns ténylegesen nem zéró.) 1. Megjegyzés. Zárt göbe esetén p0 = pn . Ha azt is el˝oírjuk, hogy v0 = vn , továbbá a teljes görbe legalább C2 osztályú legyen, akkor az el˝oz˝oekhez hasonló módon: vi−1 + 4vi + vi+1 = 3(pi+1 − pi−1 )
(i = 1, . . . , n, vn+1 = v1 ),
koordinátánként n egyenlettel és n ismeretlennel. Az alapmátrix determinánsa nem zéró, azaz zárt görbe esetén a kontrollpontok a görbét egyértelm˝uen meghatározzák a görbe legalább kétszeri folytonos differenciálhatóságát megkövetelve. 3. Feladat. Vegyük fel az origó középpontú egységkörön az (1, 0), (0, 1), (−1, 0), (0, −1) pontokat és határozzuk meg az ezen pontokra illeszked˝o összetett zárt Hermite görbét. Számítsuk ki a görbületi függvényét.
A feladatok megoldásai 1. Útmutatás. A feltételek szerint pb =
q p0 p1 + + . 2 4 4
(2.2)-be történ˝o egyszer˝u behelyettesítés után a görbe geometriai együtthatói: p0 , p1 , 2(q − p0 ), 2(p1 − q). 6
5. ábra. Kör közelítése Hermite görbékkel: a három zárt, összetett Hermite görbe kontrollpontjai a (szaggatott vonallal rajzolt) körön vannak. A görbe tehát: p(u) = u2 (p0 + p1 − 2q) + u(2q − p0 ) + p0 . Legyen q = 0. Ekkor: p(u) = (u2 − 2u + 1)p0 + u2 p1 . Az y tengelyt jelölje ki a (p0 + p1 )/2 vektor. Írjuk fel a görbe egyenletét az így meghatározott xy koordinátarendszerben! 2. A det Mn = ∆n determinánst az utolsó sor szerint kifejtve: ∆n = 4∆n−1 − ∆n−2 . Tekintsük a valós sorozatok vektorterét. Ebben a vektortérben kétdimenziós altér az an = 4an−1 − an−2 rekurziónak eleget tév˝o sorozatok tere, melyet jelöljön L. Olyan λ számot keresünk, melyre (λ , λ 2 , . . . , λ n , . . .) eleme L-nek. √ A rekurziót leíró√feltétel λ -ra a λ 2 − 4λ + 1 = 0 feltételt adja, ahonnan λ1 = 2 + 3 és λ2 = 2 − 3. Tehát a Λ1 = (λ1 , λ12 , . . . , λ1n , . . .) Λ2 = (λ2 , λ22 , . . . , λ2n , . . .) sorozatok L bázisát adják. Határozzuk meg a (∆1 , ∆2 , . . . , ∆n , . . .) sorozat (α, β ) koordinátáit a (Λ1 , Λ2 ) bázisra vonatkozóan: √ √ α(2 + 3) + β (2 − 3) = 4 √ √ α(2 + 3)2 + β (2 − 3)2 = 15, 7
ahonnan
1 1√ 1 1√ + 3, β = − 3. 2 3 2 3 µ ¶ ¶ µ √ √ n 1 1√ 1√ 1 ∆n = (2 − 3)n . + 3 (2 + 3) − 3− 2 3 3 2 α=
Tehát
∆n 6= 0, mert az els˝o tag egyt˝ol nagyobb, a második tag pedig egyt˝ol kisebb.
8
