De Boor algorithm
|
|
In the mathematical subfield of numerical analysis the De Boor 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.
Introduction
The general setting is as follows. We would like to construct a curve passing through a sequence of p points <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}<math>. The curve can be described as a function <math> \vec{s}(x)<math> of one parameter x. To pass through the sequence of points, the curve must satisfy <math>\vec{s}(u_0)=\vec{d}_0, \dots, \vec{s}(u_{p-1})=\vec{d}_{p-1}<math>. We assume that u0, ..., up-1 are given to us along with <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}<math>. This problem is called interpolation.
One approach to solving this problem is by splines. A spline is a curve that is 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 a 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 algorithm is an algorithm which, given u0, ..., up-1 and <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}<math>, finds the value of spline curve <math>\vec{s}(x)<math> at a point x. It uses O(n2) operations. Notice that the running time of the algorithm depends only on degree n and not on the number of points p.
Outline of the algorithm
Suppose we want to evaluate the spline curve for a parameter value <math> x \in [u_{\ell},u_{\ell+1}) <math>. We can express the curve as
- <math> \vec{s}(x) = \sum_{i=0}^{p-1} \vec{d}_i N_i^n(x), <math>
where Nin(x) are polynomials in x with coefficients depending on u0, ..., up but not <math>\vec{d}_i<math>. Due to the spline locality property,
- <math> \vec{s}(x) = \sum_{i=\ell-n}^{\ell} \vec{d}_i N_i^n(x) <math>
So the value <math>\vec{s}(x)<math> is determined by the controlpoints <math> \vec{d}_{\ell-n},\vec{d}_{\ell-n+1},\dots,\vec{d}_{\ell} <math>; the other control points <math>\vec{d}_i<math> have no influence. De Boor's algorithm, described in the next section, is a procedure which efficiently evaluates the expression for <math> \vec{s}(x) <math>.
The algorithm
Suppose <math> x \in [u_{\ell},u_{\ell+1}) <math> and <math> \vec{d}_i^{[0]} = \vec{d}_i <math> for i = l-n+k, ..., l. Now calculate
- <math> \vec{d}_i^{[k]} = (1-\alpha_{k,i}) \vec{d}_{i-1}^{[k-1]} + \alpha_{k,i} \vec{d}_i^{[k-1]}; \qquad k=1,\dots,n; \quad i=\ell-n+k,\dots,\ell <math>
with
- <math> \alpha_{k,i} = \frac{x-u_i}{u_{i+n+1-k}-u_i}. <math>
Then <math> \vec{s}(x) = \vec{d}_{\ell}^{[n]} <math>.