Wikipedia / De Boor's algorithm
Wikipedia / De Boor's algorithm
In the mathematical subfield of numerical analysis, de Boor's algorithm is a polynomial-time and numerically stable algorithm for evaluating spline curves in B-spline form. It is a generalization of de Casteljau's algorithm for Bézier curves. The algorithm was devised by German-American mathematician Carl R. de Boor. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.
Introduction
A general introduction to B-splines is given in the main article (we always use zero-based indices in the following). De Boor's algorithm uses O(p2) + O(p) operations to evaluate the spline curve. Note: the main article about B-splines and the classic publications.
Local support
B-splines have local support, meaning that the polynomials are positive only in a compact domain and zero elsewhere. The Cox-de Boor recursion formula
additional knots before and after. In a computer program.
The algorithm
through an equivalent recursion formula.
is the desired result.
with the Cox-de Boor recursion formula, because it does not compute terms which are guaranteed to be multiplied by zero.
Optimizations
used in each step, so we can reuse the memory as well.
. Thus we obtain the improved algorithm:
Note that .
Example implementation
The following code in the Python programming language is a naive implementation of the optimized algorithm.
See also
External links
Computer code
GNU Scientific Library: C-library, contains a sub-library for splines ported from PPPACK
SciPy: Python-library, contains a sub-library scipy.interpolate with spline functions based on FITPACK
TinySpline: C-library for splines with a C++ wrapper and bindings for C#, Java, Lua, PHP, Python, and Ruby
Einspline: C-library for splines in 1, 2, and 3 dimensions with Fortran wrappers
References
Works cited