De Boor's Algorithm
(Redirected from De Boor's algorithm)
Jump to navigation
Jump to search
A De Boor's Algorithm is a Spline Interpolation Algorithm for computing B-Spline curves that is based on a generalization of De Casteljau's algorithm.
- AKA: DeBoor-Cox Algorithm, B-Spline DeBoor Algorithm.
- Context:
- It is a fast and numerically stable algorithm for finding a point on a B-spline curve given a $u$ in the domain.
- Example(s):
- Counter-Example(s):
- See: Numerical Analysis, Carl R. de Boor, Mathematics, Numerically Stable, Algorithm, Spline Curve, B-Spline, de Casteljau's Algorithm, Bézier Curve.
References
2021a
- (MTU, 2021) ⇒ https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/de-Boor.html Retrieved:2021-9-5.
- QUOTE: De Boor's algorithm is a generalization of de Casteljau's algorithm. It provides a fast and numerically stable way for finding a point on a B-spline curve given a $u$ in the domain.
Recall from a property of multiple knots that increasing the multiplicity of an internal knot decreases the number of non-zero basis functions at this knot. In fact, if the multiplicity of this knot is $k$, there are at most $p - k + 1$ non-zero basis functions at this knot. Consequently, at a knot of multiplicity $p$, there will be only one non-zero basis function whose value at this knot is one because of the property of partition of unity. (...)
- QUOTE: De Boor's algorithm is a generalization of de Casteljau's algorithm. It provides a fast and numerically stable way for finding a point on a B-spline curve given a $u$ in the domain.
2021b
- (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/De_Boor's_algorithm Retrieved:2021-9-5.
- In the mathematical subfield of numerical analysis de Boor's algorithm[1] is a polynomial-time 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. The algorithm was devised by Carl R. de Boor. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.
- ↑ C. de Boor [1971], "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121.
2021b
- (MIT, 2021) ⇒ https://web.mit.edu/hyperbook/Patrikalakis-Maekawa-Cho/node18.html Retrieved:2021-9-5.
- QUOTE: Evaluation and subdivision algorithm: A B-spline curve can be evaluated at a specific parameter value using the de Boor algorithm, which is a generalization of the de Casteljau algorithm (...)