Aproximácia (interpolácia) je generujúci princíp, ktorý umožňuje modelovať súvislé oblúky čiar z diskrétnych usporiadaných množín bodov rozšíreného euklidovského priestoru. Vnútorné geometrické vlastnosti modelovaných čiar sú závislé od tvaru polynomických interpolačných funkcií určujúcich analytické reprezentácie modelovaných útvarov, t.j. od hodnôt koeficientov pri mocninách premennej u. Požadované geometrické vlastnosti stanovujú podmienky pre určenie týchto koeficientov. Všeobecne musia interpolačné polynómy

Pl_i(u) = a_inuⁿ + a_in-1u^n-1 +...+ a_i1u + a_i0

spĺňať túto podmienku:
súčet polynómov vzťahujúcich sa na vlastné body riadiaceho útvaru (v danom usporiadaní) sa rovná jednej

            (1)

Analytická reprezentácia modelovaného oblúka určeného usporiadanou n-ticou bodov

M = ( P_i(x_i , y_i , z_i , h_i ) ), i = 1, ..., n, kde h_i = 0, 1

ktorý vytvoríme aproximáciou (interpoláciou) určenou maticou interpolácie

I(u) = ( Pl₁(u) Pl₂(u) ... Pl_n(u) )

je bodová funkcia požadovaných vlastností na I = < 0, 1 >

Rozoznávame dva typy modelovania:

Modelovanie možno aplikovať na celú usporiadanú n-ticu bodov, alebo možno modelovať po častiach, pričom výsledná čiara je zložená z elementárnych oblúkov, najčastejšie kubických. Oba spôsoby modelovania čiar majú svoje výhody i nevýhody. Ak interpolujeme naraz celú n-ticu bodov, výsledná čiara je stupňa n-1, má veľa extrémov (extrémne krivosti v niektorých bodoch, inflexné body) a väčšinou nie je možné zmeniť lokálne (len v okolí niektorého bodu) jej tvar, modelovanie čiary je nepružné. Pri modelovaní po častiach je nevyhnutné zabezpečiť spojitosť a hladkosť výslednej čiary v spoločných bodoch jednotlivých oblúkov, a to zhodnosťou niektorých prvkov riadiacich útvarov napájaných oblúkov, čiže v súbore vstupných údajov pre počítačové spracovanie. Tieto súbory bývajú v praktických prípadoch veľmi obsiahle a neprehľadné a ich zmena je náročná a nepohodlná. Uvedieme niekoľko typov modelovaných oblúkov najčastejšie sa vyskytujúcich v používaných CAD systémoch konštruovania s podporou počítačov.

spĺňajúcich podmienku (1).

Fergusonova kubika je interpolačná čiara určená začiatočným a koncovým bodom a vektormi dotyčníc v týchto bodoch. Interpolácia je určená kubickými Hermitovými polynómami.

Platí: r(0) = P₀     r(1) = P₁      r´(0) = a₀     r´(1) = a₁

Začiatočným bodom oblúka Fergusonovej kubiky je bod P₀, koncovým bodom bod P₁.
Vektor dotyčnice v bode P₀ je vektor a₀, v bode P₁ vektor a₁.
Geometrické vlastnosti modelovaného oblúka stanovujú podmienky pre určenie koeficientov použitých interpolačných polynómov. Názov Hermitove polynómy je odvodený z mena matematika Hermita, ktorý už v 19. storočí poznal uvedené polynómy a použil ich pri interpolácii funkcií. Aplikovaný generujúci princíp sa nazýva Hermitova kubická interpolácia. Súradnice vnútorných bodov oblúka Fergusonovej kubiky možno určiť výpočtom z bodovej funkcie pre hodnoty krivoiarych súradníc príslušných bodov z intervalu (0,1).

Vo väčšine praktických aplikácií je interpolačná čiara určená len usporiadanou množinou vlastných bodov, ktorými má prechádzať. Vektory dotyčníc určujúce zakrivenie (prvú krivosť) v danom bode modelovanej čiary sú volené empiricky a ich voľba spôsobuje konštruktérom nezanedbateľné problémy, pretože významne ovplyvňujú tvar výslednej čiary.
V kvalitnejších CAD systémoch je zabezpečená možnosť určovania vektorov dotyčníc v závislosti od riadiaceho útvaru - usporiadanej množiny vlastných bodov tak, aby mala výsledná interpolačná čiara "kľudný priebeh", kopírujúci bez väčších extrémov tvar riadiacej lomenej čiary. Jednou z metód určovania vektorov dotyčníc v bodoch interpolačnej čiary je Akimova interpolácia.

Nech P_i-2 P_i-1 P_i P_i+1 P_i+2 je časť lomenej čiary určenej bodmi riadiaceho útvaru interpolačnej čiary (obr. 3.31). Akimovou konštrukciou určíme v bode P_i vektor dotyčnice. Nájdeme body A_i, B_i a C_i, pre ktoré platí

Iný spôsob určenia vektorov dotyčnice je D-interpolácia, pri ktorej je vektor dotyčnice a v bode P_i určený ako lineárna kombinácia vektorov tvorených daným bodom a bodmi riadiaceho útvaru P_i-1 (predchádzajúci) a P_i+1 (nasledujúci) (obr. 3.32).

Vektor a_i je kolmý priemet vektora b_i do vektora súčtu d_i.

Interpolačná kubika, ktorej vektory dotyčníc riadiaceho útvaru { P₀ P₁ a₀ a₁} sú určené pomocou D-interpolácie, a ktorej interpolačné polynómy sú Hermitove, sa nazýva D-splajn kubika.

Owerhauserova kubika je interpolačná čiara určená usporiadanou n-ticou bodov a Hermitovou interpoláciou, pričom vektory dotyčníc čiary sú určené len v začiatočnom a koncovom bode čiary.

2. Bézierova kubika (kubický aproximačný oblúk)

Bézierova kubika je aproximačná čiara určená štyrmi vlastnými bodmi riadiaceho útvaru. Aproximácia je určená Bernštejnovými kubickými polynómami.

Platí: r(0) = P₀     r(1) = P₃     r´(0) = 3 P₀ P₁    r´(1) = 3 P₂ P₃

Začiatočný bod oblúka je bod P₀ a vektor dotyčnice oblúka v tomto bode je trojnásobkom vektora v prvej strane riadiaceho polygónu 3P₀P₁. Koncový bod oblúka je bod P₁, vektor dotyčnice v tomto bode je trojnásobkom vektora v poslednej strane riadiaceho polygónu 3P₂P₃. Uvedené geometrické vlastnosti modelovaného kubického oblúka zaručujú použité Bernštejnove polynómy, pomenované po ruskom matematikovi Bernštejnovi, ktorý ich použil už v roku 1912 na aproximáciu funkcií. Všeobecný vzorec pre určenie týchto polynómov stupňa n je

, pre i = 0,...,n, kde n je stupeň.

Homogénne súradnice vnútorných bodov Bézierovej kubiky s krivočiarymi súradnicami z intervalu (0,1) možno nájsť z bodovej funkcie výpočtom.
Bod Bézierovej kubiky zostrojíme pomocou konštrukcie nazývanej algoritmus Boor - de Casteljau (obr. 3.34).

Nech a = 1/3 je krivočiara súradnica hľadaného bodu kubiky z intervalu (0, 1).
V jednej tretine dĺžky od začiatočného bodu každej z úsečiek P₀P₁ , P₁P₂ , P₂P₃
ležia body P₀', P₁', P₂' určujúce nový riadiaci útvar,
ktorý zredukujeme obdobnou konštrukciou až na úsečku P₀''P₁''
a ďalej na bod Bézierovho oblúka P(1/3).
Pre vektor dotyčnice v tomto bode platí
r´(1/3) = P₀´´P₁´´.

3. Coonsova B-splajn kubika (kubický aproximačný oblúk)

Coonsova B-splajn kubika je aproximačná čiara určená štyrmi vlastnými bodmi riadiaceho útvaru. Aproximácia je určená Coonsovými kubickými polynómami (obr. 3.35).

Syntetická reprezentácia:     ({P₀, P₁, P₂, P₃}, I(u))

Analytické reprezentácie:

riadiaci útvar - P_i = (x_i, y_i, z_i, 1) pre i = 0, 1, 2, 3

mapa oblúka čiary     M=(P₀ P₁ P₂ P₃)

generujúci princíp - I(u) = (Co₀₃(u) Co₁₃(u) Co₂₃(u) Co₃₃(u)), kde

Co₀₃(u) =            Co₁₃(u) =


Co₂₃(u) =            Co₃₃(u) =

sú Coonsove aproximačné polynómy, pričom .

modelovaný útvar-   r(u) = M.I^T(u) = P₀Co₀₃(u)+P₁Co₁₃(u)+P₂Co₂₃(u)+P₃Co₃₃(u), u ∈ < 0, 1 >

Platí: r(0) = ((P₀ + P₂)/2 + 2P₁)/3    r´(0) = (P₂ - P₀)/2

    r(1) = ((P₁ + P₃)/2 + 2P₂)/3 r´(1) = (P₃ - P₁)/2

Začiatočný bod oblúka je bod ťažnice prechádzajúcej vrcholom P₁ a stredom strany P₀P₂ trojuholníka P₀P₁P₂ ležiaci v jednej tretine dĺžky ťažnice od vrchola P₁ (antiťažisko trojuholníka).
Koncový bod oblúka je antiťažisko trojuholníka P₁P₂P₃ na ťažnici prechádzajúcej vrcholom P₂ a stredom strany P₁P₃.
Vektory dotyčníc v týchto bodoch sú kolineárne s vektormi P₀ + P₂ , P₁ + P₃.
Geometriu modelovaného oblúka zaručujú Coonsove polynómy pomenované podľa amerického počítačového grafika Coonsa, ktoré sú B-splajn kubickými polynómami.

Skutočnosť, že modelovaná čiara neobsahuje žiadny z bodov riadiaceho útvaru a pri modelovaní nie je dostatočne zrejmá poloha začiatočného a koncového bodu oblúka, predstavuje určitú nevýhodu pri praktickom používaní B-splajn kubík v konštruovaní s podporou počítačov. Pôvodný riadiaci útvar, usporiadanú štvoricu bodov {P₀ , P₁ , P₂ , P₃} možno nahradiť novým útvarom - náhradným riadiacim polygónom {Q₀ , Q₁ , Q₂ , Q₃}, ktorý zostrojíme tak, aby body P₀ a P₃ boli začiatočným a koncovým bodom aproximačného B-splajn oblúka s riadiacim útvarom určeným náhradným polygónom{Q₀ , Q₁ , Q₂ , Q₃}, krivku "natiahneme" do bodov P₀ a P₃ (obr. 3.36).

|Q₁P₁| = |P₁P₂| = |P₂Q₂|

|Q´₀P₀| = |P₀P₁|

|Q₀Q´₀| = 2|Q´₀Q₁|

|Q´₃P₃| = |P₃P₂|

|Q₃Q´₃| = 2|Q´₃Q₂|

Vo všetkých predchádzajúcich typoch modelovaných čiar je možné dosiahnuť zmenu tvaru čiary iba zmenou prvkov riadiaceho útvaru, ktoré predstavujú súbor vstupných údajov pre spracovanie počítačom. Tento súbor je v praktických prípadoch veľmi objemný a neprehľadný, čo obmedzuje modelovacie možnosti konštruktéra. Zmenu vnútorných vlastností modelovaného oblúka možno dosiahnuť aj zmenou generujúceho princípu, t.j. zmenou tvaru použitých polynomických funkcií, možnosťou meniť hodnoty ich koeficientov pomocou niekoľkých parametrov.

4. β-splajn kubika (kubický aproximačný oblúk)

β-splajn kubika je aproximačná čiara určená usporiadanou štvoricou vlastných bodov priestoru. Aproximáciu určujú β-splajn kubické polynómy.

Syntetická reprezentácia:  ({P₀ , P₁ , P₂ , P₃}, I(u))

Analytické reprezentácie:

riadiaci útvar - P_i = (x_i, y_i, z_i, 1) pre i = 0, 1, 2, 3

mapa oblúka čiary     M = (P₀ P₁ P₂ P₃)

generujúci princíp - I(u) = (Ba₀₃(u) Ba₁₃(u) Ba₂₃(u) Ba₃₃(u)), kde

Ba₀₃(u) =

Ba₁₃(u) =

Ba₂₃(u) =

Ba₃₃(u) =          

sú β-splajn aproximačné polynómy.

modelovaný útvar -      r(u) = M.I^T(u) = P₀ Ba₀₃(u) + P₁Ba₁₃(u) + P₂Ba₂₃(u) + P₃Ba₃₃(u), u ∈ < 0, 1 >

Koeficienty β-splajn polynómov sú funkciami dvoch parametrov, ovplyvňujúcich vnútorné vlastnosti modelovaných oblúkov.

Parameter β₁ - ťah ovplyvňuje polohu začiatočného a koncového bodu oblúka,
"doťahuje" čiaru k prvému, príp. koncovému bodu riadiaceho útvaru.

Parameter β₂ - napätie ovplyvňuje prvú krivosť modelovaného oblúka vo vnútorných bodoch,
"napína" ("uvoľňuje") čiaru smerom ku strane (od strany) P₁P₂ riadiaceho útvaru.
Ak β₁ = 1 a β₂ = 0, dostávame Coonsove B-splajn polynómy.

5. Racionálne kubiky (kubické aproximačné oblúky)

Racionálna kubika je aproximačná čiara určená usporiadanou štvoricou vlastných bodov priestoru a kladnými váhami bodov (zvolenými reprezentantmi z tried homogénnych súradníc bodov). Váha bodu vyjadruje mieru, akou bod ovplyvňuje tvar modelovanej čiary. Aproximácia je určená kubickými polynómami.

Syntetická reprezentácia:     ({h₀P₀ , h₁P₁ , h₂P₂ , h₃P₃}, I(u))

Analytické reprezentácie:

riadiaci útvar -     P_i = h_i(x_i, y_i, z_i, 1), h_i > 0, pre i = 0, 1, 2, 3

mapa oblúka čiary          M = (h₀P₀ h₁P₁ h₂P₂ h₃P₃)

generujúci princíp - I(u) = (Pl₀₃(u) Pl₁₃(u) Pl₂₃(u) Pl₃₃(u)), kde

Pl_i3(u) pre i = 0, 1, 2, 3 sú aproximačné kubické polynómy - Bernštejnove, B-splajn, β-splajn, pre ktoré platí

modelovaný útvar -     racionálne rozšírenie kubickej aproximačnej čiary
(Bézierovej, Coonsovej, B-splajn, β-splajn) reprezentované bodovou funkciou

R(u) = M.I^T(u) = ,

kde H(u) = je váhová funkcia, nenulová pre u ∈ < 0, 1 >.

Oblúk racionálnej aproximačnej kubiky je pre u ∈ < 0,1 > určený racionálnou bodovou funkciou

V závislosti od veľkosti váhy každého bodu riadiaceho útvaru sa mení tvar modelovaného oblúka.
Pre hodnoty h₀ = h₁ = h₂ = h₃ je modelovaným oblúkom príslušná Bèzierova, Coonsova B-splajn, príp. β-splajn kubika.

Oblúky kužeľosečiek možno modelovať ako aproximačné Bézierove racionálne kvadratické oblúky (obr. 3.38).

Syntetická reprezentácia:        ({h₀P₀ h₁P₁ h₂P₂ }, I(u))

Analytické reprezentácie:

riadiaci útvar -     P_i = h_i(x_i, y_i, z_i,1), h_i > 0, pre i = 0, 1, 2

mapa oblúka čiary      M = (h₀P₀ h₁P₁ h₂P₂)

generujúci princíp - I(u) = (Be₀₂(u) Be₁₂(u) Be22(u)), kde

Be₀₂(u) = (1-u)²        Be₁₂(u) = 2u(1-u)        Be₂₂ (u) = u²

sú Bernštejnove aproximačné polynómy druhého stupňa

modelovaný útvar        R(u) = M.I^T(u) =

r(u) = R(u)/H(u), H(u) = , u ∈ < 0, 1 >,     h₀ = 1-ρ, h₁ = ρ, h₂ = 1-ρ, ρ =

Bod O je stred úsečky P₀P₂ a bod P = P_E (P_P príp. P_H)
je bod oblúka modelovanej kužeľosečky, ktorou je

elipsa pre ρ < 0,5

parabola pre ρ = 0,5

hyperbola pre ρ > 0,5

Pri modelovaní racionálnych aproximačných kriviek po častiach, keď sú spájané oblúky rôznych stupňov, hovoríme o neuniformných racionálnych čiarach.

NURBS - neuniformné racionálne B-splajn krivky sú považované za aproximačné čiary najširšieho praktického uplatnenia, vďaka pomerne jednoduchým analytickým reprezentáciám, možnosti lokálnej zmeny tvaru modelovanej čiary zmenou váhy príslušného bodu riadiaceho útvaru (nie je potrebná zmena jeho homogénnych súradníc) a možnosti vytvárať čiaru z oblúkov rôznych stupňov podľa požadovaného tvaru výsledku.

Na obr. 3.39 sú použité Fergusonove kubické oblúky pri modelovaní písmen gréckej abecedy, na obr. 3.49 je nápis modelovaný z Bézierových kubík. Bézierove kubiky sú najčastejšie používané aproximačné čiary v grafických programových vybaveniach (SketchPad, AutoCAD, MSGraph, CorellDraw, CorellFlow) a bývajú súčasťou kresliacich procedúr poskytovaných textovými editormi (MSWord, AmiPro, Word Pro, a pod.).

Obr. 3. 39