Determine si un punto está dentro de un triángulo formado por 3 puntos con una latitud/longitud dada

Question

Tengo 3 puntos (lat, lon) que forman un triángulo. ¿Cómo puedo encontrar un punto dentro de este triángulo?

Answer 1

La pregunta principal es si puede usar una aproximación 2D para esto (en otras palabras, si su triángulo es lo suficientemente pequeño).

Si es así, algo simple como coordenadas baricéntricas funcionará bien.

Answer 2

La mayoría de los lenguajes incluyen una función para esto. En Java es Polygon.contains() http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html

Simplemente crea un polígono a partir de tus puntos y luego llama a contains() en tu punto de prueba.

Answer 3

Pruebe el algoritmo de fundición de rayos.

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

Es bastante simple de implementar.

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 

explicados en el siguiente enlace

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

Answer 5

Se puede utilizar la prueba de punto polígono.

Es simple. Dibuja una línea desde tu punto hacia el este a una distancia lo suficientemente grande. Cuenta el número de veces que esa línea se cruza con tu plygon. Si es par, tu punto está afuera, si es impar, está adentro.

Eso funciona para cualquier tipo de polígono.

Answer 6

¡He hecho algo como esto hoy! También con (lat, lon), en realidad (theta, phi), aunque sabía un poco más acerca de la malla con la que estaba trabajando. Estoy trabajando con (theta, phi) con 0 < = theta < = PI & = phi < = 2 * PI.

Encontrará que puede tener algunos problemas si uno de los vértices está en la parte superior o inferior de su esfera, ya que en mi caso phi no está realmente definido. Terminas con una singularidad allí. Básicamente tienes un cuadrado, lo que hace que sea más fácil verificar si tu punto está dentro o no.

En todos los demás casos, si ha convertido su punto en (lat, lon)/(theta, phi). Debería ser simple usar el método descrito por @Michelle Six.

Answer 7

Código de Java para solo triángulo, es decir 3 puntos.

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

Aquí hay una aplicación de JavaScript de barycentric coordina solución 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); 
} 

Se dice que es más rápido que las soluciones basadas en productos cruzados.