De Boor's algorithm: Difference between revisions

Revision as of 21:46, 5 March 2007

Revision as of 18:59, 29 May 2007

Line 3:

== Introduction ==

The general setting is as follows. We would like to construct a curve passingwhose throughshape is described by a sequence of ''p'' points <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}</math>, which palys the role of a ''control polygon''. 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>. But this is not quite the case: in general we are satisfied that the curve "approximate" the control polygon. We assume that ''u₀, ..., u_p-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 [[spline (mathematics)|spline]]s. A spline is a curve that is piecewise ''n^th'' degree polynomial. This means that, on any interval ''<nowiki>[</nowiki>u_i, u_i+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 ''<nowiki>[</nowiki>u_i-1, u_i)'' and ''<nowiki>[</nowiki>u_i, u_i+1)'' meet at the point ''u_i'', they must have the same value at this point and their derivatives must be equal (to ensure that the curve is smooth).