Cubic spline extrapolation

Question

I have a nice cubic spline code but it is for interpolation only. I need to extrapolate just a little into the future. Does anyone know of a good source of code, not a library, for doing this?

This is the code I wrote in basic (now ASM) for interpolation.

Answer 1

You don't need new code for that.

To extrapolate the spline you can extrapolate the parameters of the first and last spline.

Depending on your existing code/library that might not be possible without modifying the code. In that case just prepend/append two other points to the beginning/end of your list of points. You can get those two points by linearily interpolating between the first/last two points.

Be careful: Depending on the original meaning of the points that extrapolation might be completely inappropriate, especially when it comes to statistical data. In that case you should consider using regression analysis.

Answer 2

For simplicity, I'm going to represent a cubic Bezier curve as 4 points (A, B, C, D), where A and D are the endpoints of the curve, and B and C are the "control handle points". (The actual curve usually does not touch the control handle points).

See "Don Lancaster's Guru's Lair Cubic Spline Library" for ways to convert this representation of a cubic Bezier curve into other popular representations.

interpolation

Given one cubic Bezier curve (P0, P1, P2, P3), we use De Casteljau's algorithm to chop a Bezier curve into a left half and a right half. This is super-easy even on a microcontroller that doesn't have a "multiply" instruction, because it only requires calculating a few averages until we get a midpoint:

P0
   F0 := average(P0, P1)
P1                       S0 := average(F0, F1)
   F1 := average(P1, P2)         Midpoint := average(S0, S1)
P2                       S1 := average(F1, F2)
   F2 := average(P2, P3)
P3

The entire Bezier curve is (P0, P1, P2, P3).

The left half of that entire Bezier curve is the Bezier curve (P0, F0, S0, M).

The right half of that entire Bezier curve is the Bezier curve (M, S1, F2, P3).

Many microcontrollers continue to divide each curve up into smaller and smaller little curves until each piece is small enough to approximate with a straight line.

But we want to go the other way -- extrapolate out to a bigger curve.

extrapolation

Given either the left half or the right half, we can run this in reverse to recover the original curve.

Let's imagine that we forgot the original points P1, P2, P3.

Given the left half of a Bezier curve (P0, F0, S0, M), we can extrapolate to the right with:

S1 := M + (M - S0)
F1 := S0 + (S0 - F0)
P1 := F0 + (F0 - P0)

then use those values to calculate

F2 := S1 + (S1 - F1)
P2 := F1 + (F1 - P1)

and finally

P3 := F2 + (F2 - P2)

to extrapolate and recover the extrapolated Bazier curve (P0, P1, P2, P3).

details

The extrapolated curve (P0, P1, P2, P3) passes through every point in the original curve (P0, F0, S0, M) -- in particular, starting at P0 and passing through the midpoint M -- and keeps on going until it reaches P3.

We can always extrapolate from any 4 points (P0, F0, S0, M), whether or not those 4 points were originally calculated as the left half (or right half) of some larger Bezier spline.

I'm sure you already know this, but just for clarity:

Midpoint = average(F0, F1)

means "find the Midpoint exactly halfway between points F0 and F1", or in other words,

Midpoint.x = (F0.x + F1.x)/2
Midpoint.y = (F0.y + F1.y)/2
Midpoint.z = (F0.z + F1.z)/2

The expression

S1 := M + (M - S0)

means "Given a line segment, with one end at S0, and the midpoint at M, start at S0 and run in a straight line past M until you reach the other end at S1", or in other words (unless you have a decent vector library) 3 lines of code

S1.x := M.x + (M.x - S0.x)
S1.y := M.y + (M.y - S0.y)
S1.z := M.z + (M.z - S0.z)

. (If you're doing 2D, skip all the "z" stuff -- it's always zero).