KUBI ˇ CNIZLEPKIZMAJHNOPRO ˇ ZNOSTNO ENERGIJO GA ˇ SPER JAKLI ˇ C in EMIL ˇ ZAGAR Fakulteta za matematiko in fiziko Univerza v Ljubljani Math. Subj. Class. (2000): 41A05, 41A15, 65D05, 65D07, 65D17 V ˇ clanku obravnavamo enega od osnovnih interpolacijskih problemov: dano je za- poredje toˇ ck v ravnini, poiskati pa ˇ zelimo interpolacijsko krivuljo, ki se ” dobro“ prilega podatkom. Uporabljamo kubiˇ cni zlepek in metodo, ki minimizira pribliˇ zno proˇ znostno energijokrivulje. Izpeljemopogojezaobstojinterpolanta,kiimalepoobliko(jeregularen, nima zank, osti in zavihkov) in predstavimo enostavno lokalno geometrijsko konstrukcijo. CUBIC SPLINES WITH SMALL STRAIN ENERGY In the paper one of the basic interpolation problems is considered. A sequence of points in the plane is given. Our goal is to find an interpolatory curve which fits the data “nicely”. Cubic splines are used and a method, which minimizes the approximate strain energy of the curve. Conditions on the existence of the interpolant, which has a nice shape (it is regular, loop-, cusp- and fold-free), are derived and a simple local geometric construction is presented. 1. Uvod Pomembnavejaraziskovanjanamejimedraˇ cunalniˇ stvominmatematiko je raˇ cunalniˇ sko podprto geometrijsko oblikovanje (angl. Computer Aided Geometric Design ali na kratko CAGD). Problemi, s katerimi se ukvarjamo raziskovalci na tem podroˇ cju, so povezani predvsem z geometrijsko pred- stavitvijo objektov (krivulj, ploskev, teles, ...), ki se pojavljajo v razliˇ cnih raziskovalnih in industrijskih problemih (konstrukcija letal, ladij, avtomobi- lov,oblikovanjeizdelkov,...). Panogajevzadnjihnekajdesetletjihdoˇ zivela nesluten razvoj, saj je oblikovanje izdelkov postalo pomemben dejavnik v proizvodnem procesu. Med standardne probleme, ki jih sreˇ camo na omenjenem podroˇ cju, sodi gotovo konstrukcija ravninskih parametriˇ cnih krivulj, ki temelji na interpo- laciji danih ravninskih toˇ ck. Oglejmo si to nalogo malo podrobneje. Dane so toˇ cke T j ∈R 2 , j = 0,1,...,n. (1) Iˇ sˇ cemo ravninsko parametriˇ cno polinomsko krivuljop: [t 0 ,t n ]→R 2 stopnje ≤n(torejp(t) = (x n (t),y n (t)) T ,kjerstax n iny n skalarnapolinomastopnje 48 Obzornik mat. fiz. 56 (2009) 2 Kubiˇ cni zlepki z majhno prožnostno energijo ≤ n), ki interpolira podane toˇ cke pri predpisanih vrednostih naraˇ sˇ cajoˇ cih interpolacijskih parametrov t j , j = 0,1,...,n, p(t j ) =T j , j = 0,1,...,n, t 0 0, potem pravimo, da se p in q v toˇ cki T zlepita G 1 zvezno. Opomba. Definicija geometrijske zveznosti reda 1 je ekvivalentna dejstvu, da se enotska tangenta krivulje spreminja zvezno. V CAGD tako zveznost pogosto sreˇ camo, saj je za obliko objektov kla- siˇ cna zveznost odvodov ponavadi prehuda zahteva. Niˇ cesar ˇ se nismo povedali o izbiri interpolacijskih parametrov t j in α j,k ter enotskih vektorjev d j , j = 0,1,...,n, k = 0,1. Omenili smo ˇ ze, da doloˇ citev interpolacijskih parametrovt j v sploˇ snem moˇ cno vpliva na obliko zlepka (slika 1). Vendar to ni veˇ c res, kadar zahtevamo geometrijsko zve- znost. V tem primeru oblika zlepka ni odvisna od parametrizacije, kar je zelo zaˇ zelena lastnost v CAGD (ni namreˇ c pomembno, kako smo do oblike objektapriˇ sli,pomembnesonjegovegeometrijskelastnosti). Zakonstrukcijo in kasnejˇ so uporabo zlepka pa je izbira interpolacijskih parametrov nujna. Poznamo veliko naˇ cinov, kako doloˇ citi interpolacijske parametre, a nobeden od njih ni univerzalen. Veˇ c o moˇ znih izbirah si bralci lahko preberejo v [6]. ˇ Se bolj zanimiv problem (predvsem za geometrijsko zvezne zlepke) je izbira enotskih vektorjev d i in parametrovα i,k , k = 0,1. Ko tudi te enkrat izberemo, je zlepek enoliˇ cno doloˇ cen in s i ∈P 3 , ki ga doloˇ cajo enaˇ cbe (3), lahko dokaj preprosto konstruiramo z reˇ sitvijo naslednjega matriˇ cnega sis- tema:     1 t i−1 t 2 i−1 t 3 i−1 1 t i t 2 i t 3 i 0 1 2t i−1 3t 2 i−1 0 1 2t i 3t 2 i         a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3     =     T T i−1 T T i α i,0 d T i−1 α i,1 d T i     . Poudarimo, da je pri G 1 zveznosti izbira zgoraj omenjenih koliˇ cin bi- stvena za obliko zlepka. Ponavadi imamo tri moˇ znosti: 50 Obzornik mat. fiz. 56 (2009) 2 Kubiˇ cni zlepki z majhno prožnostno energijo Slika1. Razliˇ cne izbire interpolacijskih parametrov (2) vodijo do razliˇ cnih interpolantov stopnje5naistihinterpolacijskihtoˇ ckah. Prikazanesoenakomernaparametrizacija(polna ˇ crta), tetivna parametrizacija (ˇ crtkana ˇ crta) in centripetalna parametrizacija (pikˇ casta ˇ crta). (a) smeri tangent so dane vnaprej; (b) izbira smeri je prepuˇ sˇ cena uporabniku; (c) zainterpolacijskizlepekzahtevamosamoG 1 zveznost,medtemkosmeri tangent ne predpiˇ semo. Prva dva naˇ cina vodita v lokalne interpolacijske sheme (konstrukcija se iz- vaja segment za segmentom), zadnja pa vodi v globalno shemo, pri kateri je treba reˇ sevati (ponavadi velike) sisteme linearnih enaˇ cb. Naj opozorimo, da je druga moˇ znost omejena le na manjˇ se popravke ˇ ze konstruiranega zlepka, saj sicer lahko ” laiˇ cni“ pristop uporabnika hitro zapelje v konstrukcijo zlep- kov z nesprejemljivo obliko. Za zlepek, ki zadoˇ sˇ ca (3), je pomembno predvsem to, da nima neˇ zelenih osti, zank ali zavihkov (slika 2) in da smiselno rekonstruira obliko prvotnih podatkov (1). Obiˇ cajno zahtevamo, da je krivulja s regularna, kar zadosti nekaterimzgorajzapisanimzahtevam. Spomnimose,daregularnostpomeni neniˇ celnost odvodas ′ (t) pri vsakem parametrut iz domene (oz. grads(t)6= 0). 2. Interpolacijski problem Najprej predstavimo oznake, ki jih bomo uporabljali. Za a = (a 1 ,a 2 ) T inb = (b 1 ,b 2 ) T najboa·b :=a 1 b 1 +a 2 b 2 skalarniproduktvR 2 ter∠(a,b) 48–60 51 Gašper Jakliˇ c in Emil Žagar Slika 2. Zanka (levo), ost (v sredini) in zavihek (krivulja se obrne in teˇ ce nazaj po sami sebi) (skica desno). kot med vektorjema a in b. Spomnimo se, da je a·b =kakkbkcos∠(a,b), |a×b| =kakkbk|sin∠(a,b)|, kjer je a×b :=a 1 b 2 −a 2 b 1 planarni vektorski produkt. Uporabljali bomo tudi standardno diferenˇ cno notacijo Δ(•) i = (•) i+1 −(•) i . ˇ Studirali bomo naslednji problem. Denimo, da so dane toˇ cke (1), kjer je T j 6= T j+1 in pripadajoˇ ci interpolacijski parametri (t j ) n j=0 . Opomnimo, da se toˇ cke kasneje lahko ponovijo (T i+k = T i ,k 6= ±1), le zaporedni dve ne smeta sovpadati. Predpostavili bomo, da so interpolacijski parametri podani vnaprej (obiˇ cajno jih sicer izraˇ cunamo iz podatkov, na primer s centripetalno ali tetivno parametrizacijo (2)). Vˇ casih so namreˇ c tudi inter- polacijski parametri neznanke, kar vodi v reˇ sevanje nelinearnih problemov in je veˇ cinoma zelo teˇ zka naloga. O takih problemih za kubiˇ cne krivulje si lahko bralci kaj veˇ c preberejo v [5]. ˇ Zelimo poiskatiG 1 zvezen parametriˇ cni zlepeks: [t 0 ,t n ]→R 2 , za kate- regavelja(3). Obstajaneskonˇ cnoreˇ sitevproblema,sajvsakaizbiraα i,0 > 0, α i,1 > 0 in d i poda enoliˇ cen zlepek s. Tako imamo na voljo veliko ˇ stevilo prostih parametrov, ki jih lahko uporabimo kot parametre oblike krivulje. Naravni pristop, kako izkoristiti parametre oblike, je minimizacija ustre- znega funkcionala. Ker je oblika krivulje odvisna predvsem od njene ukri- vljenosti κ, je smiselno minimizirati naslednji funkcional: ϕ s (α) := tn Z t 0 kκ(t)k 2 ks ′ (t)kdt = tn Z t 0 (s ′ (t)×s ′′ (t)) 2 ks ′ (t)k 5 dt, (4) kjer je α := ((α i,0 ,α i,1 )) n i=1 ∈ R 2n . Funkcionalu (4) pravimo proˇ znostna energija (angl. strain energy) krivulje in ima fizikalno ozadje, saj predsta- vlja energijo elastiˇ cne palice zaradi fleksijskega zvijanja. V praksi [1, 7] se namesto (4) obiˇ cajno uporablja pribliˇ zna proˇ znostna energija (tudi lineari- zirana upogibna energija) ϕ(α) := tn Z t 0 ks ′′ (t)k 2 dt. (5) 52 Obzornik mat. fiz. 56 (2009) 2 Kubiˇ cni zlepki z majhno prožnostno energijo ˇ Ce je ks ′ (t)k ≈ 1, je parametrizacija blizu naravni in kot ∠(s ′ (t),s ′′ (t)) blizu pravemu. Tako opazimo, da je v tem primeru (5) dobra aproksima- cija (4). Odvod s ′′ ni nujno zvezen, vendar pa ima samo konˇ cno ˇ stevilo konˇ cnih skokov, zato integral (5) obstaja. Omenimoˇ se, da med vsemi glad- kimi interpolacijskimi krivuljami kubiˇ cniC 2 zlepek minimizira linearizirano upogibno energijo [1]. Oˇ citno lahko minimizacijo izvajamo lokalno. Velja namreˇ c min α ϕ(α) = n X i=1 min α i ϕ i (α i ), kjer je ϕ i (α i ) := t i Z t i−1 ks ′′ i (t)k 2 dt, (6) in α i := (α i,0 ,α i,1 ). Iz geometrije sledi, da morajo biti komponente α i pozitivne, sicer tangentna vektorja na s i pri t i−1 in t i ne bi imela enakih smeri kot vektorjad i−1 ind i . Torej moramo dejansko izvajati minimizacijo z omejitvami min α i ∈D i ϕ i (α i ), D i :={α i ∈R 2 |α i >0}. Tu je neenakost α i >0 miˇ sljena po komponentah. Na ˇ zalost za dani smeri tangentd i−1 ,d i , globalniminimumnivednovobmoˇ cjuD i , karsoopaziliˇ ze v [8]. Problem so reˇ sili tako, da so dodali eno ali dve novi ” umetni“ toˇ cki, s katerima so dosegli, da je minimum vedno vˇ zelenem obmoˇ cju. Tu se pojavi standardni problem, kako dobro izbrati nove toˇ cke. Metoda ima veliko po- manjkljivost: predpostavka, dasosmeritangentpodanevnaprej, jevpraksi ˇ zal vse prej kot realistiˇ cna. ˇ Ceprav je postopek relativno preprost, zahteva kar nekaj dodatnega dela, kar lahko pomeni precejˇ snjo oviro v aplikacijah, ki imajo opravka z velikimi koliˇ cinami podatkov. V nadaljevanju bomoˇ studirali pristop, ki se izogne gornjim problemom. Namesto dodajanja novih interpolacijskih toˇ ck in smeri tangent, ˇ ce mini- mumϕ i nivdopustnidomeniD i ,bomopredpostavili,dasosmeritangentd i neznane. ˇ Ce vztrajamo pri fiksnemˇ stevilu interpolacijskih toˇ ck, funkcional ϕ i morda ne bo imel minimuma v dopustnem obmoˇ cju D i za kakˇ sno smer d i−1 ali d i . Namesto tega bomo uporabili primerno aproksimacijo funk- cionala ϕ i , kar vodi k bolj milim pogojem na dopustno obmoˇ cje za smeri tangent. 3. Minimizacija Nadaljujmo z aproksimacijo funkcionala (6). Kot v prejˇ snjem razdelku predpostavljamo, da imamo dane toˇ cke T i , enotske smeri tangent d i in 48–60 53 Gašper Jakliˇ c in Emil Žagar parametret i . Naraven naˇ cin aproksimacije (6) je uporaba kakˇ snega kvadra- turnega pravila. Uporabimo enega najpreprostejˇ sih, trapezno pravilo. Tako dobimo ϕ i (α) = t i Z t i−1 ks ′′ i (t)k 2 dt≈ Δt i−1 2 ks ′′ i (t i−1 )k 2 +ks ′′ i (t i )k 2  . (7) Toda ks ′′ i (t i−1 )k in ks ′′ i (t i )k sta odvisna od obeh smeri tangent d i−1 in d i , zato lahko priˇ cakujemo podobne teˇ zave in omejitve na dopustna obmoˇ cja kotvˇ clanku[8]. Temuselahkoizognemozaproksimacijoizraza(7). Poiskali bomo najboljˇ so aproksimacijo zas ′′ i (t i−1 ) kot linearno kombinacijos i (t i−1 ), s ′ i (t i−1 ) in s i (t i ), in podobno, najboljˇ so aproksimacijo za s ′′ i (t i ) s s i (t i−1 ), s ′ i (t i ) in s i (t i ). Tu z najboljˇ so aproksimacijo mislimo na aproksimacijo, ki je toˇ cna za polinome stopnje ≤k za ˇ cim veˇ cji k. Tako dobimo s ′′ i (t i−1 )≈ 2 Δt i−1  s i (t i )−s i (t i−1 ) Δt i−1 −s ′ i (t i−1 )  , s ′′ i (t i )≈ 2 Δt i−1  s ′ i (t i )− s i (t i )−s i (t i−1 ) Δt i−1  , in po (3) in (7) lahko aproksimiramoϕ i z ϕ i (α)≈ 2 Δt i−1 ψ i (α), (8) kjer je ψ i (α) := 1 Δt i−1 ΔT i−1 −α i,0 d i−1 2 + α i,1 d i − 1 Δt i−1 ΔT i−1 2 . (9) Izrek 1. Nelinearni funkcional ψ i , i = 1,2,...,n, ima enoliˇ cen globalni minimum v notranjosti D i natanko takrat, ko velja α ∗ i := 1 Δt i−1 (d i−1 ·ΔT i−1 ,d i ·ΔT i−1 ) T >0. Vrednost ekstrema je ψ i (α ∗ i ) = 2−c 2 i,0 −c 2 i,1 (Δt i−1 ) 4 kΔT i−1 k 2 , kjer je c i,k = cos∠(d i+k−1 ,ΔT i−1 ), k = 0,1. 54 Obzornik mat. fiz. 56 (2009) 2 Kubiˇ cni zlepki z majhno prožnostno energijo Dokaz. Funkcional (9) lahko poenostavimo v ψ i (α i ) = 1 (Δt i−1 ) 2 (Δt i−1 ) 2 α 2 i,0 +α 2 i,1  −2Δt i−1 (α i,0 d i−1 +α i,1 d i )·ΔT i−1 + 2kΔT i−1 k 2  . Minimumψ i je bodisi na robuD i ali pa ga dobimo prek parcialnih odvodov ψ i . V drugem primeru je lokalni minimum pri α ∗ i :=  α ∗ i,0 ,α ∗ i,1  T , kjer je α ∗ i,k = d i+k−1 ·ΔT i−1 Δt i−1 , k = 0,1, kar vodi do m :=ψ i (α ∗ i ) = 2−c 2 i,0 −c 2 i,1 (Δt i−1 ) 2 kΔT i−1 k 2 . Pokazati je treba, da je to tudi globalni minimum. Vzemimo poljubenα i = (α i,0 ,α i,1 ) T narobuobmoˇ cjaD i . Takojeα i,k = 0zavsajenk∈{0,1}. ˇ Ceje α i,0 =α i,1 = 0,potemjeψ i (α i ) = 2kΔT i−1 k 2 /(Δt i−1 ) 2 ≥m,inobravnavati je treba samo primer, ko je eden od α i,k pozitiven. Zaradi simetrije je dovolj gledatiα i,0 > 0. V tem primeru je enostavno preveriti, da funkcional ψ i | α i,1 =0 doseˇ ze svoj globalni minimum pri α i,0 = (d i−1 ·ΔT i−1 )/Δt i−1 , torej je ψ i (α i,0 ,0) =  2−c 2 i,0  kΔT i−1 k 2 /(Δt i−1 ) 2 ≥ m. S tem je dokaz konˇ can. Minimumjelahkotudi0. Vtemprimerujec i,0 =c i,1 = 1(lahkobibilotudi −1, vendar ima krivulja tedaj nezaˇ zeleni zavihek) in kubiˇ cni odsek zlepka s i postane ravna ˇ crta s i (t) =T i−1 + t−t i−1 Δt i−1 ΔT i−1 . Posledica 2. Pogoji α ∗ i >0, i = 1,2,...,n, imajo enostavno geometrijsko interpretacijo, namreˇ c∠(d i+k−1 ,ΔT i−1 )∈ [0, π 2 ), k = 0,1. Naj bodo predpostavke izreka 1 izpolnjene. Zastavimo si lahko pomem- bno vpraˇ sanje: ali je dobljeni kubiˇ cni odsek zlepkas i regularen na [t i−1 ,t i ], i = 1,2,...,n. Odgovor je pritrdilen, ˇ se veˇ c, dokaˇ zemo lahko, da s i nima osti, zank in zavihkov (slika 2). Izrek 3. Naj bodo izpolnjene predpostavke izreka 1 in s i , i = 1,2,...,n, dobljeni geometrijski interpolant, definiran s (3). Potem je odsek zlepka s i regularen in brez zank, osti in zavihkov. Zainteresirani bralci lahko dokaz preberejo v [3]. 48–60 55 Gašper Jakliˇ c in Emil Žagar 4. Konstrukcija smeri tangent V prejˇ snjem razdelku smo konstruirali kubiˇ cenG 1 zlepek z minimizacijo proˇ znostne energije. Pri tem smo predpostavili, da so enotske smeri tan- gent d i znane vnaprej in da so parametri α i dobljeni prek minimizacije. Iz izreka 1 sledi, da morajo biti smeri tangent primerno izbrane, sicer zlepek ne obstaja. V tem razdelku bomo obravnavali problem konstrukcije ustreznih smeri tangent d i . Zahtevati moramo d i+k−1 ·ΔT i−1 > 0, i = 1,2,...,n, k = 0,1. Da bi izpolnili te pogoje, obravnavajmo i-ti in (i + 1)-i segment zlepka s (slika 3). Definirajmo rotacijo za π/2 v pozitivni smeri R :=  0 −1 1 0  (10) in z i := sign(ΔT i−1 ×ΔT i ), ter u i :=z i RΔT i−1 , v i :=−z i RΔT i , w i :=λ i u i +(1−λ i )v i , λ i ∈R. (11) Slika 3. Dopustni poloˇ zaji za di. V prikazanem primeru je zi =−1. Lema 4. ˇ Ce je z i 6= 0 in λ i ∈ (0,1), potem je w i ·ΔT j > 0, j =i−1,i. Dokaz. Dokazali bomo, da velja w i ·ΔT j > 0, j =i−1. Dokaz za j =i je podoben in ga bomo izpustili. Vzemimo poljubenw i =λ i u i +(1−λ i )v i z λ i ∈ (0,1). Po (10) in (11) velja w i ·ΔT i−1 =λ i u i ·ΔT i−1 +(1−λ i )v i ·ΔT i−1 = =−(1−λ i )z i (RΔT i )·ΔT i−1 , 56 Obzornik mat. fiz. 56 (2009) 2 Kubiˇ cni zlepki z majhno prožnostno energijo ker sta u i in ΔT i−1 pravokotna. Oˇ citno je dovolj preveriti z i =−sign((RΔT i )·ΔT i−1 ). Kerjez i 6= 0,je∠(ΔT i−1 ,ΔT i )6= 0,π,inobravnavamodvemoˇ znosti. ˇ Ceje z i < 0, iz (11) in slike 3 sledi∠(RΔT i ,ΔT i−1 )<π/2 in je skalarni produkt (RΔT i )·ΔT i−1 pozitiven. Podobno obravnavamo ˇ se primerz i > 0. Iz leme 4 sledi, da vsak λ i ∈ (0,1) doloˇ ca w i , ki vodi k minimizaciji funk- cionala (9). Vzamemo na primer kar d i = w i /kw i k. Tako lahko na λ i , i = 1,2,...,n,gledamokotnaprosteparametre,kivplivajonaoblikozlepka s. Ena od moˇ znih izbir je λ i =kv i k/(ku i k+kv i k), kar pomeni, da d i kaˇ ze iz T i v smeri simetrale kota ∠(u i ,v i ) (glejte sliko 3 in posledico 6). To je naravna hevristiˇ cna izbira, ker tako smer d i postane najbolj oddaljena od neˇ zelenih smeri, ki vodijo do α i,k = 0 za k = 0 ali k = 1. Lema 4 izpuˇ sˇ ca dve moˇ znosti,∠(ΔT i−1 ,ΔT i ) = 0,π. ˇ Ce je obravnavani kot enak 0, lahko vzamemo w i = ΔT i , in spet veljajo sklepi leme. Primer, ko je kot enak π, pomeni, da ima vsaka parametrizacija takih podatkov zavihek. Torej je trebatakˇ senprimerizloˇ citispomoˇ cjopoprejˇ snjeobdelavepodatkov, napri- mer z dodajanjem nove, ” umetne“ toˇ cke zunaj premice, sˇ cimer se izognemo nezaˇ zelenemu zavihku. Gornje metode ne moremo uporabiti za smeri prve in zadnje tangente, vendar lahko izberemo kar d 0 = ΔT 0 /kΔT 0 k in d n = ΔT n−1 /kΔT n−1 k. Tako lahko za dane parametre oblike λ i ∈ (0,1) uporabimo algoritem 1 za konstrukcijo smeri tangent in G 1 kubiˇ cnega zlepka. Algoritem 1. Algoritem za konstrukcijo smeri tangentd i in kubiˇ cnegaG 1 zlepka s: for i = 1 to n−1 if ∠(ΔT i−1 ,ΔT i ) =π Exit. end if end for d 0 = ΔT 0 /kΔT 0 k for i = 1 to n−1 if ∠(ΔT i−1 ,ΔT i ) = 0 d i = ΔT i /kΔT i k else u i =z i RΔT i−1 v i =−z i RΔT i w i =λ i u i +(1−λ i )v i // λ i ∈ (0,1) so podani vnaprej ali izraˇ cunani po izreku 5 d i =w i /kw i k end if end for 48–60 57 Gašper Jakliˇ c in Emil Žagar d n = ΔT n−1 /kΔT n−1 k for i = 1 to n Konstruiraj segment zlepka s i z uporabo T j ,d j , j =i−1,i, in izreka 1. end for Izrek 1 ponuja ˇ sirok nabor dopustnih smeri tangent. Nato lahko z al- goritmom 1 lokalno konstruiramo zlepek. Naravno vpraˇ sanje je, katere so optimalne smeri tangent. Izrek 5. Minimalna vrednost funkcionala (9) je doseˇ zena pri smereh tan- gent d i :=w i /kw i k iz (11) in λ i = 2Δt 3 i A± √ B u i ·v i , (12) kjer je A := Δt 3 i−1 kΔT i k 2 +2Δt 3 i u i ·v i −Δt 3 i kΔT i−1 k 2 , B := Δt 3 i kΔT i−1 k 2 −Δt 3 i−1 kΔT i k 2  2 +4Δt 3 i−1 Δt 3 i (u i ·v i ) 2 . ˇ Ce je u i ·v i 6= 0, predznak v imenovalcu (12) izberemo tako, da je λ i ∈ (0,1), sicer pa postavimo a) λ i = 0 za z i =−1, ali b) λ i = 1 za z i = 1. Dokaz. Poiskati je treba optimalne smeri tangent d i , ki minimizirajo pri- bliˇ zno proˇ znostno energijo (8). ˇ Ce smeri tangent ˇ ze poznamo, z izrekom 1 dobimo optimalne α i . Ker smer d i nastopa samo v dveh sosednjih odsekih v (9), je dovolj minimizirati izraz 2 Δt i−1 α i,1 d i − 1 Δt i−1 ΔT i−1 2 + 2 Δt i 1 Δt i ΔT i −α i+1,0 d i 2 . Z uporabo izreka 1 in (11), izraˇ cunom parcialnih odvodov na λ i in precej raˇ cunanja dobimo naslednjo kvadratno enaˇ cbo: Λ(λ i ) :=λ 2 i (Δt 3 i−1 −Δt 3 i )u i ·v i +Δt 3 i kΔT i−1 k 2 −Δt 3 i−1 kΔT i k 2  + +λ i Δt 3 i−1 kΔT i k 2 +2Δt 3 i u i ·v i −Δt 3 i kΔT i−1 k 2  −Δt 3 i u i ·v i = 0. ˇ Ce je u i ·v i 6= 0, je Λ(0)Λ(1) =−Δt 3 i−1 Δt 3 i (u i ·v i ) 2 < 0, torej je natanko ena od reˇ sitev gotovo na (0,1). V primeruu i ·v i = 0 pa sta reˇ sitvi ravno 0 in 1. Pravo reˇ sitev izberemo glede na (11). 58 Obzornik mat. fiz. 56 (2009) 2 Kubiˇ cni zlepki z majhno prožnostno energijo Za posebno izbiro parametrizacije α = 2/3 (2) se da izraz (12) zelo poenostaviti. Opazimo, da del izraza B in koren izgineta. Tako dobimo naslednji rezultat: Posledica 6. Za 2/3-parametrizacijo, Δt i−1 Δt i =  kΔT i−1 k kΔT i k 2 3 , optimalne smeri tangent leˇ zijo na simetralah kotov ∠(u i ,v i ) pri vrednostih parametrov λ i := kΔT i k kΔT i−1 k+kΔT i k . Dobljene rezultate brez teˇ zav iz ravnine posploˇ simo v prostor R d ,d≥ 2 [4]. 5. Numeriˇ cna primera Slika 4. Kubiˇ cni G 1 interpolant (polna ˇ crta) z ustreznimi enotskimi tangentami (levo). Na desni je primerjava iste krivulje s C 2 zveznim kubiˇ cnim zlepkom (ˇ crtkana ˇ crta). Pri- bliˇ zni proˇ znostni energiji sta 112,0 in 55,74. Sklenimo ˇ clanek s primeroma. Kubiˇ cni G 1 interpolant, dobljen z algo- ritmom 1, se dobro prilegaC 2 kubiˇ cnemu interpolacijskemu zlepku s centri- petalno parametrizacijo (slika 4 desno). Na levi sliki so prikazane optimalne smeri tangent. Za laˇ zjo primerjavo sta izraˇ cunani tudi pribliˇ zni proˇ znostni energiji (5) za krivulji na slikah. Priˇ cakovano je energijaC 2 zlepka manjˇ sa, saj minimizira funkcional (5). Naj omenimo, da je bilo pri konstrukciji C 2 kubiˇ cnega zlepka treba reˇ siti globalni matriˇ cni sistem linearnih enaˇ cb, medtem ko je bil G 1 kubiˇ cni zlepek konstruiran lokalno z algoritmom 1. 48–60 59 Gašper Jakliˇ c in Emil Žagar Slika 5. Primer geometrijskega interpolanta na realnih podatkih Na sliki 5 je primer kubiˇ cnega G 1 zlepka na realnih podatkih. LITERATURA [1] C. de Boor, A practical guide to splines, Springer-Verlag, New York, 2001. [2] M. S. Floater, On the deviation of a parametric cubic spline interpolant from its data polygon, Comput. Aided Geom. Design25 (2008) 3, str. 148–156. [3] G. Jakliˇ c in E. ˇ Zagar, Planar cubic Hermite G 1 splines with small strain energy, poslano v objavo. [4] G.Jakliˇ cinE. ˇ Zagar,ShapepreservinginterpolationbyspatialcubicG 1 splines,Annali dell’Universita di Ferrara54 (2008) 2, str. 259–267. [5] J. Kozak in M. Krajnc, Geometric interpolation by planar cubic polynomial curves, Comput. Aided Geom. Design24 (2007) 2, str. 67–78. [6] E. T. Y. Lee, Choosing nodes in parametric curve interpolation, Comput. Aided De- sign21 (1989) 6, str. 363–370. [7] J. Wallner, Note on curve and surface energies, Comput. Aided Geom. Design 24 (2007) 8–9, str. 494–498. [8] J.-H.YonginF.Cheng,Geometric Hermite curves with minimum strain energy,Com- put. Aided Geom. Design21 (2004) 3, str. 281–301. 60 Obzornik mat. fiz. 56 (2009) 2