Value interpolation in 2d from scattered data
c++, interpolation
Solution
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?)
Problem
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++?