De Boor's algorithm: Difference between revisions

Content deleted Content added
Repository has been renamed
TN (talk | contribs)
More precise smootheness condition; (otherwise the given statement is wrong)
Line 6:
\mathbf{s}(u_{p-1})=\mathbf{d}_{p-1}</math>. But this is not quite the case: in general we are satisfied that the curve "approximates" the control polygon. We assume that ''u<sub>0</sub>, ..., u<sub>p-1</sub>'' are given to us along with <math>\mathbf{d}_0, \mathbf{d}_1, \dots, \mathbf{d}_{p-1}</math>.
 
One approach to solve this problem is by [[spline (mathematics)|spline]]s. A spline is a curve that is a piecewise ''n<sup>th</sup>'' degree polynomial. This means that, on any interval ''<nowiki>[</nowiki>u<sub>i</sub>, u<sub>i+1</sub>)'', 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 ''<nowiki>[</nowiki>u<sub>i-1</sub>, u<sub>i</sub>)'' and ''<nowiki>[</nowiki>u<sub>i</sub>, u<sub>i+1</sub>)'' meet at the point ''u<sub>i</sub>'', they must have the same value at this point and their derivatives must be equal up to order <math>n-1</math> (to ensure that the curve is as smooth as possible without restricting <math>s(x)</math> to a plain polynomial within <math>[u_{i-1},u_{i+1})</math>).
 
De Boor's algorithm is an algorithm which, given ''u<sub>0</sub>, ..., u<sub>p-1</sub>'' and <math>\mathbf{d}_0, \mathbf{d}_1, \dots, \mathbf{d}_{p-1}</math>, finds the value of spline curve <math>\mathbf{s}(x)</math> at a point ''x''. It uses [[Big O notation|O]](n<sup>2</sup>) + [[Big O notation|O]](n + p) operations where ''n'' is the degree and ''p'' the number of control points of ''s''.