In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
subfield of
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, de Boor's algorithm
[C. de Boor 971 "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121.] is a
polynomial-time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
and
numerically stable algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for evaluating
spline curve
In mathematics, a spline is a Function (mathematics), function defined piecewise by polynomials.
In interpolation, interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, eve ...
s in
B-spline
In numerical analysis, a B-spline (short for basis spline) is a type of Spline (mathematics), spline function designed to have minimal Support (mathematics), support (overlap) for a given Degree of a polynomial, degree, smoothness, and set of bre ...
form. It is a generalization of
de Casteljau's algorithm for
Bézier curve
A Bézier curve ( , ) is a parametric equation, parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approxima ...
s. The algorithm was devised by German-American mathematician
Carl R. de Boor. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.
Introduction
A general introduction to B-splines is given in the
main article. Here we discuss de Boor's algorithm, an efficient and numerically stable scheme to evaluate a spline curve
at position
. The curve is built from a sum of B-spline functions
multiplied with potentially vector-valued constants
, called control points,
B-splines of order
are connected piece-wise polynomial functions of degree
defined over a grid of knots
(we always use zero-based indices in the following). De Boor's algorithm uses
O(p
2) +
O(p) operations to evaluate the spline curve. Note: the
main article about B-splines and the classic publications
use a different notation: the B-spline is indexed as
with
.
Local support
B-splines have local support, meaning that the polynomials are positive only in a compact domain and zero elsewhere. The Cox-de Boor recursion formula
[C. de Boor, p. 90] shows this:
Let the index
define the knot interval that contains the position,
. We can see in the recursion formula that only B-splines with are non-zero for this knot interval. Thus, the sum is reduced to:
Python is a high-level, general-purpose programming language. Its design philosophy emphasizes code readability with the use of significant indentation.
Python is dynamically type-checked and garbage-collected. It supports multiple prog ...
is a naive implementation of the optimized algorithm.
def deBoor(k: int, x: int, t, c, p: int):
"""Evaluates S(x).
Arguments
---------
k: Index of knot interval that contains x.
x: Position.
t: Array of knot positions, needs to be padded as described above.
c: Array of control points.
p: Degree of B-spline.
"""
d = [c[j + k - p] for j in range(0, p + 1)]
for r in range(1, p + 1):
for j in range(p, r - 1, -1):
alpha = (x - t[j + k - p]) / (t[j + 1 + k - r] - t[j + k - p])
d[j] = (1.0 - alpha) * d - 1+ alpha * d
return d
See also
*
De Casteljau's algorithm
*
Bézier curve
A Bézier curve ( , ) is a parametric equation, parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approxima ...
*
Non-uniform rational B-spline
Non-uniform rational basis spline (NURBS) is a mathematical model using B-spline, basis splines (B-splines) that is commonly used in computer graphics for representing curves and Surface (mathematics), surfaces. It offers great flexibility and pr ...
External links
De Boor's Algorithm
Computer code
PPPACK contains many spline algorithms in
Fortran
GNU Scientific Library C-library, contains a sub-library for splines ported from
PPPACK
SciPy Python-library, contains a sub-library ''scipy.interpolate'' with spline functions based on
FITPACK
TinySpline C-library for splines with a C++ wrapper and bindings for C#, Java, Lua, PHP, Python, and Ruby
Einspline C-library for splines in 1, 2, and 3 dimensions with Fortran wrappers
References
Works cited
* {{cite book , author = Carl de Boor , title = A Practical Guide to Splines, Revised Edition , publisher = Springer-Verlag , year = 2003, isbn=0-387-95366-3
Articles with example Python (programming language) code
Numerical analysis
Splines (mathematics)
Interpolation