Algoritmo de De Boor
En el subcampo matemático del análisis numérico, el algoritmo de De Boor[1] 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.[2][3]
Introducción
El algoritmo de De Boor es un esquema eficiente y numéricamente estable para evaluar una curva spline en posición . La curva se construye a partir de una suma de funciones B-spline multiplicada con valores vectoriales potencialmente constantes , llamados puntos de control.
Las B-splines de orden son funciones polinómicas unitarias de grado definidas sobre una cuadrícula de nudos (se utilizan índices basados en cero en adelante). El algoritmo de De Boor utiliza operaciones O(p2) + O(p) para evaluar la curva de spline. Nota: El artículo principal sobre B-splines y las publicaciones clásicas[1] utilizan una notación diferente: la B-spline es indexada como .
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[4] muestra esto::
Permitiendo que el índice defina el intervalo de nudos que contiene la posición, . Podemos ver en la fórmula de recursión que solo B-splines con no son ceros para este intervalo de nudos. Así, la suma se reduce a:
De se deduce que . Del mismo modo, vemos en la recursividad que la ubicación del nudo más alto está en el índice . Esto significa que cualquier intervalo de nudos que se use realmente debe tener al menos 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 veces. Por ejemplo, para y ubicaciones de nudos reales , uno podría rellenar el vector de nudos como .
El algoritmo
Con estas definiciones, ahora podemos describir el algoritmo de De Boor . El algoritmo no calcula las funciones de las B-splines directamente. En cambio evalúa a través de una fórmula de recursión equivalente.
Deja a ser un nuevo punto de control con para . Para la siguiente recursión es aplicada:
Una vez las iteraciones están completas, tenemos , esto significa que es el resultado deseado.
El algoritmo De Boor es más eficaz que un cálculo explícito de B-splines 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 puntos de control provisional . Cada punto de control provisional es escrito exactamente una vez y leídos dos veces. Al invertir la iteración sobre (contando hacia abajo, en vez de hacia arriba), podemos ejecutar el algoritmo con memoria para solo puntos de control provisionales, permitiendo a reutilizar la memoria para . De modo parecido, hay solo un valor de 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 para los puntos de control provisionales. La relación al índice anterior es . Por ello obtenemos el algoritmo mejorado:
Sea para . Iterar para :
- ( debe ser contado hacia abajo)
Después que las iteraciones se completan, el resultado es .
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
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
Referencias
- ↑ a b C. de Boor [1971], "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121.
- ↑ Lee, E. T. Y. (December 1982). «A Simplified B-Spline Computation Routine». Computing (Springer-Verlag) 29 (4): 365-371. doi:10.1007/BF02246763.
- ↑ Lee, E. T. Y. (1986). «Comments on some B-spline algorithms». Computing (Springer-Verlag) 36 (3): 229-238. doi:10.1007/BF02240069.
- ↑ C. de Boor, p. 90
Bibliografía
- Carl de Boor (2003). A Practical Guide to Splines, Revised Edition. Springer-Verlag. ISBN 0-387-95366-3.
Datos: Q5244271