What mathematical methods work for interpolation 2d to 2d functions?

Question

So we have a matrix like

12,32
24,12
...

with length 2xN and another

44,32
44,19
...

with length 2xN and there is some function f(x, y) that returns z[1], z[2]. That 2 matrices that we were given represent known value pairs for x,y and z[1],z[2]. What are interpolation formulas that would help in such case?

Answer 1

If you solve the problem for one return value, you can find two functions f_1(x,y) and f_2(x,y) by interpolation, and compose your function as f(x, y) = [f_1(x,y), f_2(x,y)]. Just pick any method for solving the interpolation function suitable for your problem.

For the actual interpolation problem in two dimensions, there are a lot of ways you can handle this. If simple is what you require, you can go with linear interpolation. If you are OK with piecewise functions, you can go for bezier curves, or splines. Or, if data is uniform, you could get away with a simple polynomial interpolation (well, not quite trivial when in 2D, but easy enough).

---

EDIT: More information and some links.

A piecewise solution is possible using Bilinear interpolation (wikipedia).

For polynomial interpolation, if your data is on a grid, you can use the following algorithm (I cannot find the reference for it, it is from memory).

If the data points are on a k by l grid, rewrite your polynomial as follows:

f(x,y) = cx_1(x)*y^(k-1) + cx_2(x)*y^(k-2) + ... + cx_k(x)

Here, each coefficient cx_i(x) is also a polynomial of degree l. The first step is to find k polynomials of degree l by interpolating each row or column of the grid. When this is done, you have l coefficient sets (or, in other words, l polynomials) as interpolation points for each cx_i(x) polynomials as cx_i(x0), cx_i(x1), ..., cx_i(xl) (giving you a total of l*k points). Now, you can determine these polynomials using the above constants as the interpolation points, which give you the resulting f(x,y).

The same method is used for bezier curves or splines. The only difference is that you use control points instead of polynomial coefficients. You first get a set of splines that will generate your data points, and then you interpolate the control points of these intermediate curves to get the control points of the surface curve.

---

Let me add an example to clarify the above algorithm. Let's have the following data points:

0,0 => 1
0,1 => 2
1,0 => 3
1,1 => 4

We start by fitting two polynomials: one for data points (0,0) and (0,1), and another for (1, 0) and (1, 1):

f_0(x) = x + 1
f_1(x) = x + 3

Now, we interpolate in the other direction to determine the coefficients.When we read these polynomial coefficients vertically, we need two polynomials. One evaluates to 1 at both 0 and 1; and another that evaluates to 1 at 0, and 3 at 1:

cy_1(y) = 1
cy_2(y) = 2*y + 1

If we combine these into f(x,y), we get:

f(x,y) = cy_1(y)*x + cy_2(y)
       = 1*x + (2*y + 1)*1
       = x + 2*y + 1