Algoritmo de De Boor

Método de evaluación de curvas spline

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

Introducción

En el artículo principal se ofrece una introducción general a las B-splines . Aquí analizamos el algoritmo de De Boor, un esquema eficiente y numéricamente estable para evaluar una curva spline en la posición . La curva se construye a partir de una suma de funciones B-spline multiplicadas por constantes potencialmente de valor vectorial , llamadas puntos de control, las B-splines de orden son funciones polinómicas conectadas por partes de grado definido sobre una cuadrícula de nodos (siempre usamos índices basados ​​en cero en lo sucesivo). El algoritmo de De Boor utiliza operaciones O (p ² ) + O (p) para evaluar la curva spline. Nota: el artículo principal sobre B-splines y las publicaciones clásicas ^[1] utilizan una notación diferente: la B-spline se indexa como con . ${\displaystyle \mathbf {S} (x)}$ ${\displaystyle x}$ ${\displaystyle B_{i,p}(x)}$ ${\displaystyle \mathbf {c} _{i}}$ $${\displaystyle \mathbf {S} (x)=\sum _{i}\mathbf {c} _{i}B_{i,p}(x).}$$ ${\displaystyle p+1}$ ${\displaystyle p}$ ${\displaystyle {t_{0},\dots ,t_{i},\dots ,t_{m}}}$ ${\displaystyle B_{i,n}(x)}$ ${\displaystyle n=p+1}$

Soporte local

Las b-splines tienen soporte local, lo que significa que los polinomios son positivos solo en un dominio finito y cero en el resto del mundo. La fórmula de recursión de Cox-de Boor ^[4] lo demuestra: $${\displaystyle B_{i,0}(x):={\begin{cases}1&{\text{if }}\quad t_{i}\leq x<t_{i+1}\\0&{\text{otherwise}}\end{cases}}}$$ $${\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).}$$

Dejemos que el índice defina el intervalo de nudos que contiene la posición, . Podemos ver en la fórmula de recursión que solo los B-splines con son distintos de cero para este intervalo de nudos. Por lo tanto, la suma se reduce a: ${\displaystyle k}$ ${\displaystyle x\in [t_{k},t_{k+1})}$ ${\displaystyle i=k-p,\dots ,k}$ $${\displaystyle \mathbf {S} (x)=\sum _{i=k-p}^{k}\mathbf {c} _{i}B_{i,p}(x).}$$

De ello se desprende que . De manera similar, vemos en la recursión que la ubicación de nudo consultada más alta está en el índice . Esto significa que cualquier intervalo de nudo que se utilice realmente debe tener al menos nudos adicionales antes y después. En un programa informático, esto se consigue normalmente repitiendo los tiempos de la primera y la última ubicación de nudo utilizada. Por ejemplo, para las ubicaciones de nudo reales y , se rellenaría el vector de nudo con . ${\displaystyle i\geq 0}$ ${\displaystyle k\geq p}$ ${\displaystyle k+1+p}$ ${\displaystyle [t_{k},t_{k+1})}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p=3}$ ${\displaystyle (0,1,2)}$ ${\displaystyle (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 B-spline directamente, sino que las evalúa mediante una fórmula de recursión equivalente. ${\displaystyle B_{i,p}(x)}$ ${\displaystyle \mathbf {S} (x)}$

Sean nuevos puntos de control con para . Para se aplica la siguiente recursión: ${\displaystyle \mathbf {d} _{i,r}}$ ${\displaystyle \mathbf {d} _{i,0}:=\mathbf {c} _{i}}$ ${\displaystyle i=k-p,\dots ,k}$ ${\displaystyle r=1,\dots ,p}$ $${\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}}}.}$$

Una vez completadas las iteraciones, tenemos , lo que significa que es el resultado deseado. ${\displaystyle \mathbf {S} (x)=\mathbf {d} _{k,p}}$ ${\displaystyle \mathbf {d} _{k,p}}$

El algoritmo de De Boor es más eficiente que un cálculo explícito de B-splines con la fórmula de recursión de Cox-de Boor, porque no calcula términos que se garantiza que se multiplicarán por cero. ${\displaystyle B_{i,p}(x)}$

Optimizaciones

El algoritmo anterior no está optimizado para su implementación en una computadora. Requiere memoria para los puntos de control temporales . Cada punto de control temporal se escribe exactamente una vez y se lee dos veces. Al invertir la iteración (contando hacia atrás en lugar de hacia arriba), podemos ejecutar el algoritmo con memoria solo para los puntos de control temporales, permitiendo que se reutilice la memoria para . De manera similar, solo se utiliza un valor de en cada paso, por lo que también podemos reutilizar la memoria. ${\displaystyle (p+1)+p+\dots +1=(p+1)(p+2)/2}$ ${\displaystyle \mathbf {d} _{i,r}}$ ${\displaystyle i}$ ${\displaystyle p+1}$ ${\displaystyle \mathbf {d} _{i,r}}$ ${\displaystyle \mathbf {d} _{i,r-1}}$ ${\displaystyle \alpha }$

Además, resulta más conveniente utilizar un índice de base cero para los puntos de control temporales. La relación con el índice anterior es . De esta forma obtenemos el algoritmo mejorado: ${\displaystyle j=0,\dots ,p}$ ${\displaystyle i=j+k-p}$

Sea para . Iterar para : Nótese que j debe contarse hacia atrás. Una vez que se completan las iteraciones, el resultado es . ${\displaystyle \mathbf {d} _{j}:=\mathbf {c} _{j+k-p}}$ ${\displaystyle j=0,\dots ,p}$ ${\displaystyle r=1,\dots ,p}$ $${\displaystyle \mathbf {d} _{j}:=(1-\alpha _{j})\mathbf {d} _{j-1}+\alpha _{j}\mathbf {d} _{j};\quad j=p,\dots ,r\quad }$$ $${\displaystyle \alpha _{j}:={\frac {x-t_{j+k-p}}{t_{j+1+k-r}-t_{j+k-p}}}.}$$ ${\displaystyle \mathbf {S} (x)=\mathbf {d} _{p}}$

Ejemplo de implementación

El siguiente código en el lenguaje de programación Python es una implementación ingenua del algoritmo optimizado.

def  deBoor ( k :  int ,  x :  int ,  t ,  c ,  p :  int ): """Evalúa S(x). Argumentos --------- k: Índice del intervalo de nudos que contiene x. x: Posición. t: Matriz de posiciones de nudos, debe rellenarse como se describe arriba. c: Matriz de puntos de control. p: Grado de B-spline. """ d  =  [ c [ j  +  k  -  p ]  para  j  en  el rango ( 0 ,  p  +  1 )]  para  r  en  el rango ( 1 ,  p  +  1 ): para  j  en  el rango ( 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 ] volver  d [ p ]

Véase también

• Algoritmo de De Casteljau
• Curva de Bézier
• B-spline racional no uniforme

Enlaces externos

• Algoritmo de De Boor
• El cálculo de DeBoor-Cox

Código de computadora

• PPPACK: contiene muchos algoritmos spline en Fortran
• Biblioteca científica GNU: biblioteca C, contiene una subbiblioteca para splines trasladada desde PPPACK
• SciPy: biblioteca de Python que contiene una subbiblioteca scipy.interpolate con funciones spline basadas en FITPACK
• TinySpline: biblioteca C para splines con un contenedor C++ y enlaces para C#, Java, Lua, PHP, Python y Ruby
• Einspline: biblioteca C para splines en 1, 2 y 3 dimensiones con envoltorios Fortran

Referencias

1. C. de Boor [1971], "Paquete de subrutinas para calcular con B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; pág. 109, 121.
2. Lee, ETY (diciembre de 1982). "Una rutina de cálculo B-Spline simplificada". Computing . 29 (4). Springer-Verlag: 365–371. doi :10.1007/BF02246763. S2CID  2407104.
3. Lee, ETY (1986). "Comentarios sobre algunos algoritmos B-spline". Computing . 36 (3). Springer-Verlag: 229–238. doi :10.1007/BF02240069. S2CID  7003455.
4. C. de Boor, pág. 90

Obras citadas

• Carl de Boor (2003). Una guía práctica para splines, edición revisada . Springer-Verlag. ISBN 0-387-95366-3.