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 de De Casteljau para curvas de Bézier . El algoritmo fue diseñado por Carl R. de Boor . Se han creado variantes simplificadas y 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 B-splines . Aquí discutimos 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 multiplicado con constantes potencialmente vectoriales , llamados puntos de control,
B-splines de orden están conectadas funciones polinomiales de grado por partes definido sobre una cuadrícula de nudos (siempre usamos índices de base cero en lo siguiente). El algoritmo de De Boor usa operaciones O (p 2 ) + 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: el B-spline está indexado como con .
Apoyo local
Las B-splines tienen soporte local, lo que significa que los polinomios son positivos solo en un dominio finito y cero en otros lugares. La fórmula de recursividad de Cox-de Boor [4] muestra esto:
Deje que el índice definir el intervalo de nudos que contiene la posición, . Podemos ver en la fórmula de recursividad que solo B-splines conson distintos de cero para este intervalo de nudos. Así, la suma se reduce a:
Se sigue de que . De manera similar, vemos en la recursividad que la ubicación de nudo consultada más alta está en el índice. Esto significa que cualquier intervalo de nudos que se utiliza realmente debe tener al menos nudos adicionales antes y después. En un programa de computadora, esto se logra típicamente repitiendo la ubicación del primer y último nudo usadoveces. Por ejemplo, para y ubicaciones reales de nudos , uno rellenaría el vector de nudos para .
El algoritmo
Con estas definiciones, ahora podemos describir el algoritmo de De Boor. El algoritmo no calcula las funciones B-splinedirectamente. En cambio, evalúa a través de una fórmula de recursividad equivalente.
Dejar ser nuevos puntos de control con por . Para se aplica la siguiente recursividad:
Una vez que se completan las iteraciones, tenemos , significa que es el resultado deseado.
El algoritmo de De Boor es más eficiente que un cálculo explícito de B-splines con la fórmula de recursividad de Cox-de Boor, porque no calcula términos cuya multiplicación está garantizada por cero.
Optimizaciones
El algoritmo anterior no está optimizado para la implementación en una computadora. Requiere memoria para puntos de control temporales . Cada punto de control temporal se escribe exactamente una vez y se lee dos veces. Al invertir la iteración sobre (contando hacia atrás en lugar de hacia arriba), podemos ejecutar el algoritmo con memoria por solo puntos de control temporales, dejando reutilizar la memoria para . De manera similar, solo hay un valor de utilizado en cada paso, por lo que también podemos reutilizar la memoria.
Además, es más conveniente utilizar un índice de base cero. para los puntos de control temporales. La relación con el índice anterior es. Así obtenemos el algoritmo mejorado:
Dejar por . Iterar por:
- ( debe ser contado hacia atrás)
Una vez completadas las iteraciones, el resultado es .
Implementación de ejemplo
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 de 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 ]) re [ j ] = ( 1.0 - alfa ) * d [ j - 1 ] + alfa * d [ j ] volver d [ p ]
Ver también
enlaces externos
Codigo de computadora
- PPPACK : contiene muchos algoritmos spline en Fortran
- Biblioteca científica GNU : biblioteca C, contiene una subbiblioteca para splines portados desde PPPACK
- SciPy : Python-library, contiene una sub-biblioteca 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
- ^ a b C. de Boor [1971], "Paquete de subrutinas para calcular con B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; pag. 109, 121.
- ^ Lee, ETY (diciembre de 1982). "Una rutina de cálculo B-Spline simplificada". Computación . Springer-Verlag. 29 (4): 365–371. doi : 10.1007 / BF02246763 .
- ^ Lee, ETY (1986). "Comentarios sobre algunos algoritmos B-spline". Computación . Springer-Verlag. 36 (3): 229–238. doi : 10.1007 / BF02240069 .
- ↑ C. de Boor, pág. 90
Trabajos citados
- Carl de Boor (2003). Una guía práctica de splines, edición revisada . Springer-Verlag. ISBN 0-387-95366-3.