In the mathematical subfield of numerical analysis de Boor's algorithm is a fast 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 Carl R. de Boor. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.
Contents
Introduction
The general setting is as follows. We would like to construct a curve whose shape is described by a sequence of p points
One approach to solve this problem is by splines. A spline is a curve that is a piecewise nth degree polynomial. This means that, on any interval [ui, ui+1), the curve must be equal to a polynomial of degree at most n. It may be equal to different polynomials on different intervals. The polynomials must be synchronized: when the polynomials from intervals [ui-1, ui) and [ui, ui+1) meet at the point ui, they must have the same value at this point and their derivatives must be equal (to ensure that the curve is smooth).
De Boor's algorithm is an algorithm which, given u0, ..., up-1 and
Outline of the algorithm
Suppose we want to evaluate the spline curve for a parameter value
where
and
Due to the spline locality property,
So the value
The algorithm
We can compute the above
Where the ratio
Doing so gives us
Computer code
TinySpline: Open source C-library for splines which implements De Boor's algorithm