.gif)
Spline (mathematics)
Encyclopedia
In mathematics
, a spline is a sufficiently smooth piecewise
-polynomial function
. In interpolating
problems, spline interpolation
is often preferred to polynomial interpolation
because it yields similar results, even when using low-degree polynomials, while avoiding Runge's phenomenon
for higher degrees.
In computer graphics
splines are popular curves because of the simplicity of their construction, their ease and accuracy of evaluation, and their capacity to approximate complex shapes through curve fitting
and interactive curve design.
The term spline comes from the flexible spline
devices used by shipbuilders and drafters to draw smooth shapes.
The most commonly used splines are cubic spline, i.e., of order 3—in particular, cubic B-spline
and cubic Bézier spline
. They are common, in particular, in spline interpolation
simulating the function of flat spline
s.
-polynomial
real
function
on an interval [a,b] composed of k ordered disjoint subintervals
with
.
The restriction of S to an interval i is a polynomial
,
so that
The highest order of the polynomials
is said to be the order of the spline S. If all subintervals are of the same length, the spline is said to be uniform and non-uniform otherwise.
The idea is to choose the polynomials in a way that guarantees sufficient smoothness of S. Specifically, for a spline of order n, S is required to be continuously differentiable to order n-1 at the interior points
: for all 
and all 
,
.
for which
.
A simple example of a cubic spline is
as
and
An example of using a cubic spline to create a bell shaped curve is the Irwin-Hall polynomials:
were used but polynomials were generally preferred. With the advent of computers, splines first replaced polynomials in interpolation, and then served in construction of smooth and flexible shapes in computer graphics.
It is commonly accepted that the first mathematical reference to splines is the 1946 paper by Schoenberg
, which is probably the first place that the word "spline" is used in connection with smooth, piecewise polynomial approximation. However, the ideas have their roots in the aircraft and shipbuilding industries. In the foreword to (Bartels et al., 1987), Robin Forrest describes "lofting
", a technique used in the British aircraft industry during World War II
to construct templates for airplanes by passing thin wooden strips (called "spline
s") through points laid out on the floor of a large design loft, a technique borrowed from ship-hull design. For years the practice of ship design had employed models to design in the small. The successful design was then plotted on graph paper and the key points of the plot were re-plotted on larger graph paper to full size. The thin wooden strips provided an interpolation of the key points into smooth curves. The strips would be held in place at discrete points (called "ducks" by Forrest; Schoenberg used "dogs" or "rats") and between these points would assume shapes of minimum strain energy. According to Forrest, one possible impetus for a mathematical model for this process was the potential loss of the critical design components for an entire aircraft should the loft be hit by an enemy bomb. This gave rise to "conic lofting", which used conic sections to model the position of the curve between the ducks. Conic lofting was replaced by what we would call splines in the early 1960s based on work by J. C. Ferguson at Boeing
and (somewhat later) by M.A. Sabin at British Aircraft Corporation
.
The word "spline" was originally an East Anglian
dialect word.
The use of splines for modeling automobile bodies seems to have several independent beginnings. Credit is claimed on behalf of de Casteljau
at Citroën
, Pierre Bézier
at Renault
, and Birkhoff
, Garabedian, and de Boor
at General Motors (see Birkhoff and de Boor, 1965), all for work occurring in the very early 1960s or late 1950s. At least one of de Casteljau's papers was published, but not widely, in 1959. De Boor's work at General Motors resulted in a number of papers being published in the early 1960s, including some of the fundamental work on B-splines.
Work was also being done at Pratt & Whitney Aircraft, where two of the authors of (Ahlberg et al., 1967) — the first book-length treatment of splines — were employed, and the David Taylor Model Basin
, by Feodor Theilheimer. The work at General Motors is detailed nicely in (Birkhoff, 1990) and (Young, 1997). Davis (1997) summarizes some of this material.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a spline is a sufficiently smooth piecewise
Piecewise
On mathematics, a piecewise-defined function is a function whose definition changes depending on the value of the independent variable...
-polynomial function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
. In interpolating
Interpolation
In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
problems, spline interpolation
Spline interpolation
In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. Spline interpolation is preferred over polynomial interpolation because the interpolation error can be made small even...
is often preferred to polynomial interpolation
Polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial: given some points, find a polynomial which goes exactly through these points.- Applications :...
because it yields similar results, even when using low-degree polynomials, while avoiding Runge's phenomenon
Runge's phenomenon
In the mathematical field of numerical analysis, Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree...
for higher degrees.
In computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
splines are popular curves because of the simplicity of their construction, their ease and accuracy of evaluation, and their capacity to approximate complex shapes through curve fitting
Curve fitting
Curve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data is required, or smoothing, in which a "smooth" function...
and interactive curve design.
The term spline comes from the flexible spline
Flat spline
A spline or the more modern term flexible curve consists of a long strip fixed in position at a number of points that relaxes to form and hold a smooth curve passing through those points for the purpose of transferring that curve to another material....
devices used by shipbuilders and drafters to draw smooth shapes.
The most commonly used splines are cubic spline, i.e., of order 3—in particular, cubic B-spline
B-spline
In the mathematical subfield of numerical analysis, a B-spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. B-splines were investigated as early as the nineteenth century by Nikolai Lobachevsky...
and cubic Bézier spline
Bézier spline
In the mathematical field of numerical analysis and in computer graphics, a Bézier spline is a spline curve where each polynomial of the spline is in Bézier form....
. They are common, in particular, in spline interpolation
Spline interpolation
In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. Spline interpolation is preferred over polynomial interpolation because the interpolation error can be made small even...
simulating the function of flat spline
Flat spline
A spline or the more modern term flexible curve consists of a long strip fixed in position at a number of points that relaxes to form and hold a smooth curve passing through those points for the purpose of transferring that curve to another material....
s.
Definition
A spline is a piecewisePiecewise
On mathematics, a piecewise-defined function is a function whose definition changes depending on the value of the independent variable...
-polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
on an interval [a,b] composed of k ordered disjoint subintervals
with.The restriction of S to an interval i is a polynomial
,so that
The highest order of the polynomials
is said to be the order of the spline S. If all subintervals are of the same length, the spline is said to be uniform and non-uniform otherwise.The idea is to choose the polynomials in a way that guarantees sufficient smoothness of S. Specifically, for a spline of order n, S is required to be continuously differentiable to order n-1 at the interior points
: for all and all ,.Derivation of a Cubic Spline interpolating between points
This is one of the most important uses of splines. The algorithm for this is given in the article Spline interpolationSpline interpolation
In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. Spline interpolation is preferred over polynomial interpolation because the interpolation error can be made small even...
Examples
A simple example of a quadratic spline (a spline of degree 2) isfor which
.A simple example of a cubic spline is
as
and
An example of using a cubic spline to create a bell shaped curve is the Irwin-Hall polynomials:
History
Before computers were used, numerical calculations were done by hand. Functions such as the step functionStep function
In mathematics, a function on the real numbers is called a step function if it can be written as a finite linear combination of indicator functions of intervals...
were used but polynomials were generally preferred. With the advent of computers, splines first replaced polynomials in interpolation, and then served in construction of smooth and flexible shapes in computer graphics.
It is commonly accepted that the first mathematical reference to splines is the 1946 paper by Schoenberg
Isaac Jacob Schoenberg
Isaac Jacob Schoenberg was a Romanian mathematician, known for his discovery of splines.He studied at the University of Iaşi, receiving his M.A. in 1922. From 1922 to 1925 he studied at the Universities of Berlin and Göttingen, working on a topic in analytic number theory suggested by Issai Schur...
, which is probably the first place that the word "spline" is used in connection with smooth, piecewise polynomial approximation. However, the ideas have their roots in the aircraft and shipbuilding industries. In the foreword to (Bartels et al., 1987), Robin Forrest describes "lofting
Lofting
Lofting is a Drafting technique whereby curved lines are drawn on wood and the wood then cut for advanced woodworking...
", a technique used in the British aircraft industry during World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
to construct templates for airplanes by passing thin wooden strips (called "spline
Flat spline
A spline or the more modern term flexible curve consists of a long strip fixed in position at a number of points that relaxes to form and hold a smooth curve passing through those points for the purpose of transferring that curve to another material....
s") through points laid out on the floor of a large design loft, a technique borrowed from ship-hull design. For years the practice of ship design had employed models to design in the small. The successful design was then plotted on graph paper and the key points of the plot were re-plotted on larger graph paper to full size. The thin wooden strips provided an interpolation of the key points into smooth curves. The strips would be held in place at discrete points (called "ducks" by Forrest; Schoenberg used "dogs" or "rats") and between these points would assume shapes of minimum strain energy. According to Forrest, one possible impetus for a mathematical model for this process was the potential loss of the critical design components for an entire aircraft should the loft be hit by an enemy bomb. This gave rise to "conic lofting", which used conic sections to model the position of the curve between the ducks. Conic lofting was replaced by what we would call splines in the early 1960s based on work by J. C. Ferguson at Boeing
Boeing
The Boeing Company is an American multinational aerospace and defense corporation, founded in 1916 by William E. Boeing in Seattle, Washington. Boeing has expanded over the years, merging with McDonnell Douglas in 1997. Boeing Corporate headquarters has been in Chicago, Illinois since 2001...
and (somewhat later) by M.A. Sabin at British Aircraft Corporation
British Aircraft Corporation
The British Aircraft Corporation was a British aircraft manufacturer formed from the government-pressured merger of English Electric Aviation Ltd., Vickers-Armstrongs , the Bristol Aeroplane Company and Hunting Aircraft in 1960. Bristol, English Electric and Vickers became "parents" of BAC with...
.
The word "spline" was originally an East Anglian
East Anglian English
East Anglian English is a dialect of English spoken in East Anglia. This easternmost area of England was probably home to the first-ever form of language which can be called English...
dialect word.
The use of splines for modeling automobile bodies seems to have several independent beginnings. Credit is claimed on behalf of de Casteljau
Paul de Casteljau
Paul de Casteljau is a French physicist and mathematician. In 1959, while working at Citroën, he developed an algorithm for computation of Bézier curves, which would later be formalized and popularized by engineer Pierre Bézier...
at Citroën
Citroën
Citroën is a major French automobile manufacturer, part of the PSA Peugeot Citroën group.Founded in 1919 by French industrialist André-Gustave Citroën , Citroën was the first mass-production car company outside the USA and pioneered the modern concept of creating a sales and services network that...
, Pierre Bézier
Pierre Bézier
Pierre Étienne Bézier was a French engineer and one of the founders of the fields of solid, geometric and physical modeling as well as in the field of representing curves, especially in CAD/CAM systems...
at Renault
Renault
Renault S.A. is a French automaker producing cars, vans, and in the past, autorail vehicles, trucks, tractors, vans and also buses/coaches. Its alliance with Nissan makes it the world's third largest automaker...
, and Birkhoff
Garrett Birkhoff
Garrett Birkhoff was an American mathematician. He is best known for his work in lattice theory.The mathematician George Birkhoff was his father....
, Garabedian, and de Boor
Carl R. de Boor
Carl-Wilhelm Reinhold de Boor is a German-American mathematician and professor emeritus at the University of Wisconsin–Madison.-Early life:...
at General Motors (see Birkhoff and de Boor, 1965), all for work occurring in the very early 1960s or late 1950s. At least one of de Casteljau's papers was published, but not widely, in 1959. De Boor's work at General Motors resulted in a number of papers being published in the early 1960s, including some of the fundamental work on B-splines.
Work was also being done at Pratt & Whitney Aircraft, where two of the authors of (Ahlberg et al., 1967) — the first book-length treatment of splines — were employed, and the David Taylor Model Basin
David Taylor Model Basin
The David Taylor Model Basin is one of the largest ship model basins — test facilities for the development of ship design — in the world...
, by Feodor Theilheimer. The work at General Motors is detailed nicely in (Birkhoff, 1990) and (Young, 1997). Davis (1997) summarizes some of this material.
Theory
- Cubic Splines Module Prof. John H. Mathews California State University, FullertonCalifornia State University, FullertonCalifornia State University, Fullerton is a public university located in Fullerton, California. It is the largest institution in the CSU System by enrollment, it offers long-distance education and adult-degree programs...
- Spline Curves, Prof. Donald H. House Clemson UniversityClemson UniversityClemson University is an American public, coeducational, land-grant, sea-grant, research university located in Clemson, South Carolina, United States....
- An Interactive Introduction to Splines, ibiblio.org
- Introduction to Splines, codeplea.com
Excel functions
- Open source Excel cubic spline User Defined Function
- SRS1 Cubic Spline for Excel - Free Excel cubic spline function (with utility to embed spline function code into any workbook)
Online utilities
- Online Cubic Spline Interpolation Utility
- Learning by Simulations Interactive simulation of various cubic splines
- Symmetrical Spline Curves, an animation by Theodore GrayTheodore GrayTheodore W. Gray is one of the founders of Wolfram Research and is currently Wolfram's Director of User Interface Technology.He is a prominent element collector and created a wooden periodic table with compartments for samples of each of the elements...
, The Wolfram Demonstrations Project, 2007.
Computer code
- Notes, PPT, Mathcad, Maple, Mathematica, Matlab, Holistic Numerical Methods Institute
- various routines, NTCC
- Sisl: Opensource C-library for NURBS, SINTEF
- Closed Bezier Spline, C#, WPF, Oleg V. Polikarpotchkin
- Bezier Spline from 2D Points, C#, WPF, Oleg V. Polikarpotchkin