SPLINE
Interpolation and Approximation of Data

SPLINE is a FORTRAN77 library which defines and evaluates spline functions.

These spline functions are typically used to

• interpolate data exactly at a set of points;
• approximate data at many points, or over an interval.

The most common use of this software is for situations where a set of (X,Y) data points is known, and it is desired to determine a smooth function which passes exactly through those points, and which can be evaluated everywhere. Thus, it is possible to get a formula that allows you to "connect the dots".

Of course, you could could just connect the dots with straight lines, but that would look ugly, and if there really is some function that explains your data, you'd expect it to curve around rather than make sudden angular turns. The functions in SPLINE offer a variety of choices for slinky curves that will make pleasing interpolants of your data.

There are a variety of types of approximation curves available, including:

• least squares polynomials,
• divided difference polynomials,
• piecewise polynomials,
• B splines,
• Bernstein splines,
• beta splines,
• Bezier splines,
• Hermite splines,
• Overhauser (or Catmull-Rom) splines.

Also included are a set of routines that return the local "basis matrix", which allows the evaluation of the spline in terms of local function data.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

SPLINE is available in a C version and a C++ version and a FORTRAN90 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

BERNSTEIN_POLYNOMIAL, a FORTRAN77 library which evaluates the Bernstein polynomials, useful for uniform approximation of functions;

CHEBYSHEV, a FORTRAN77 library which computes the Chebyshev interpolant/approximant to a given function over an interval.

DIVDIF, a FORTRAN77 library which uses divided differences to interpolate data.

HERMITE, a FORTRAN77 library which computes the Hermite interpolant, a polynomial that matches function values and derivatives.

HERMITE_CUBIC, a FORTRAN77 library which can compute the value, derivatives or integral of a Hermite cubic polynomial, or manipulate an interpolating function made up of piecewise Hermite cubic polynomials.

INTERP, a FORTRAN90 library which can be used for parameterizing and interpolating data;

LAGRANGE_INTERP_1D, a FORTRAN77 library which defines and evaluates the Lagrange polynomial p(x) which interpolates a set of data, so that p(x(i)) = y(i).

NMS, a FORTRAN77 library which includes a wide variety of numerical software, including solvers for linear systems of equations, interpolation of data, numerical quadrature, linear least squares data fitting, the solution of nonlinear equations, ordinary differential equations, optimization and nonlinear least squares, simulation and random numbers, trigonometric approximation and Fast Fourier Transforms.

PPPACK, a FORTRAN77 library which implements piecewise polynomial functions, including, in particular, cubic splines, by Carl deBoor.

TEST_APPROX, a FORTRAN77 library which defines a number of test problems for approximation and interpolation.

TEST_INTERP_1D, a FORTRAN77 library which defines test problems for interpolation of data y(x), depending on a 1D argument.

TOMS446, a FORTRAN77 library which manipulates Chebyshev series for interpolation and approximation;
this is a version of ACM TOMS algorithm 446, by Roger Broucke.

Reference:

1. JA Brewer, DC Anderson,
   Visual Interaction with Overhauser Curves and Surfaces,
   SIGGRAPH 77,
   in Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques,
   ASME, July 1977, pages 132-137.
2. Edwin Catmull, Raphael Rom,
   A Class of Local Interpolating Splines,
   in Computer Aided Geometric Design,
   edited by Robert Barnhill, Richard Reisenfeld,
   Academic Press, 1974,
   ISBN: 0120790505,
   LC: QA464.I58.
3. Samuel Conte, Carl deBoor,
   Elementary Numerical Analysis,
   Second Edition,
   McGraw Hill, 1972,
   ISBN: 07-012446-4,
   LC: QA297.C65.
4. Alan Davies, Philip Samuels,
   An Introduction to Computational Geometry for Curves and Surfaces,
   Clarendon Press, 1996,
   ISBN: 0-19-851478-6,
   LC: QA448.D38.
5. Carl deBoor,
   A Practical Guide to Splines,
   Springer, 2001,
   ISBN: 0387953663,
   LC: QA1.A647.v27.
6. Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart,
   LINPACK User's Guide,
   SIAM, 1979,
   ISBN13: 978-0-898711-72-1,
   LC: QA214.L56.
7. Gisela Engeln-Muellges, Frank Uhlig,
   Numerical Algorithms with C,
   Springer, 1996,
   ISBN: 3-540-60530-4,
   LC: QA297.E56213.
8. James Foley, Andries vanDam, Steven Feiner, John Hughes,
   Computer Graphics, Principles and Practice,
   Second Edition,
   Addison Wesley, 1995,
   ISBN: 0201848406,
   LC: T385.C5735.
9. Fred Fritsch, Judy Butland,
   A Method for Constructing Local Monotone Piecewise Cubic Interpolants,
   SIAM Journal on Scientific and Statistical Computing,
   Volume 5, Number 2, 1984, pages 300-304.
10. Fred Fritsch, Ralph Carlson,
    Monotone Piecewise Cubic Interpolation,
    SIAM Journal on Numerical Analysis,
    Volume 17, Number 2, April 1980, pages 238-246.
11. David Kahaner, Cleve Moler, Steven Nash,
    Numerical Methods and Software,
    Prentice Hall, 1989,
    ISBN: 0-13-627258-4,
    LC: TA345.K34.
12. David Rogers, Alan Adams,
    Mathematical Elements for Computer Graphics,
    Second Edition,
    McGraw Hill, 1989,
    ISBN: 0070535299,
    LC: T385.R6.

Source Code:

• spline.f, the source code;
• spline.sh, commands to compile the source code;

Examples and Tests:

• spline_prb.f, the test program;
• spline_prb.sh, commands to compile, link and run the test program;
• spline_prb_output.txt, the output file.

List of Routines:

• BASIS_FUNCTION_B_VAL evaluates the B spline basis function.
• BASIS_FUNCTION_BETA_VAL evaluates the beta spline basis function.
• BASIS_MATRIX_B_UNI sets up the uniform B spline basis matrix.
• BASIS_MATRIX_BETA_UNI sets up the uniform beta spline basis matrix.
• BASIS_MATRIX_BEZIER sets up the cubic Bezier spline basis matrix.
• BASIS_MATRIX_HERMITE sets up the Hermite spline basis matrix.
• BASIS_MATRIX_OVERHAUSER_NONUNI: nonuniform Overhauser spline basis matrix.
• BASIS_MATRIX_OVERHAUSER_NUL sets the nonuniform left Overhauser basis matrix.
• BASIS_MATRIX_OVERHAUSER_NUR: the nonuniform right Overhauser basis matrix.
• BASIS_MATRIX_OVERHAUSER_UNI sets the uniform Overhauser spline basis matrix.
• BASIS_MATRIX_OVERHAUSER_UNI_L sets the left uniform Overhauser basis matrix.
• BASIS_MATRIX_OVERHAUSER_UNI_R sets the right uniform Overhauser basis matrix.
• BASIS_MATRIX_TMP computes Q = T * MBASIS * P
• BC_VAL evaluates a parameterized N-th degree Bezier curve in 2D.
• BEZ_VAL evaluates an N-th degree Bezier function at a point.
• BP_APPROX evaluates the Bernstein polynomial approximant to F(X) on [A,B].
• BP01 evaluates the Bernstein basis polynomials for [0,1] at a point.
• BPAB evaluates the Bernstein basis polynomials for [A,B] at a point.
• CHFEV evaluates a cubic polynomial given in Hermite form.
• D3_MXV multiplies a D3 matrix times a vector.
• D3_NP_FS factors and solves an D3 system.
• D3_UNIFORM randomizes a D3 matrix.
• DATA_TO_DIF sets up a divided difference table from raw data.
• DIF_VAL evaluates a divided difference polynomial at a point.
• LEAST_SET_OLD constructs the least squares polynomial approximation to data.
• LEAST_VAL_OLD evaluates a least squares polynomial defined by LEAST_SET_OLD.
• LEAST_SET defines a least squares polynomial for given data.
• LEAST_VAL evaluates a least squares polynomial defined by LEAST_SET.
• LEAST_VAL2 evaluates a least squares polynomial defined by LEAST_SET.
• PARABOLA_VAL2 evaluates a parabolic interpolant through tabular data.
• PCHST: PCHIP sign-testing routine.
• R8_SWAP swaps two real values.
• R8_UNIFORM_01 is a portable pseudorandom number generator.
• R8VEC_BRACKET searches a sorted R8VEC for successive brackets of a value.
• R8VEC_BRACKET3 finds the interval containing or nearest a given value.
• R8VEC_DISTINCT is true if the entries in an R8VEC are distinct.
• R8VEC_EVEN returns N real values, evenly spaced between ALO and AHI.
• R8VEC_INDICATOR sets an R8VEC to the indicator vector.
• R8VEC_ORDER_TYPE determines the order type of an R8VEC.
• R8VEC_PRINT prints an R8VEC.
• R8VEC_SORT_BUBBLE_A ascending sorts an R8VEC using bubble sort.
• R8VEC_UNIFORM_01 sets a double precision vector to unit pseudorandom numbers.
• R8VEC_UNIQUE_COUNT counts the unique elements in an unsorted R8VEC.
• SPLINE_B_VAL evaluates a cubic B spline approximant.
• SPLINE_BETA_VAL evaluates a cubic beta spline approximant.
• SPLINE_BEZIER_VAL evaluates a cubic Bezier spline.
• SPLINE_CONSTANT_VAL evaluates a piecewise constant spline at a point.
• SPLINE_CUBIC_SET computes the second derivatives of a piecewise cubic spline.
• SPLINE_CUBIC_VAL evaluates a piecewise cubic spline at a point.
• SPLINE_CUBIC_VAL2 evaluates a piecewise cubic spline at a point.
• SPLINE_HERMITE_SET sets up a piecewise cubic Hermite interpolant.
• SPLINE_HERMITE_VAL evaluates a piecewise cubic Hermite interpolant.
• SPLINE_LINEAR_INT evaluates the integral of a piecewise linear spline.
• SPLINE_LINEAR_INTSET sets a piecewise linear spline with given integral properties.
• SPLINE_LINEAR_VAL evaluates a piecewise linear spline at a point.
• SPLINE_OVERHAUSER_NONUNI_VAL evaluates the nonuniform Overhauser spline.
• SPLINE_OVERHAUSER_UNI_VAL evaluates the uniform Overhauser spline.
• SPLINE_OVERHAUSER_VAL evaluates an Overhauser spline.
• SPLINE_PCHIP_SET sets derivatives for a piecewise cubic Hermite interpolant.
• SPLINE_PCHIP_VAL evaluates a piecewise cubic Hermite function.
• SPLINE_QUADRATIC_VAL evaluates a piecewise quadratic spline at a point.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the FORTRAN77 source codes.