Value interpolation in 2d from scattered data [closed]

Question

I'm looking for a way to interpolate values from some 2D scattered data. I have a 3d points that represent a terrain from which I want to interpolate intermediate points. For input (X,Y) coordinates I need Z (height) value.

This article on wikipedia may also help you understand my wishes. There is a library in matlab called triscateredinterp that I think it does what I want.

What is a lightweight way to accomplish this interpolation in C++?

Answer 1

I don't think you need 3D interpolation (triscateredinterp). You have data based on 2D inputs; the 3rd dimension is your output. If I understand correctly you want to provide a point in 2D (something between the original points, and interpolate the value.

Light weight? nearest neighbor!; then bi-linear interpolation; then bi-cubic (and others). The first is simple, the others require an increasing amount of math.

Bi-linear: For each point to be interpolated, find the nearest 3 points to your X and Y:

lat long Altitude
X1   Y1   A1
X2   Y2   A2
X3   Y3   A3

Make these matrices:

    X1   Y1   1                      A1
X = X2   Y2   1                  Y = A2
    X3   Y3   1                      A3

B is the interpolation coefficients we will calculate for those three nearest points (and can be re-used for all points in the area)

    B1
B = B2
    B3

The matrix equation is: X*B = Y

You could use brut force: Multiply both sides by XT: XT*X*B = XT*Y
Take the inverse of XT*X: B = (XT*X)^-1 *XT*Y.

Yes 3x3 matrix inversion. Tying this back to a C++ question, you might use Boost for your matrix operations.

Here is another similar C++ question: Solving a system of equations programmably?

One problem that can arise from the bi-linear technique is that as your interpolated point becomes closer to a different set of 3 values you can get some jumps (how would you interpolate 4 points in a saddle configuration?)

Answer 2

One good method for scattered points is Natural Neighbor Interpolation. You can check the implementation available in CGAL for example : http://doc.cgal.org/latest/Interpolation/index.html