Cubic spline interpolation is a simple way to obtain a smooth curve from a set of discrete points (knots). It has both C1 (first derivative) and C2 (second derivative) continuity, enabling it to produce a continuous piecewise function given a set of data points.

From the algorithm detailed below I have implemented a clamped cubic spline class in C++. It is templated on the type of X and Y, allowing for use of scalar or vector types. It requires only that X and Y define the operators +, -, *, and /, and that Y have a constructor that takes a single scalar argument, initializing all elements to the supplied value.

Usage is very simple. For example, to interpolate a 2D location over time, try this:

The code for the spline class is below:

# Math

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 $y_n$ is an n-tuple defined as

with corresponding location values $X$ defined as

we wish to compute a value of Y for any value in the range $[x_0, x_n]$. We will do this for some $x_i \leq x < x_j$ by evaluating a cubic spline $S_i(x)$.

A cubic spline is of the form:

where $(x_i, a, b, c, d)$ is a 5-tuple describing the parameters of $S_i(x)$. Given our set of data $Y$ and locations $X$, we wish to find $n$ polynomials $S_i (x)$ for $i = 0, \dots , n-1$ such that

We can compute the parameters of these $n$ polynomials using the algorithm below.

#### Computation of Cubic Spline Parameters

Input: list of points $Y$, with $\left| Y \right| =n+1$, with locations $X$

Output: list spline parameters composed of $n$ 5-tuples.

1. Create new arrays $a, b, d$ of size $n$
2. Create new arrays $c, h, l, u, z$ of size $n+1$
3. Set $l_0 = 1, u_0 = z_0 = 0$
4. Set $h_0 = x_1 - x_0$
5. For $i = 1, \dots, n-1$
1. Set $h_i = x_{i+1} - x_i$
2. Set $l_i = 2 \left ( x_{i+1} - x_{i-1} \right ) - h_{i-1}u_{i-1}$
3. Set $u_i = \frac{h_i}{l_i}$
4. Set $a_i = \frac{3}{h_i} \left ( y_{i+1} - y_i \right ) - \frac{3}{h_{i-1}} \left ( y_i - y_{i-1} \right )$
5. Set $z_i = \frac{a_i - h_{i-1}z_{i-1}}{l_i}$
6. Set $l_n = 1, z_n = c_n = 0$
7. For $j = n-1, n-2, \dots, 0$
1. Set $c_j = z_j - u_j c_{j+1}$
2. Set $b_j = \frac{y_{j+1} - y_j}{h_j} - \frac{h_j \left( c_{j+1} + 2c_j \right)}{3}$
3. Set $d_j = \frac{c_{j+1} - c_j}{3h_j}$
8. For $i = 0, \dots, n-1$
1. Set $S_{i,\left(x_i,a,b,c,d\right)} = \left( x_i, y_i, b_i, c_i, d_i \right)$