In the mathematical subfield of numerical analysis, de Boor's algorithm[1] 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.
[2][3] A general introduction to B-splines is given in the main article.
Here we discuss de Boor's algorithm, an efficient and numerically stable scheme to evaluate a spline curve
The curve is built from a sum of B-spline functions
multiplied with potentially vector-valued constants
are connected piece-wise polynomial functions of degree
defined over a grid of knots
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[1] use a different notation: the B-spline is indexed as
B-splines have local support, meaning that the polynomials are positive only in a finite domain and zero elsewhere.
The Cox-de Boor recursion formula[4] shows this:
define the knot interval that contains the position,
are non-zero for this knot interval.
Similarly, we see in the recursion that the highest queried knot location is at index
In a computer program, this is typically achieved by repeating the first and last used knot location
, one would pad the knot vector to
With these definitions, we can now describe de Boor's algorithm.
The algorithm does not compute the B-spline functions
De Boor's algorithm is more efficient than an explicit calculation of B-splines
with the Cox-de Boor recursion formula, because it does not compute terms which are guaranteed to be multiplied by zero.
The algorithm above is not optimized for the implementation in a computer.
temporary control points
Each temporary control point is written exactly once and read twice.
(counting down instead of up), we can run the algorithm with memory for only
temporary control points, by letting
Thus we obtain the improved algorithm: Let
The following code in the Python programming language is a naive implementation of the optimized algorithm.