# Multidimensional Interpolation within a polygon

Apologies in advance if I get terminologies wrong (not sure if "multidimensional interpolation" is the right term), I'm not really that great at maths, but here goes:

Suppose we have two 2D points, point A(x1,y1) and point B(x2, y2).

If we associate both Point A and point B with a z value, then for any point P in the map, we can determine it's z value by interpolating between points A and B's z values.

So if P is right in between A and B, the z value will be the average of the two, if it's right on A it'll have A's z value etc.

(to calculate the z value, we just get the conjugate of the complex number (B - A), multiply that with (P - A) and get it's x value and then interpolate as usual.

But what about when there's 3 points, or 4 points? I gather 3 points can be done easily, I mean you can already picture the 3 points as forming a plane.

But how do I get the "z" value for 4 or more points? Because I'm using this for a game I'm developing, the 4 points would always be a polygon, and I need interpolated points that are inside an edge of the polygon (that is, right in between two neighboring points), to be in a straight line..

My current approach right now is just to split the 4 points into two triangles, but I'd like to have something easier/faster on the CPU. Is there a way to come up with the interpolation without having to calculate each sub-triangle of the polygon?

p.s I have no idea what to tag this question as

-
For 3 points, this might help: en.wikipedia.org/wiki/… but for four or more points, I guess there's not a unique choice of z-value at every point. For example, the midpoint of a square ABCD could be assigned the average of the z-values at A and C, or at B and D. –  mac May 12 '11 at 9:47
I think a useful term to learn in this connection may be barycentric coordinates, which permits "interpolation" over a triangle on any three points not on one line. For a more general (but convex) polygon the coordinates are not uniquely defined, but if the function being interpolated is linear (first-degree polynomial in cartesian coordinates), this non-uniqueness won't matter (up to rounding errors). –  hardmath May 12 '11 at 9:50

A standard quick way to interpolate among "irregular" points in a metric space (like the plane) is to pick in advance a simple continuous decreasing function of (positive) distance, such as a negative power of the distance. Use this function as the weights in a weighted mean of the corresponding $z$ values. When the weight function blows up at 0 (as with the negative power) or goes to 0 for distances greater than or equal to the smallest point-point distance, the interpolated surface will pass through the original data values.

This is known in many circles as Inverse Distance Weighted interpolation.

There are many other forms of interpolation in Euclidean spaces but IDW is one of the simplest to implement. Next simplest would likely be least squares fits (using as many parameters as there are data) and various splines. An example of the former in the case of four points is bilinear interpolation, which is equivalent to a least squares fit using the basis functions $1$, $x$, $y$, and $xy$.

It's unclear what the remarks about "need interpolated points... to be in a straight line" mean. I hope the ideas I have shared here are consistent with their intent.

-

See Barycentric Coordinates and Transfinite Interpolation, which includes many papers and presentations, including Mean Value Coordinates for Arbitrary Planar Polygons.

-
Transfinite interpolation is best thought of as "construct a roof, given that you know what the edges of your roof look like"; this might be best if the OP's polygons are rectangular... –  Ｊ. Ｍ. May 13 '11 at 0:22