Algoritmo de De Boor

En el subcampo matemático del análisis numérico, el algoritmo de De Boor es un algoritmo de tiempo polinomial y numéricamente estable para evaluar curvas spline en forma B-spline. Es una generalización del algoritmo Casteljau para las curvas de Bézier. El algoritmo fue ideado por Carl R. De Boor. Se han creado variantes simplificadas y potencialmente más rápidas del algoritmo de De Boor, pero sufren una estabilidad comparativamente menor.

Introducción

El algoritmo de De Boor es un esquema eficiente y numéricamente estable para evaluar una curva spline $𝐒(x)$ en posición $x$. La curva se construye a partir de una suma de funciones B-spline $B_{i,p}(x)$ multiplicada con valores vectoriales potencialmente constantes ${𝐜}_i$, llamados puntos de control.

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

Las B-splines de orden $p+1$ son funciones polinómicas unitarias de grado $p$ definidas sobre una cuadrícula de nudos $t_0,\dots ,t_i,\dots ,t_m$ (se utilizan índices basados en cero en adelante). El algoritmo de De Boor utiliza operaciones O(p²) + O(p) para evaluar la curva de spline. Nota: El artículo principal sobre B-splines y las publicaciones clásicas utilizan una notación diferente: la B-spline es indexada como $B_{i,n}(x)$$n=p+1$.

Soporte local

Las B-splines tienen soporte local, lo que significa que los polinomios son positivos solamente en un ámbito finito y cero en otros lugares. La fórmula de recursión Cox-De Boor muestra esto::

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

Permitiendo que el índice $k$ defina el intervalo de nudos que contiene la posición, $x\in [t_k,t_{k+1}]$. Podemos ver en la fórmula de recursión que solo B-splines con $i=k-p,\dots ,k$ no son ceros para este intervalo de nudos. Así, la suma se reduce a:

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

De $i\ge 0$ se deduce que $k\ge p$. Del mismo modo, vemos en la recursividad que la ubicación del nudo más alto está en el índice $k+1+p$ . Esto significa que cualquier intervalo de nudos $[t_k,t_{k+1})$ que se use realmente debe tener al menos $p$ nudos adicionales antes y después. En un programa de computadora, esto generalmente se logra repitiendo la primera y la última ubicación de nudo utilizada $p$ veces. Por ejemplo, para $p=3$ y ubicaciones de nudos reales $(0,1,2)$, uno podría rellenar el vector de nudos como $(0,0,0,0,1,2,2,2,2)$.

El algoritmo

Con estas definiciones, ahora podemos describir el algoritmo de De Boor . El algoritmo no calcula las funciones de las B-splines $B_{i,p}(x)$ directamente. En cambio evalúa $𝐒(x)$ a través de una fórmula de recursión equivalente.

Deja a ${𝐝}_{i,r}$ ser un nuevo punto de control con ${𝐝}_{i,0}:={𝐜}_i$ para $i=k-p,\dots ,k$. Para $r=1,\dots ,p$ la siguiente recursión es aplicada:

${𝐝}_{i,r}=(1-{\alpha }_{i,r}){𝐝}_{i-1,r-1}+{\alpha }_{i,r}{𝐝}_{i,r-1};i=k-p+r,\dots ,k$

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

Una vez las iteraciones están completas, tenemos $𝐒(x)={𝐝}_{k,p}$, esto significa que ${𝐝}_{k,p}$ es el resultado deseado.

El algoritmo De Boor es más eficaz que un cálculo explícito de B-splines $B_{i,p}(x)$ con la fórmula de recursión Cox-De Boor, porque no calcula términos que están garantizados para ser multiplicados por cero.

Optimizaciones

El algoritmo anterior no está optimizado para la implementación en un ordenador. Requiere memoria para $(p+1)+p+\dots +1=(p+1)(p+2)/2$ puntos de control provisional ${𝐝}_{i,r}$. Cada punto de control provisional es escrito exactamente una vez y leídos dos veces. Al invertir la iteración sobre $i$ (contando hacia abajo, en vez de hacia arriba), podemos ejecutar el algoritmo con memoria para solo $p+1$ puntos de control provisionales, permitiendo a ${𝐝}_{i,r}$ reutilizar la memoria para ${𝐝}_{i,r-1}$. De modo parecido, hay solo un valor de $\alpha$ utilizado en cada paso, de manera que podemos reutilizar la memoria también.

Además, es más conveniente utilizar un índice basado en cero $j=0,\dots ,p$ para los puntos de control provisionales. La relación al índice anterior es $i=j+k-p$. Por ello obtenemos el algoritmo mejorado:

Sea ${𝐝}_j:={𝐜}_{j+k-p}$ para $j=0,\dots ,p$. Iterar para $r=1,\dots ,p$:

${𝐝}_j:=(1-{\alpha }_j){𝐝}_{j-1}+{\alpha }_j{𝐝}_j;j=p,\dots ,r$($j$ debe ser contado hacia abajo)

${\alpha }_j:=\frac{x-t_{j+k-p}}{t_{j+1+k-r}-t_{j+k-p}}.$

Después que las iteraciones se completan, el resultado es $𝐒(x)={𝐝}_p$.

Implementación de ejemplo

El código siguiente en el lenguaje de programación de Python es una implementación inocente ("naive") del algoritmo optimizado.

def deBoor(k: int, x: int, t, c, p: int):
    """Evaluates S(x).

    Arguments
    ---------
    k: Index of knot interval that contains x.
    x: Position.
    t: Array of knot positions, needs to be padded as described above.
    c: Array of control points.
    p: Degree of B-spline.
    """
    d = [c[j + k - p] for j in range(0, p+1)]

    for r in range(1, p+1):
        for j in range(p, r-1, -1):
            alpha = (x - t[j+k-p]) / (t[j+1+k-r] - t[j+k-p])
            d[j] = (1.0 - alpha) * d[j-1] + alpha * d[j]

    return d[p]

Véase también

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

Enlaces externos

• De Boor's Algorithm

Código de ordenador

• PPPACK: Contiene muchos spline algoritmos en Fortran
• GNU Biblioteca científica: C-biblioteca, contiene un sub-biblioteca para splines ported de PPPACK
• SciPy: Pitón-biblioteca, contiene un sub-biblioteca scipy.interpolate Con spline las funciones basaron en FITPACK
• TinySpline: C-biblioteca para splines con un C++ wrapper y encuadernaciones para C#, Java, Lua, PHP, Pitón, y Ruby
• Einspline: C-biblioteca para splines en 1, 2, y 3 dimensiones con Fortran wrappers

Bibliografía

• Plantilla:Cita libro