Linear interpolation code on wikipedia - I don't understand it

Question

I'm reading the following code (taken from here)

void linear_interpolation_CPU(float2* result, float2* data, 
                              float* x_out, int M, int N) {     
    float a;
    for(int j = 0; j < N; j++) {
        int k = floorf(x_out[j]);
        a = x_out[j] - floorf(x_out[j]);
        result[j].x = a*data[k+1].x + (-data[k].x*a + data[k].x);
        result[j].y = a*data[k+1].y + (-data[k].y*a + data[k].y);
    }   
}

but I don't get it.

Why isn't the result[y] calculated by using the

formula?

Answer 1

It is calculated that way.

Look at the first two lines:

int k = floorf(x_out[j]);
a = x_out[j] - floorf(x_out[j]);

The first line defines x0 using the floor function. This is because the article assumes a lattice spacing of one for the sample points, as per the line:

the samples are obtained on the 0,1,...,M lattice

Now we could rewrite the second line for clarity as:

a = x_out[j] - k;

The second line is therefore x-x0.

Now, let us examine the equation:

result[j].y = a*data[k+1].y + (-data[k].y*a + data[k].y);

Rewriting this in terms of y, x, and x0 gives:

y = (x-x0)*data[k+1].y + (-data[k].y*(x-x0) + data[k].y);

Let's rename data[k+1].y as y1 and data[k].y as y0:

y = (x-x0)*y1 + (-y0*(x-x0) + y0);

Let's rearrange this by pulling out x-x0:

y = (x-x0)*(y1-y0) + y0;

And rearrange again:

y = y0 + (y1-y0)*(x-x0);

Again, the lattice spacing is important:

the samples are obtained on the 0,1,...,M lattice

Thus, x1-x0 is always 1. If we put it back in, we get

y = y0 + (y1-y0)*(x-x0)/(x1-x0);

Which is just the equation you were looking for.

Granted, it's ridiculous that the code is not written so as to make that apparent.