Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Interpolation of a triangle

I have a unit right triangle and a value at each of the 3 vertices. I need to interpolate to find the value at a point inside the triangle. Hours of searching have turned up nothing that actually tells me how to do this. Here is my closest attempt, which is actually pretty close but not quite right -

                result = 
                v1 * (1 - x) * (1 - y) +
                v2 * x * (1 - y) +
                v3 * x * y;

v1, v2, and v3 are the values at the 3 vertices of the triangle. (x, y) is the point in the triangle that you are trying to find the value of.

Any kind of method would help me here. It doesn't necessarily need to be a unit/right triangle.

Updated info: I have a grid of evenly spaced points and a value at each point. I make a triangle out of the nearest 3 points on the grid. Here is a picture to illustrate it - enter image description here
So I have to interpolate between 5, 3, and 7 to find the value of x. The point could also be inside the other triangle, meaning you would interpolate between 5, 7, and the value of the bottom left corner of the square.

In the code I showed, v1 = 5, v2 = 3, v3 = 7.
x is the fractional distance (range [0-1]) in the "x" direction, and y is the fractional distance in the "y" direction.
In the picture's example, x would probably be about 0.75 and y would be about 0.2

Here are my closest attempts -
enter image description here
Created using -

        if (x > y) //if x > y then the point is in the upper right triangle
            return
                v1 * (1 - x) * (1 - y) +
                v2 * x * (1 - y) +
                v3 * x * y;
        else //bottom left triangle
            return
                v1 * (1 - x) * (1 - y) +
                v4 * (1 - x) * y +
                v3 * x * y;

And another attempt -
enter image description here
Created using -

if (x > y)
            return
                (1 - x) * v1 + (x - y) * v2 + y * v3;
        else
            return
                (1 - y) * v1 + (y - x) * v4 + x * v3;

They're both close to what I need but obviously not quite right.

like image 688
Frobot Avatar asked Jan 02 '12 04:01

Frobot


People also ask

How do you calculate interpolation?

Know the formula for the linear interpolation process. The formula is y = y1 + ((x - x1) / (x2 - x1)) * (y2 - y1), where x is the known value, y is the unknown value, x1 and y1 are the coordinates that are below the known x value, and x2 and y2 are the coordinates that are above the x value.

What is interpolation and example?

Interpolation is the process of estimating unknown values that fall between known values. In this example, a straight line passes through two points of known value. You can estimate the point of unknown value because it appears to be midway between the other two points.

How do you find the barycentric coordinates of a triangle?

To compute the position of this point using barycentric coordinates we use the following equation (1): P=uA+vB+wC. where A B and C are the vertices of a triangle and u, v, and w (the barycentric coordinates), three real numbers (scalars) such that u+v+w=1 (barycentric coordinates are normalized).


2 Answers

You should use barycentric coordinates. There is a very thorough write-up here that also discusses alternative solutions and why barycentric coordinates are best: CodePlea - Interpolating in a Triangle

Basically, the weights will end up looking like this:

enter image description here

like image 156
reneekk Avatar answered Sep 18 '22 19:09

reneekk


Actually the simplest and most robust solution is based on barycentric coordinates -

http://answers.unity3d.com/questions/383804/calculate-uv-coordinates-of-3d-point-on-plane-of-m.html

like image 31
titanae Avatar answered Sep 17 '22 19:09

titanae