Interpolación de un triángulo

Question

Tengo una unidad de triángulo rectángulo y un valor en cada uno de los 3 vértices. Necesito interpolar para encontrar el valor en un punto dentro del triángulo. Las horas de búsqueda no han revelado nada que realmente me diga cómo hacer esto. Aquí está mi intento más cercano, que es en realidad muy cerca, pero no del todo bien -

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

v1, v2 y v3 son los valores en los 3 vértices del triángulo. (x, y) es el punto en el triángulo que está tratando de encontrar el valor de.

Cualquier tipo de método me ayudaría aquí. No necesariamente tiene que ser un triángulo unidad/derecha.

Información actualizada: Tengo una grilla de puntos espaciados uniformemente y un valor en cada punto. Formo un triángulo con los 3 puntos más cercanos en la cuadrícula. Aquí está una imagen para ilustrarlo -
Así que tengo que interpolar entre 5, 3 y 7 para encontrar el valor de x. El punto también podría estar dentro del otro triángulo, lo que significa que se interpolaría entre 5, 7 y el valor de la esquina inferior izquierda del cuadrado.

En el código mostré, v1 = 5, v2 = 3, v3 = 7.
x es la distancia fraccional (rango [0-1]) en la dirección "x", y Y es la distancia fraccional en la dirección "y"
En el ejemplo de la imagen, x probablemente sería aproximadamente 0,75 e y sería de alrededor de 0,2

Aquí están mis intentos más cercanos -

creado usando -

 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; 

Y otro intento -

Creado mediante -

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

Ambos están cerca de lo que necesito, pero obviamente no del todo bien.

Answer 1

hice esta hace 3 años y todavía he estado trabajando en una manera de hacer esto. Sí creo que es imposible a menos que use un triángulo equilátero. Aquí hay una forma decente de hacerlo usando coordenadas baricéntricas y luego agregar una técnica que elimina la mayoría de los artefactos. v1, v2, v3 son los valores en los tres puntos del triángulo. x, y es el punto para el que desea encontrar un valor.

if (x > y) 
     { 
      b1 = -(x - 1); 
      b2 = (x - 1) - (y - 1); 
      b3 = 1 - b1 - b2; 
     } 
     else 
     { 
      b1 = -(y - 1); 
      b2 = -((x - 1) - (y - 1)); 
      b3 = 1 - b1 - b2; 
     } 

     float 
      abs = x - y; 
     if (abs < 0) abs *= -1; 
     if (abs < 0.25f) 
     { 
      abs = 0.25f - abs; 
      abs *= abs; 
      b1 -= abs; 
      b3 -= abs; 
     } 

     b1 *= b1; 
     b2 *= b2; 
     b3 *= b3; 
     float fd = 1/(b1 + b2 + b3); 
     b1 *= fd; 
     b2 *= fd; 
     b3 *= fd; 

     return 
       v1 * b1 + 
       v2 * b2 + 
       v3 * b3; 

Answer 2

Bien, entonces haremos una interpolación lineal, suponiendo que el gradiente sea constante con respecto a xy a y. d/dx = v2 - v1 y d/dy = v3 - v2, y f(0,0) = v1. Tenemos una ecuación diferencial bidimensional simple.

d{f(x,y)} = (v2 - v1)*dx 
f(x,y) = (v2 - v1)*x + g(y) 
d{f(x,y)} = g'(y) = (v3 - v2)*dy 
g(y) = (v3 - v2)*y + C 
f(x,y) = (v2 - v1)*x + (v3 - v2)*y + C 
f(0,0) = v1 = (v2 - v1)*0 + (v3 - v2)*0 + C = C 
f(x,y) = (v2 - v1)*x + (v3 - v2)*y + v1 

o en términos de v1 v2 y v3

f(x,y) = (1 - x)*v1 + (x - y)*v2 + y*v3 

Si desea hacerlo en un cuadrado de cuatro vértices, que el anterior con v4 en la parte inferior izquierda en x = 0 y = 1 , aquí son las condiciones: d/dx = (v2 - v1) (1 - y) + (v3 - v4) y, d/dy = (v3 - v2) x + (v4 - v1) (1 - x), f(0,0) = v1

d/dx = (v2 - v1) (1 - y) + (v3 - v4) y 
f(x,y) = (v2 - v1) (1 - y) x + (v3 - v4) y x + g(y) 
d/dy = (v3 - v2) x + (v4 - v1) (1 - x) = -(v2 - v1) x + (v3 - v4) x + g'(y) 
v3 - v2 + (v4 - v1)/x + v4 - v1 = -v2 + v1 + v3 - v4 + g'(y)/x 
(v4 - v1)/x + 2*(v4 - v1) = g'(y)/x 
g'(y) = (v4 - v1) + 2 x (v4 - v1) 
g(y) = (v4 - v1) (1 + 2 x) y + C 
f(x,y) = (v2 - v1) (1 - y) x + (v3 - v4) y x + (v4 - v1) (1 + 2 x) y + C 
f(0,0) = (v2 - v1) (1 - 0) 0 + (v3 - v4) 0 0 + (v4 - v1) (1 + 2 0) 0 + C = v1 
f(x,y) = (v2 - v1) (1 - y) x + (v3 - v4) y x + (v4 - v1) (1 + 2 x) y + v1 

Answer 3

aquí es un poco de pseudocódigo para la vecina más cercana:

if(dist(p, p1) <= dist(p, p2) && dist(p, p1) <= dist(p, p3)) 
    return val(p1) 
if(dist(p, p2) <= dist(p, p3) && dist(p, p2) <= dist(p, p1)) 
    return val(p2) 
if(dist(p, p3) <= dist(p, p1) && dist(p, p3) <= dist(p, p2)) 
    return val(p3) 

Creo que esto también genera un diagrama de Voronoi

Answer 4

En realidad, la solución más sencilla y robusta se basa en coordenadas baricéntricas -

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

Answer 5

que puedes usar coordenadas barycentric. Hay una muy cuidadosa escritura hasta aquí que también discute alternativas de solución y por qué coordenadas barycentric son mejores: CodePlea - Interpolating in a Triangle

Básicamente, los pesos terminará pareciéndose a esto: