Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
2  
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
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... –  J. M. May 13 '11 at 0:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.