Interpolazione di un triangolo

Question

Ho un triangolo a destra unitario e un valore su ciascuno dei 3 vertici. Ho bisogno di interpolare per trovare il valore in un punto all'interno del triangolo. Ore di ricerca non hanno rilevato nulla che in realtà mi dica come farlo. Ecco il mio tentativo più vicino, che è in realtà abbastanza vicino ma non abbastanza di destra -

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

v1, v2 e v3 sono i valori ai 3 vertici del triangolo. (x, y) è il punto nel triangolo che stai cercando di trovare il valore di.

Qualsiasi tipo di metodo potrebbe aiutarmi qui. Non deve necessariamente essere un'unità/triangolo rettangolo.

Informazioni aggiornate: Ho una griglia di punti equidistanti e un valore in ogni punto. Faccio un triangolo fuori dai 3 punti più vicini sulla griglia. Ecco un'immagine per illustrarlo -
Quindi devo interpolare tra 5, 3 e 7 per trovare il valore di x. Il punto potrebbe trovarsi anche all'interno dell'altro triangolo, il che significa che interpolate tra 5, 7 e il valore dell'angolo in basso a sinistra del quadrato.

Nel codice ho mostrato, v1 = 5, v2 = 3, v3 = 7.
x è la distanza frazionata (intervallo [0-1]) nella direzione "x", e y è la distanza frazionaria nella direzione "y".
Nell'esempio del quadro, x sarebbe probabilmente circa 0,75 e y sarebbero circa 0,2

Qui sono i miei vicini tentativi -

creata 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; 

E un altro tentativo -

Creato utilizzando -

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

Sono entrambi vicini a ciò di cui ho bisogno, ma ovviamente non del tutto a posto.

Answer 1

ho chiesto questo 3 anni fa e sono stati ancora lavorando su un modo per farlo. Credo che sia impossibile a meno che non si usi un triangolo equilatero. Ecco un modo decente di farlo usando le coordinate baricentriche e quindi aggiungendo una tecnica che elimina la maggior parte degli artefatti. v1, v2, v3 sono i valori nei tre punti del triangolo. x, y è il punto per cui si desidera trovare un valore.

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

Ok, quindi faremo un'interpolazione lineare, assumendo che il gradiente sia costante rispetto a x e a y. d/dx = v2 - v1 e d/dy = v3 - v2 e f(0,0) = v1. Abbiamo una semplice equazione differenziale bidimensionale.

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 in termini di v1 v2 e v3

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

Se si vuole fare in una piazza per i quattro vertici, come sopra, con v4 in basso a sinistra in x = 0 y = 1 , qui le condizioni: 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

Ecco alcuni pseudocodice per primi vicini:

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) 

Credo che questo genera anche un diagramma di Voronoi

Answer 4

In realtà la soluzione più semplice e robusto si basa su coordinate baricentriche -

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

Answer 5

si dovrebbe usare le coordinate baricentriche. C'è un molto approfondita write-up qui che discute anche soluzioni alternative e perché coordinate baricentriche sono i migliori: CodePlea - Interpolating in a Triangle

In sostanza, i pesi finirà per assomigliare a questo: