Algoritme de De Boor

En el subcampo matemàtic del anàlisis numèric, l'algoritme de De Boor és un algoritme de temps polinomial i numèricament estable per a evaluar curves spline en forma B-spline. És una generalisació del algoritme Casteljau per a les curves de Bézier. L'algoritme va ser ideat per Carl R. De Boor. S'han creat variants simplificades i potencialment més ràpides de l'algoritme de De Boor, pero sofrixen una estabilitat comparativament menor.

Introducció

L'algoritme de De Boor és un esquema eficient i numèricament estable per a evaluar una curva spline $𝐒(x)$ en posició $x$. La curva es construïx a partir d'una suma de funcions B-spline $B_{i,p}(x)$ multiplicada en valors vectorials potencialment constants ${𝐜}_i$, cridats punts de control.

$𝐒(x)=\sum _i{𝐜}_i{B}_{i,p}(x).$

Les B-splines d'orde $p+1$ són funcions polinòmiques unitàries de grau $p$ definides sobre una cuadrícula de nucs $t_0,\dots ,t_i,\dots ,t_m$ (s'utilisen índexs basats en zero en avant). L'algoritme de De Boor utilisa operacions O(p²) + O(p) per a evaluar la curva de spline. Nota: l'artícul principal sobre B-splines i les publicacions clàssiques utilisen una notació diferent: la B-spline és indexada com $B_{i,n}(x)$$n=p+1$.

Soport local

Les B-splines tenen soport local, lo que significa que els polinomis són positius solament en un àmbit finito i zero en atres llocs. La fòrmula de recursión Cox-De Boor mostra açò:

$B_{i,0}(x):=\{\begin{array}{cc}1& \mathrm{s}\mathrm{i}{t}_i\le x<t_{i+1}\\ 0& \mathrm{d}\mathrm{e}\mathrm{o}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\end{array}$

$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).$

Permetent que l'índex $k$ definixca l'interval de nucs que conté la posició, $x\in [t_k,t_{k+1}]$. Podem vore en la fòrmula de recursión que solament B-splines en $i=k-p,\dots ,k$ no són zeros per a este interval de nucs. Aixina, la suma es reduïx a:

$𝐒(x)=\sum _{i=k-p}^k{𝐜}_i{B}_{i,p}(x).$

De $i\ge 0$ es deduïx que $k\ge p$. De la mateixa manera, veem en la recursividad que l'ubicació del nuc més alt està en l'índex $k+1+p$ . Açò significa que qualsevol interval de nucs $[t_k,t_{k+1})$ que s'use realment deu tindre a lo manco $p$ nucs adicionals abans i despuix. En un programa de computadora, açò generalment es conseguix repetint la primera i l'última ubicació de nuc utilisada $p$ voltes. Per eixemple, per a $p=3$ i ubicacions de nucs reals $(0,1,2)$, un podria reblir el vector de nucs com $(0,0,0,0,1,2,2,2,2)$.

Vore també

• Algoritme de De Casteljau
• Curva de Bézier
• NURBS

Bibliografia

• Carl de Boor (2003). A Practical Guide to Splines, Revised Edition, Springer-Verlag. ISBN 0-387-95366-3.