Determina se un punto si trova all'interno di un triangolo formato da 3 punti con data latitudine/longitudine

Question

Ho 3 punti (lat, lon) che formano un triangolo.Come posso trovare se un punto si trova all'interno di questo triangolo?

Answer 1

La domanda principale è se è possibile utilizzare un'approssimazione 2D per questo (in altre parole, il tuo triangolo è abbastanza piccolo).

Se è così, qualcosa di semplice come le coordinate baricentriche funzionerà bene.

Answer 2

La maggior parte delle lingue include una funzione per questo. In Java è Polygon.contains() http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html

Basta creare un poligono dai punti e quindi chiamare contiene() sul punto di test.

Answer 3

Provare l'algoritmo di trasmissione di raggi.

http://en.wikipedia.org/wiki/Point_in_polygon

E 'abbastanza semplice da implementare.

Answer 4

function SameSide(p1,p2, a,b) 
    cp1 = CrossProduct(b-a, p1-a) 
    cp2 = CrossProduct(b-a, p2-a) 
    if DotProduct(cp1, cp2) >= 0 then return true 
    else return false 

function PointInTriangle(p, a,b,c) 
    if SameSide(p,a, b,c) and SameSide(p,b, a,c) 
     and SameSide(p,c, a,b) then return true 
    else return false 

spiegato sul link qui sotto

http://www.blackpawn.com/texts/pointinpoly/default.html

Answer 5

È possibile usare il test point-poligono.

È semplice. Disegna una linea dal tuo punto a Est per una distanza abbastanza grande. Conta il numero di volte in cui la linea si interseca con il tuo plygon. Se è pari, il tuo punto è all'esterno, se è strano, è dentro.

Che funziona per qualsiasi tipo di poligono.

Answer 6

Oggi ho fatto qualcosa del genere! Anche con (lat, lon), in realtà (theta, phi), anche se sapevo qualcosa in più sulla mesh con cui stavo lavorando. Sto lavorando con (theta, phi) con 0 < = theta < = PI & = phi < = 2 * PI.

Troverete che potreste avere qualche problema se uno dei vertici si trova nella parte superiore o inferiore della vostra sfera, dal momento che nel mio caso phi non è realmente definito. Finisci con una singolarità lì. Hai fondamentalmente un quadrato, il che rende più facile controllare se il tuo punto si trova all'interno di esso o meno.

In tutti gli altri casi, se hai convertito il tuo punto in (lat, lon)/(theta, phi). Dovrebbe essere semplice usare il metodo come descritto da @Michelle Six.

Answer 7

Codice Java per solo triangolo, ovvero 3 punti.

public static boolean pntInTriangle(double px, double py, double x1, double y1, double x2, double y2, double x3, double y3) { 

    double o1 = getOrientationResult(x1, y1, x2, y2, px, py); 
    double o2 = getOrientationResult(x2, y2, x3, y3, px, py); 
    double o3 = getOrientationResult(x3, y3, x1, y1, px, py); 

    return (o1 == o2) && (o2 == o3); 
} 

private static int getOrientationResult(double x1, double y1, double x2, double y2, double px, double py) { 
    double orientation = ((x2 - x1) * (py - y1)) - ((px - x1) * (y2 - y1)); 
    if (orientation > 0) { 
     return 1; 
    } 
    else if (orientation < 0) { 
     return -1; 
    } 
    else { 
     return 0; 
    } 
} 

Answer 8

Ecco un'implementazione JavaScript del baricentrica coordinate soluzione discussed here:

// Returns true if point P inside the triangle with vertices at A, B and C 
// representing 2D vectors and points as [x,y]. Based on       
// http://www.blackpawn.com/texts/pointinpoly/default.html 
function pointInTriange(P, A, B, C) { 
    // Compute vectors   
    function vec(from, to) { return [to[0] - from[0], to[1] - from[1]]; } 
    var v0 = vec(A, C); 
    var v1 = vec(A, B); 
    var v2 = vec(A, P); 
    // Compute dot products 
    function dot(u, v) { return u[0] * v[0] + u[1] * v[1]; } 
    var dot00 = dot(v0, v0); 
    var dot01 = dot(v0, v1); 
    var dot02 = dot(v0, v2); 
    var dot11 = dot(v1, v1); 
    var dot12 = dot(v1, v2); 
    // Compute barycentric coordinates 
    var invDenom = 1.0/(dot00 * dot11 - dot01 * dot01); 
    var u = (dot11 * dot02 - dot01 * dot12) * invDenom; 
    var v = (dot00 * dot12 - dot01 * dot02) * invDenom; 
    // Check if point is in triangle 
    return (u >= 0) && (v >= 0) && (u + v < 1); 
} 

Si dice che sia più veloce rispetto alle soluzioni basate cross-product.