2-D Linear Interpolation in C

Reader Mote wrote in with an interesting dsPIC programming query about estimating the value of a function of two variables using 2-D linear interpolation in a look-up table. We’re investigating how long it takes to compute a single interpolated value.

As a starting point, I’ve written the following C program to sketch out the basic calculation in a Windows console app before I even think about doing it on the dsPIC. This seems to be working, so I guess the next step is to stick it onto the dsPIC and see how it runs. However, that requires some careful thought on account of the size of the look-up table and the limited RAM on the dsPIC30F4011, which is the microcontroller I usually use.

I’ll post again once I’ve made a bit of progress on the dsPIC implementation.

// 
// 2-D linear interpolation experiment
// Written by Ted Burke
// last updated 11-3-2013
//
// To compile: gcc interpolation.c -o interpolation.exe
// To run: interpolation.exe
//

#include <stdio.h>

// This is just a dummy function for testing
double f(double x, double y)
{
	return (0.1*x*x + 0.2*y*y);
}

// M is number of rows, N is number of columns
#define M 61
#define N 20

int main()
{
	// m and n are row and column indices
	int m, n;
	double mf, nf; // fractional parts

	// x, y are the input parameters for the interpolation
	double x, y, x_min=2.0, x_max=18.0, y_min=5.0, y_max=15.0;
	
	// f is the table of function values - i.e. f(x,y)
	// Fill this with calculated values for testing
	double f_vals[M][N];
	for (m=0 ; m<M ; ++m)
	{
		for (n=0 ; n<N ; ++n)
		{
			x = x_min + (x_max - x_min) * (n / (double)(N-1));
			y = y_min + (y_max - y_min) * (m / (double)(M-1));
			f_vals[m][n] = f(x,y);
		}
	}
	
	// fi is interpolated estimate of f(x,y)
	double fi;

	// Ask for an (x,y) point to calculate f at
	printf("Please enter x and y values: ");
	scanf("%lf %lf", &x, &y);
	
	// Find integer and fractional part of column index
	nf = (N-1) * (x - x_min) / (x_max - x_min);
	n = (int)nf;
	nf = nf - n;
	
	// Find integer and fractional part of row index
	mf = (M-1) * (y - y_min) / (y_max - y_min);
	m = (int)mf;
	mf = mf - m;
	
	// Calculate interpolated estimated
	fi = (1-nf)*(1-mf)*f_vals[m][n] + nf*(1-mf)*f_vals[m][n+1]
			+ (1-nf)*mf*f_vals[m+1][n] + nf*mf*f_vals[m+1][n+1];
	
	// Print results
	printf("Actual f(x,y) = %lf\n", f(x,y));
	printf("Estimated f(x,y) = %lf\n", fi);
	
	return 0;
}

Here’s what it looked like when I compiled and ran the above code in a console window:

Screenshot of experimental 2D linear interpolation program compiling and running in console

This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to 2-D Linear Interpolation in C

  1. kappi says:

    The error increases if the value is asked near the minimums. A good one for starting though, thanks!

  2. BruteForce says:

    hi, what formula are you using when you do the final calculation of the fi?

    • batchloaf says:

      Hi BruteForce

      It’s basically just a weighted sum of the four nearest values in the 2-D array. If you think of the 2-D array as a grid where each element of the array is the value of the function at a different point in the grid, fi is an estimate of the value of the function at a point in between the grid points. If the point is equidistant from the four neighbouring grid points (i.e. right in the middle of that grid square, then the estimate is just the average of the four values. However, if the point of interest is closer to one particular corner, then the weight of that grid point’s contribution should be increased and the other three decreased accordingly. The weighting for each of the four grid points is the product of “how far across the grid square we are” (between 0 and 1) and “how far up the grid square we are” (also between 0 and 1). The four weights should add up to 1 (I think!).

      Ted

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s