De Boorsův algoritmus - De Boors algorithm - Wikipedia

V matematický podpole z numerická analýza de Boorův algoritmus^[1] je polynomiální čas a numericky stabilní algoritmus pro hodnocení křivky spline v B-spline formulář. Jedná se o zobecnění de Casteljauův algoritmus pro Bézierovy křivky. Algoritmus vymyslel Carl R. de Boor. Byly vytvořeny zjednodušené, potenciálně rychlejší varianty de Boorova algoritmu, ale trpí relativně nižší stabilitou.^[2]^[3]

Úvod

Obecný úvod do B-splajnů je uveden v Hlavní článek. Zde diskutujeme de Boorův algoritmus, efektivní a numericky stabilní schéma pro vyhodnocení spline křivky ${ displaystyle mathbf {S} (x)}$ v poloze ${ displaystyle x}$ . Křivka je sestavena ze součtu funkcí B-spline ${ displaystyle B_ {i, p} (x)}$ vynásobeno konstantami s potenciálně vektorovou hodnotou ${ displaystyle mathbf {c} _ {i}}$ , nazývané kontrolní body,

{ displaystyle mathbf {S} (x) = součet _ {i} mathbf {c} _ {i} B_ {i, p} (x).}

B-splines řádu ${ displaystyle p + 1}$ jsou spojeny po částech polynomiální funkce stupně ${ displaystyle p}$ definovaný přes mřížku uzlů ${ displaystyle {t_ {0}, tečky, t_ {i}, tečky, t_ {m}}}$ (v následujícím textu vždy používáme indexy založené na nule). Algoritmus De Boora používá Ó (str²) + Ó (p) operace k vyhodnocení křivky spline. Poznámka: hlavní článek o B-splines a klasické publikace^[1] použijte jinou notaci: B-spline je indexováno jako ${ displaystyle B_ {i, n} (x)}$ s ${ displaystyle n = p + 1}$ .

Místní podpora

B-splajny mají lokální podporu, což znamená, že polynomy jsou pozitivní pouze v konečné doméně a nula jinde. Cox-de Boorův rekurzní vzorec^[4] ukazuje toto:

{ displaystyle B_ {i, 0} (x): = left {{ begin {matrix} 1 & mathrm {if} quad t_ {i} leq x

{ displaystyle B_ {i, p} (x): = { frac {x-t_ {i}} {t_ {i + p} -t_ {i}}} B_ {i, p-1} (x) + { frac {t_ {i + p + 1} -x} {t_ {i + p + 1} -t_ {i + 1}}} B_ {i + 1, p-1} (x).}

Nechte index ${ displaystyle k}$ definovat interval uzlu, který obsahuje pozici, ${ displaystyle x in [t_ {k}, t_ {k + 1})}$ . Můžeme vidět ve vzorci rekurze, s nímž pouze B-splines ${ displaystyle i = k-p, tečky, k}$ jsou nenulové pro tento interval uzlů. Součet se tedy snižuje na:

{ displaystyle mathbf {S} (x) = součet _ {i = k-p} ^ {k} mathbf {c} _ {i} B_ {i, p} (x).}

Vyplývá to z ${ displaystyle i geq 0}$ že ${ displaystyle k geq p}$ . Podobně vidíme v rekurzi, že nejvyšší dotazované umístění uzlu je na indexu ${ displaystyle k + 1 + p}$ . To znamená, že jakýkoli interval uzlů ${ displaystyle [t_ {k}, t_ {k + 1})}$ který se skutečně používá, musí mít alespoň ${ displaystyle p}$ další uzly před a po. V počítačovém programu se toho obvykle dosahuje opakováním prvního a posledního použitého umístění uzlu ${ displaystyle p}$ krát. Například pro ${ displaystyle p = 3}$ a umístění skutečných uzlů ${ displaystyle (0,1,2)}$ , jeden by vložil vektor uzlu ${ displaystyle (0,0,0,0,1,2,2,2,2)}$ .

Algoritmus

S těmito definicemi nyní můžeme popsat de Boorův algoritmus. Algoritmus nevypočítává funkce B-spline ${ displaystyle B_ {i, p} (x)}$ přímo. Místo toho to hodnotí ${ displaystyle mathbf {S} (x)}$ prostřednictvím ekvivalentního rekurzního vzorce.

Nechat ${ displaystyle mathbf {d} _ {i, r}}$ být novými kontrolními body s ${ displaystyle mathbf {d} _ {i, 0}: = mathbf {c} _ {i}}$ pro ${ displaystyle i = k-p, tečky, k}$ . Pro ${ displaystyle r = 1, tečky, p}$ použije se následující rekurze:

{ displaystyle mathbf {d} _ {i, r} = (1- alpha _ {i, r}) mathbf {d} _ {i-1, r-1} + alpha _ {i, r } mathbf {d} _ {i, r-1}; quad i = k-p + r, dots, k}

{ displaystyle alpha _ {i, r} = { frac {x-t_ {i}} {t_ {i + 1 + p-r} -t_ {i}}}.}

Jakmile jsou iterace kompletní, máme ${ displaystyle mathbf {S} (x) = mathbf {d} _ {k, p}}$ , znamenající, že ${ displaystyle mathbf {d} _ {k, p}}$ je požadovaný výsledek.

Algoritmus De Boora je efektivnější než explicitní výpočet B-splajnů ${ displaystyle B_ {i, p} (x)}$ s Cox-de Boorovým rekurzním vzorcem, protože nevypočítává výrazy, u nichž je zaručeno, že budou vynásobeny nulou.

Optimalizace

Algoritmus výše není optimalizován pro implementaci v počítači. Vyžaduje paměť pro ${ displaystyle (p + 1) + p + tečky + 1 = (p + 1) (p + 2) / 2}$ dočasné kontrolní body ${ displaystyle mathbf {d} _ {i, r}}$ . Každý dočasný kontrolní bod je zapsán přesně jednou a přečten dvakrát. Obrácením iterace ${ displaystyle i}$ (odpočítávání namísto nahoru), můžeme spustit algoritmus pouze s pamětí ${ displaystyle p + 1}$ dočasné kontrolní body tím, že ${ displaystyle mathbf {d} _ {i, r}}$ znovu použít paměť pro ${ displaystyle mathbf {d} _ {i, r-1}}$ . Podobně existuje pouze jedna hodnota ${ displaystyle alpha}$ použité v každém kroku, takže můžeme také znovu použít paměť.

Dále je vhodnější použít index založený na nule ${ displaystyle j = 0, tečky, p}$ pro dočasné kontrolní body. Vztah k předchozímu indexu je ${ displaystyle i = j + k-p}$ . Takto získáme vylepšený algoritmus:

Nechat ${ displaystyle mathbf {d} _ {j}: = mathbf {c} _ {j + k-p}}$ pro ${ displaystyle j = 0, tečky, p}$ . Iterovat pro ${ displaystyle r = 1, tečky, p}$ :

{ displaystyle mathbf {d} _ {j}: = (1- alpha _ {j}) mathbf {d} _ {j-1} + alpha _ {j} mathbf {d} _ {j }; quad j = p, dots, r quad}

(

{ displaystyle j}

musí být odpočítáváno)

{ displaystyle alpha _ {j}: = { frac {x-t_ {j + k-p}} {t_ {j + 1 + k-r} -t_ {j + k-p}}}.}

Po dokončení iterací je výsledek ${ displaystyle mathbf {S} (x) = mathbf {d} _ {p}}$ .

Příklad implementace

Následující kód v Programovací jazyk Python je naivní implementace optimalizovaného algoritmu.

def deBoor(k: int, X: int, t, C, p: int):    "" "Vyhodnocuje S (x).    Argumenty    ---------    k: Index intervalu uzlů, který obsahuje x.    x: Poloha.    t: Pole poloh uzlů, musí být polstrované, jak je popsáno výše.    c: Pole kontrolních bodů.    p: Stupeň B-spline.    """    d = [C[j + k - p] pro j v rozsah(0, p + 1)]    pro r v rozsah(1, p + 1):        pro j v rozsah(p, r - 1, -1):            alfa = (X - t[j + k - p]) / (t[j + 1 + k - r] - t[j + k - p])            d[j] = (1.0 - alfa) * d[j - 1] + alfa * d[j]    vrátit se d[p]

Viz také

externí odkazy

Počítačový kód

PPPACK: obsahuje mnoho spline algoritmů v Fortran
Vědecká knihovna GNU: C-knihovna, obsahuje dílčí knihovnu pro splajny přenesené z PPPACK
SciPy: Pythonova knihovna, obsahuje dílčí knihovnu scipy.interpolate s funkcemi spline založenými na FITPACK
TinySpline: C-knihovna pro spline s obálkou C ++ a vazbami pro C #, Java, Lua, PHP, Python a Ruby
Einspline: C-knihovna pro splajny v 1, 2 a 3 rozměrech s obaly Fortran

Reference

^ ^A ^b C. de Boor [1971], „Balík podprogramů pro výpočet pomocí B-splajnů“, Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; str. 109, 121.
^ Lee, E. T. Y. (prosinec 1982). "Zjednodušený postup výpočtu B-Spline". Výpočetní. Springer-Verlag. 29 (4): 365–371. doi:10.1007 / BF02246763.
^ Lee, E. T. Y. (1986). Msgstr "Komentáře k některým algoritmům B-spline". Výpočetní. Springer-Verlag. 36 (3): 229–238. doi:10.1007 / BF02240069.
^ C. de Boor, str. 90

Citované práce

Carl de Boor (2003). Praktický průvodce Splines, revidované vydání. Springer-Verlag. ISBN 0-387-95366-3.

[de_boor_paper-1] A ^b C. de Boor [1971], „Balík podprogramů pro výpočet pomocí B-splajnů“, Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; str. 109, 121.

[2] Lee, E. T. Y. (prosinec 1982). "Zjednodušený postup výpočtu B-Spline". Výpočetní. Springer-Verlag. 29 (4): 365–371. doi:10.1007 / BF02246763.

[3] Lee, E. T. Y. (1986). Msgstr "Komentáře k některým algoritmům B-spline". Výpočetní. Springer-Verlag. 36 (3): 229–238. doi:10.1007 / BF02240069.

[4] C. de Boor, str. 90

[1]

[2]

[3]

[4]