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?

Accepted Answer

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.

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

Solution

Problem