Spline interpolation is useful for creating “continuous” curves out of discrete data points. These curves are can have C1 (first derivative) and C2 (second derivative) continuity, allowing for a smooth join between segments of the curve. An algorithm for computing natural cubic splines was listed on Wikipedia, and have reproduced it here so as to have the full math -> code translation in one place.

**Definition of a Cubic Spline**

Given a list of data values

where is an n-tuple defined as

with corresponding location values defined as

we wish to compute a value of Y for any value in the range . We will do this for some $latex x_i \leq x < x_j$ by evaluating a cubic spline $latex S_i(x)$.
A cubic spline is of the form
$latex {S}_{i}(x) = a_i + b_i (x-x_i) + c_i (x-x_i)^2 + d_i (x-x_i)^3.&s=1$
where $latex (x_i, a, b, c, d)$ is a 5-tuple describing the parameters of $latex S_i(x)$.
Given our set of data $latex Y$ and locations $latex X$, we wish to find $latex n$ polynomials $latex S_i (x)$ for $latex i = 0, \dots , n-1$
such that
$latex S_i (x_i) = y_i = S_{i-1} (x_i),\quad i = 1 , \dots , n-1&s=1$
$latex S'_i (x_i) = S'_{i-1} (x_i),\quad i = 1 , \dots , n-1&s=1$
$latex S''_i (x_i) = S''_{i-1} (x_i),\quad i = 1 , \dots , n-1&s=1$
$latex S''_0 (x_0) = S''_{n-1} (x_n) = 0&s=1$
We can compute the parameters of these $latex n$ polynomials using the algorithm below.
**Computation of Cubic Spline Parameters**

Input: list of points , with , with locations

Output: list spline parameters composed of 5-tuples.

- Create new arrays of size
- Create new arrays of size
- Set
- Set
- For
- Set
- Set
- Set
- Set
- Set
- Set
- For
- Set
- Set
- Set
- For
- Set

For a C++ implementation of this algorithm, see Cubic Spline Interpolation