Continuing from Part I, we are discussing how to interpolate a set of data points with a smooth curve. Depending on your experience or college studies, you may have been introduced to the concept of polynomial interpolation, that is fitting a set of n points with a polynomial of degree no larger than n-1. You can read the Wikipedia article here. Looking at the example picture in the article, that looks pretty good and it’s a well-known algorithm, so why are we even talking about this spline stuff?
As it happens, there are two issues with the general polynomial interpolation algorithm. As the number of interpolation points increases, there is a tendency for the polynomial to oscillate (sometimes wildly) between points. The second, and somewhat more subtle, issue is what happens if you want to create a closed shape? Will the curve look as if it were smoothly ‘drawn’ between all the points or will there be an abrupt change in the slope of the curve at the first/last points where the curve closes?
Primarily for the former reason, the textbook polynomial interpolation is undesirable. The idea behind a spline is to use multiple polynomial curves to fit the entire data set. There is one polynomial curve between each set of data points or knots. So, if three points were interpolated with cubic curves, there would be one cubic curve fit between the first and second data points. A second cubic curve would be fit between the second and third data points.
Interior knots are sometimes called joins as these knots indicate where separate polynomial curves join together. This is illustrated in the following diagram for a cubic Bezier spline.
In this case, the spline contains four separate cubic Bezier curves. One cubic Bezier curve interpolates knots 0 and 1. The second interpolates knots 1 and 2. The third interpolates knots 2 and 3. The final cubic Bezier curve interpolates knots 3 and 4. These separate curves are sometimes called ‘segments’ of the spline.
Each Bezier curve is constructed in a manner that meets certain continuity conditions at the joins. These conditions will be discussed in part III.
The Algorithmist 
Jim,
Great post for us non-math types… I love the history in part one, because it is a great visual metaphor for what is happening. I can’t wait to see how this will be implemented in Degrafa.
– Tom
Thanks Tom – this series will end with some MXML examples of how to use the cubic Bezier spline in Degrafa beta 3.
regards,
– jim