Mathematics isn’t my forte. That’s why each time I have to implement some form of interpolation, I feel a headache coming up. Even simple linear interpolation has been bugging me, as it’s the same thing over and over again. One of the beauties of software development is you can write something once, and as long as it works, you don’t have to worry about it anymore. Why then, have I already implemented interpolation for around 5 different data types? My latest need for interpolation, I finally decided to put some effort into this bugger and solve it once and for all.
Armed with a recently discovered library which allows usage of generics for calculations in C#, I managed to come up with the following classes.
Implementations of AbstractInterpolation decide on the type of interpolation between certain key points. How key points should be interpreted is decided by the implementation of AbstractKeyPointCollection. The difference between the two implementations will be demonstrated later. In order to know what to interpolate (the TValue template parameter), a trivial implementation of AbstractTypeInterpolationProvider is required for the type which needs to be interpolated. All classes have a base class AbstractBasicArithmetic, which allows to do basic arithmetic operations on the specified template type TMath. This type determines the value type to use, and return for the calculations of the interpolation. They are done through a ‘Calculator‘ object, as specified in the generic calculations article. Normally you have to pass this calculator object yourself, but I created a CalculatorFactory which creates the corresponding correct calculator for known value types like double.
Perhaps, to better understand the design, a code sample is easier to demonstrate. Consider the desired result pictured in the following image. Of course to achieve drawing simple lines, better solutions exist, but for demonstration purposes, this works really well. The subsequent code sets up some points to interpolate between, and the interpolation which will be used.
CumulativeKeyPointCollection<Point, double> keyPoints = new
CumulativeKeyPointCollection<Point, double>( new PointInterpolationProvider() );
keyPoints.Add( new Point( 50, 50 ) );
keyPoints.Add( new Point( 100, 100 ) );
...
keyPoints.Add( new Point( 300, 330 ) );
LinearInterpolation<Point, double> linear = new LinearInterpolation<Point, double>( keyPoints );
CumulativeKeyPointCollection is chosen instead of AbsoluteKeyPointCollection, because every key point added to the collection ‘continues’ on the previous point. The line needs to go through the points in the order in which they were added. When using AbsoluteKeyPointCollection, every key point has an absolute position. It doesn’t matter in which order the key points are added. E.g. Interpolating between known locations at specified times, where time is then used as the absolute position.
Next, some interpolated points are calculated as follows.
List<Point> interpolatedPoints = new List<Point>();
double curPercentage = 0;
while ( curPercentage < 1 )
{
interpolatedPoints.Add( linear.Interpolate( curPercentage ) );
curPercentage += 0.001;
}
And that’s how easy interpolation can be! To achieve the result as pictured earlier, I just draw line segments between all the calculated points, and draw rectangles on top of the key points. All that remains for the code to work, is the type provider for Point which was passed to the key point collection. As you can see, that’s just a simple implementation of AbstractTypeInterpolationProvider.
/// <summary>
/// Allows AbstractInterpolation to interpolate over a list of points.
/// </summary>
public class PointInterpolationProvider : AbstractTypeInterpolationProvider<Point, double>
{
/// <summary>
/// Create a new provider to allow AbstractInterpolation to interpolate
/// between a list of points.
/// </summary>
public PointInterpolationProvider()
: base( 2 ) // The amount of dimensions this type has.
{
}
protected override double GetDimensionValue( Point value, int dimension )
{
switch ( dimension )
{
case 0:
return value.X;
case 1:
return value.Y;
default:
throw new NotSupportedException(
"Unsupported dimension while doing interpolation on type " +
typeof(Point) + "." );
}
}
public override double RelativePosition( Point from, Point to )
{
// Pythagoras to get distance.
return Math.Sqrt( Math.Pow( to.X - from.X, 2 ) + Math.Pow( to.Y + from.Y, 2 ) );
}
public override Point CreateInstance( double[] interpolated )
{
return new Point( interpolated[ 0 ], interpolated[ 1 ] );
}
}
To show the flexibility of this approach, cardinal spline interpolation is possible by just changing the used LinearInterpolation class to CardinalSplineInterpolation.
CardinalSplineInterpolation spline =
new CardinalSplineInterpolation( keyPoints );
Every time I need to implement something a bit more mathematically challenging, and search for help, I seem to end up on web pages created during the Middle Ages of the internet. Aren’t there any reuseable libraries out there which support e.g. interpolation out of the box on the actual types you want to perform it on? Like Point in the before given sample. I experience that so many libraries implement concrete implementations instead of generic solutions. For the interpolation to work I had to implement a generic binary search algorithm because SortedList (used to store the key points) didn’t support a binary search out of the box. To indicate intervals of values I had to create a generic Interval class, which I immediately could use in other source files as well. All this, of course brings some overhead with it. Instead of Donald Knuth‘s famous “premature optimization is the root of all evil” quote, I find Bill Harlan’s succinct expression even better.
It is easier to optimize correct code than to correct optimized code. – Bill Harlan
Source code can be found as part of my FCL Extension library in the Whathecode.System assembly and namespace Whathecode.System.Arithmetic.Interpolation.
whatheco.de 
One thought on “Interpolation no more”