Content deleted Content added
m →Outline of the algorithm: break big equations into their own lines |
A real implementation needs to find u such that [uk, uk+1). This takes O(number knots) in worst case. |
||
Line 8:
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 (to ensure that the curve is smooth).
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>)
== Outline of the algorithm==
| |||