Interpolating height for a point inside a grid based on a discrete height function

Question

I have been wracking my brain to come up with a solution to this problem.

I have a lookup table that returns height values for various points (x,z) on the grid. For instance I can calculate the height at A, B, C and D in Figure 1. However, I am looking for a way to interpolate the height at P (which has a known (x,z)). The lookup table only has values at the grid intervals, and P lies between these intervals. I am trying to calculate values s and t such that:

A'(s) = A + s(C-A) B'(t) = B + t(P-B)

I would then use the these two equations to find the intersection point of B'(t) with A'(s) to find a point X on the line A-C. With this I can calculate the height at this point X and with that the height at point P.

My issue lies in calculating the values for s and t.

Any help would be greatly appreciated.

Answer 1

Try also bilinear interpolation or bicubic interpolation.

Answer 2

Depending on if you want to interpolate between ABC or ABCD the algorithm will change.

To interpolate between ABC (which I assume is what you want to do since you draw the diagonal) you will need to find the barycentric coordinates of P relative to ABC x and y positions then apply the barycentric coordinate to the height (z is assumed here) component of those triangles.

Answer 3

What about going this way: find u and v so that

  P = B + u(A-B) + v(C-B)

If you write this out, you'll see that this is a 2x2 linear system with unknowns u and v, so I guess you know how to go on from there.

Oh, and once you have u and v you use the same exact formula as above for the height, only this time A,B,C,P will be the heights at these points.

Answer 4

Considering points value are available at four corners of a square of unit length, interpolated value at any point(x,y) inside the square is given by:

f(x,y) = [ (1-y)f(0,0) + yf(0,1) ](1-x) + [ (1-y)f(1,0)+y(f(1,1)) ]x

If square has length other than 1,say L then f(x,y) is given by:

  f(x,y) = [ (L-y)f(0,0) + yf(0,L) ](L-x)/L^2 + [ (L-y)f(L,0)+y(f(L,L)) ]x/L^2

image