Interpolation of values ​​in 2d from scattered data

Question

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

This wikipedia article can also help you understand my wishes. Matlab has a library called triscateredinterp , which I think does what I want.

What is an easy way to do this interpolation in C ++?

Answer 1

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

A light weight? nearest neighbor !; then bilinear interpolation; then bi-cubic (and others). The first is simple, others require an increase in the amount of math.

Bi-linear: for each point interpolation, find the nearest 3 points for 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 are the interpolation coefficients that we calculate for these three nearest points (and they can be reused for all points in the region)

  B1 B = B2 B3 

Matrix Equation: X*B = Y

You can use brute force: Multiply both sides by XT: XT*X*B = XT*Y
Take the inverse XT * X: B = (XT*X)^-1 *XT*Y

Yes 3x3 matrix inversion. Having attached to the C ++ question, you can use Boost for your matrix operations.

Here is another similar question in C ++: Programmable system of equations?

One problem that can arise from the two-line method is that as your interpolated point gets closer to another set of three values, you may get some jumps (how would you interpolate 4 points in the saddle configuration?)

Answer 2

One of the good methods 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