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 Bzier curves.

Introduction

The general setting is as follows. We would like to construct a curve passing through a sequence of p points \vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}. The curve can be described as a function \vec{s}(x) of one parameter x. To pass through the sequence of points, the curve must satisfy \vec{s}(u_0)=\vec{d}_0, \dots, \vec{s}(u_{p-1})=\vec{d}_{p-1}. We assume that u0, ..., up-1 are given to us along with \vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}. 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 \vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}, finds the value of spline curve \vec{s}(x) 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 x \in . We can express the curve as
\vec{s}(x) = \sum_{i=0}^{p-1} \vec{d}_i N_i^n(x),
where Nin(x) are polynomials in x with coefficients depending on u0, ..., up but not \vec{d}_i. Due to the spline locality property,
\vec{s}(x) = \sum_{i=\ell-n}^{\ell} \vec{d}_i N_i^n(x)
So the value \vec{s}(x) is determined by the controlpoints \vec{d}_{\ell-n},\vec{d}_{\ell-n+1},\dots,\vec{d}_{\ell} ; the other control points \vec{d}_i have no influence. De Boor's algorithm, described in the next section, is a procedure which efficiently evaluates the expression for \vec{s}(x) .

The algorithm

Suppose x \in [u_{\ell},u_{\ell+1}) and \vec{d}_i^{[0} = \vec{d}_i for i = l-n+k, ..., l. Now calculate
\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
with
\alpha_{k,i} = \frac{x-u_i}{u_{i+n+1-k}-u_i}.
Then \vec{s}(x) = \vec{d}_{\ell}^{n} .

 

<< PreviousWord BrowserNext >>
the peak
harem anime
uss trigger (ss 564)
symbol table
bre x
lost in a good book
psychohistory (fictional)
chungking mansions
deutsch jozsa algorithm
susan calvin
u.s. robots and mechanical men
ocellated turkey
newport county
exorcist
the story of civilization
tahirid dynasty
intrinsic metric
israeli separation barrier
pueblos jvenes
supraorbital nerve
pan (novel)
robert thurman
a f records
ifk gteborg
uss haddock (ssn 621)
uss guardfish (ssn 612)
colorado state university
baron thurlow
elizabeth anania edwards
baron kenyon
hartree fock
baron auckland
the eye of argon
arthur rackham
sanday, orkney
knut vollebk
macbird
welsh hat
pparc
carrancas
xenophon of ephesus
pratt & whitney r 4360
semey
lothar matthus
Copyright 2005-2009 OnPedia.com. All Rights Reserved