¿Cómo determinar si un punto está en un triángulo 2D?

¿Hay alguna manera fácil de determinar si un punto está dentro de un triángulo? Es 2D, no 3D.

En general, el algoritmo más simple (y bastante óptimo) es verificar en qué lado del semiplano creado por los bordes está el punto.

Aquí hay información de alta calidad sobre este tema en GameDev , incluidos los problemas de rendimiento.

Y aquí hay un código para comenzar:

float sign (fPoint p1, fPoint p2, fPoint p3) { return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y); } bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3) { bool b1, b2, b3; b1 = sign(pt, v1, v2) < 0.0f; b2 = sign(pt, v2, v3) < 0.0f; b3 = sign(pt, v3, v1) < 0.0f; return ((b1 == b2) && (b2 == b3)); } 

Resuelve el siguiente sistema de ecuaciones:

 p = p0 + (p1 - p0) * s + (p2 - p0) * t 

El punto p está dentro del triángulo si 0 <= s <= 1 y 0 <= t <= 1 y s + t <= 1 .

s , t y 1 - s - t se llaman coordenadas baricéntricas del punto p .

Estoy de acuerdo con Andreas Brinck , las coordenadas baricéntricas son muy convenientes para esta tarea. Tenga en cuenta que no hay necesidad de resolver un sistema de ecuaciones cada vez: simplemente evalúe la solución analítica. Usando la notación de Andreas , la solución es:

 s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py); t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py); 

donde Area es el área (firmada) del triángulo:

 Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y); 

Solo evalúa s , t y 1-st . El punto p está dentro del triángulo si y solo si son todos positivos.

EDITAR: Tenga en cuenta que la expresión anterior para el área asume que la numeración del nodo triangular es en sentido antihorario. Si la numeración es en el sentido de las agujas del reloj, esta expresión devolverá un área negativa (pero con la magnitud correcta). La prueba misma ( s>0 && t>0 && 1-st>0 ) no depende de la dirección de la numeración, sin embargo, dado que las expresiones anteriores que se multiplican por 1/(2*Area) también cambian de signo si la orientación del nodo triángulo cambia.

EDIT 2: Para una eficiencia computacional aún mejor, consulte el comentario de coproc a continuación (que señala que si la orientación de los nodos del triángulo (en sentido horario o antihorario) se conoce de antemano, la división por 2*Area en las expresiones para s y t se pueden evitar). Ver también el jsfiddle-código de Perro Azul en los comentarios bajo la respuesta de Andreas Brinck .

Escribí este código antes de un último bash con Google y encontré esta página, así que pensé en compartirla. Básicamente es una versión optimizada de la respuesta de Kisielewicz. También investigué el método Barycentric, pero a juzgar por el artículo de Wikipedia me cuesta mucho ver cómo es más eficiente (supongo que hay una equivalencia más profunda). De todos modos, este algoritmo tiene la ventaja de no usar división; un problema potencial es el comportamiento de la detección de bordes dependiendo de la orientación.

 bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c) { int as_x = sx-ax; int as_y = sy-ay; bool s_ab = (bx-ax)*as_y-(by-ay)*as_x > 0; if((cx-ax)*as_y-(cy-ay)*as_x > 0 == s_ab) return false; if((cx-bx)*(sy-by)-(cy-by)*(sx-bx) > 0 != s_ab) return false; return true; } 

En palabras, la idea es esta: ¿El punto está a la izquierda oa la derecha de las líneas AB y AC? Si es cierto, no puede estar adentro. Si es falso, al menos está dentro de los “conos” que satisfacen la condición. Ahora que sabemos que un punto dentro de un trigon (triángulo) debe estar en el mismo lado de AB que BC (y también CA), verificamos si difieren. Si lo hacen, s no puede estar dentro, de lo contrario s debe estar adentro.

Algunas palabras clave en los cálculos son semiplanos de línea y el determinante (producto cruzado 2×2). Tal vez una forma más pedagógica sea pensar que es un punto dentro si es del mismo lado (izquierda o derecha) de cada una de las líneas AB, BC y CA. Sin embargo, la forma anterior parecía encajar mejor con alguna optimización.

Versión C # del método baricéntrico publicado por andreasdr y Perro Azul. Tenga en cuenta que el cálculo del área se puede evitar si s y t tienen signos opuestos. Verifiqué el comportamiento correcto con una prueba de unidad bastante completa.

 public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2) { var s = p0.Y * p2.X - p0.X * p2.Y + (p2.Y - p0.Y) * pX + (p0.X - p2.X) * pY; var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * pX + (p1.X - p0.X) * pY; if ((s < 0) != (t < 0)) return false; var A = -p1.Y * p2.X + p0.Y * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y; if (A < 0.0) { s = -s; t = -t; A = -A; } return s > 0 && t > 0 && (s + t) <= A; } 

[ editar ]
aceptó la modificación sugerida por @Pierre; ver comentarios

Una forma simple es:

encuentre los vectores que conectan el punto con cada uno de los tres vértices del triángulo y sume los angularjs entre esos vectores. Si la sum de los angularjs es 2 * pi, entonces el punto está dentro del triángulo.

Dos buenos sitios que explican las alternativas son:

blackpawn y wolfram

Versión Java del método baricéntrico:

 class Triangle { Triangle(double x1, double y1, double x2, double y2, double x3, double y3) { this.x3 = x3; this.y3 = y3; y23 = y2 - y3; x32 = x3 - x2; y31 = y3 - y1; x13 = x1 - x3; det = y23 * x13 - x32 * y31; minD = Math.min(det, 0); maxD = Math.max(det, 0); } boolean contains(double x, double y) { double dx = x - x3; double dy = y - y3; double a = y23 * dx + x32 * dy; if (a < minD || a > maxD) return false; double b = y31 * dx + x13 * dy; if (b < minD || b > maxD) return false; double c = det - a - b; if (c < minD || c > maxD) return false; return true; } private final double x3, y3; private final double y23, x32, y31, x13; private final double det, minD, maxD; } 

El código anterior funcionará con precisión con enteros, suponiendo que no hay desbordamientos. También funcionará con triangularjs en sentido horario y antihorario. No funcionará con triangularjs colineales (pero puede verificarlo probando det == 0).

La versión baricéntrica es más rápida si va a probar diferentes puntos con el mismo triángulo.

La versión baricéntrica no es simétrica en los 3 puntos del triángulo, por lo que es probable que sea menos consistente que la versión de semiplano de borde de Kornel Kisielewicz, debido a los errores de redondeo en coma flotante.

Crédito: Hice el código anterior del artículo de Wikipedia sobre coordenadas baricéntricas.

Al usar la solución analítica para las coordenadas baricéntricas (señaladas por Andreas Brinck ) y:

  • no distribuyendo la multiplicación sobre los términos entre paréntesis
  • evitando calcular varias veces los mismos términos almacenándolos
  • reduciendo las comparaciones (según lo señalado por coproc y Thomas Eding )

uno puede minimizar el número de operaciones “costosas”:

 function ptInTriangle(p, p0, p1, p2) { var dX = px-p2.x; var dY = py-p2.y; var dX21 = p2.x-p1.x; var dY12 = p1.y-p2.y; var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y); var s = dY12*dX + dX21*dY; var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY; if (D<0) return s<=0 && t<=0 && s+t>=D; return s>=0 && t>=0 && s+t<=D; } 

(El código se puede pegar en Perro Azul jsfiddle )

Llevando a:

  • variable "recuerda": 30
  • almacenamiento variable: 7
  • adiciones: 4
  • sustracciones: 8
  • multiplicaciones: 6
  • divisiones: ninguna
  • comparaciones: 4

Esto se compara bastante bien con la solución de Kornel Kisielewicz (25 retiros, 1 almacenamiento, 15 sustracciones, 6 multiplicaciones, 5 comparaciones), y podría ser incluso mejor si se necesita la detección en sentido horario / antihorario (que requiere 6 retiros, 1 adición, 2 sustracciones , 2 multiplicaciones y 1 comparación en sí misma, utilizando el determinante de solución analítica, como lo señala rhgb ).

Lo que hago es precalcular las tres caras normales,

  • en 3D por producto cruzado del vector lateral y el vector normal de la cara.

  • en 2D simplemente intercambiando componentes y negando uno,

luego dentro / afuera para cualquier lado es cuando un producto de puntos del lado normal y el vértice para señalar el vector, cambiar el signo. Repita para otros dos (o más) lados.

Beneficios:

  • mucho es precalculado, tan bueno para múltiples puntos de prueba en el mismo triángulo.

  • rechazo temprano de casos comunes de más puntos externos que interiores. (también si la distribución de puntos está ponderada a un lado, puede probar ese lado primero).

Aquí hay una implementación eficiente de Python :

 def PointInsideTriangle2(pt,tri): '''checks if point pt(2) is inside triangle tri(3x2). @Developer''' a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \ tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1]) s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \ (tri[0,0]-tri[2,0])*pt[1]) if s<0: return False else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \ (tri[1,0]-tri[0,0])*pt[1]) return ((t>0) and (1-st>0)) 

y un resultado de ejemplo:

enter image description here

Si está buscando velocidad, aquí hay un procedimiento que podría ayudarlo.

Clasifica los vértices del triángulo en sus ordenadas. Esto lleva, en el peor de los casos, tres comparaciones. Deje que Y0, Y1, Y2 sean los tres valores ordenados. Al dibujar tres horizontales a través de ellos, se divide el plano en dos semiplanos y dos losas. Deje que Y sea la ordenada del punto de consulta.

 if Y < Y1 if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done else Y > Y0 -> the point lies in the upper slab else if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done else Y < Y2 -> the point lies in the lower slab 

Cuesta dos comparaciones más. Como puede ver, se logra un rechazo rápido para los puntos fuera de la “losa de delimitación”.

Opcionalmente, puede proporcionar una prueba en las abscisas para un rechazo rápido a la izquierda y a la derecha ( X <= X0' or X >= X2' ). Esto implementará una prueba rápida de cuadro delimitador al mismo tiempo, pero también tendrá que ordenar las abscisas.

Finalmente, tendrá que calcular el signo del punto dado con respecto a los dos lados del triángulo que delimitan la losa relevante (superior o inferior). La prueba tiene la forma:

 ((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk)) 

La discusión completa de las combinaciones i, j, k (hay seis, basadas en el resultado del género) está fuera del scope de esta respuesta y “se dejó como un ejercicio para el lector”; para la eficiencia, deberían estar codificados.

Si crees que esta solución es compleja, observa que principalmente implica comparaciones simples (algunas de las cuales se pueden calcular previamente), más 6 restas y 4 multiplicaciones en caso de que falle la prueba de recuadro delimitador. Este último costo es difícil de superar ya que en el peor de los casos no se puede evitar comparar el punto de prueba con dos lados (ningún método en otras respuestas tiene un costo menor, algunos lo empeoran, como 15 restas y 6 multiplicaciones, a veces divisiones).

ACTUALIZACIÓN: más rápido con una transformación de corte

Como se explicó anteriormente, puede ubicar rápidamente el punto dentro de una de las cuatro bandas horizontales delimitadas por las tres ordenadas de vértice, usando dos comparaciones.

Opcionalmente, puede realizar una o dos pruebas X adicionales para verificar el interior del cuadro delimitador (líneas punteadas).

Luego considere la transformación “cizalla” dada por X'= X - m Y, Y' = Y , donde m es la pendiente DX/DY para el borde más alto. Esta transformación hará que este lado del triángulo sea vertical. Y como sabes de qué lado del horizontal medio estás, basta con probar el signo con respecto a un solo lado del triángulo.

enter image description here

Suponiendo que haya calculado previamente la pendiente m , así como la X' para los vértices del triángulo esquilado y los coeficientes de las ecuaciones de los lados como X = m Y + p , necesitará en el peor de los casos

  • dos comparaciones ordenadas para la clasificación vertical;
  • opcionalmente una o dos comparaciones de abscisas para el rechazo de cuadro delimitador;
  • cálculo de X' = X - m Y ;
  • una o dos comparaciones con las abscisas del triángulo esquilado;
  • un signo prueba X >< m' Y + p' contra el lado correspondiente del triángulo esquilado.

Si conoce las coordenadas de los tres vértices y las coordenadas del punto específico, entonces puede obtener el área del triángulo completo. Después, calcule el área de los tres segmentos del triángulo (un punto es el punto dado y los otros dos son dos vértices del triángulo). Por lo tanto, obtendrás el área de los tres segmentos triangulares. Si la sum de estas áreas es igual al área total (que obtuviste previamente), entonces, el punto debe estar dentro del triángulo. De lo contrario, el punto no está dentro del triángulo. Esto debería funcionar. Si hay algún problema, házmelo saber. Gracias.

Otra función en python , más rápida que el método de Developer (al menos para mí) e inspirada en la solución de Cédric Dufour :

 def ptInTriang(p_test, p0, p1, p2): dX = p_test[0] - p0[0] dY = p_test[1] - p0[1] dX20 = p2[0] - p0[0] dY20 = p2[1] - p0[1] dX10 = p1[0] - p0[0] dY10 = p1[1] - p0[1] s_p = (dY20*dX) - (dX20*dY) t_p = (dX10*dY) - (dY10*dX) D = (dX10*dY20) - (dY10*dX20) if D > 0: return ( (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D ) else: return ( (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D ) 

Puedes probarlo con:

 X_size = 64 Y_size = 64 ax_x = np.arange(X_size).astype(np.float32) ax_y = np.arange(Y_size).astype(np.float32) coords=np.meshgrid(ax_x,ax_y) points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,)) p_test = np.array([0 , 0]) p0 = np.array([22 , 8]) p1 = np.array([12 , 55]) p2 = np.array([7 , 19]) fig = plt.figure(dpi=300) for i in range(0,X_size*Y_size): p_test[0] = points_unif[0][i] p_test[1] = points_unif[1][i] if ptInTriang(p_test, p0, p1, p2): plt.plot(p_test[0], p_test[1], '.g') else: plt.plot(p_test[0], p_test[1], '.r') 

Se necesita mucho para trazar, pero esa cuadrícula se prueba en 0.0195319652557 segundos contra 0.0844349861145 segundos del código del Desarrollador .

Finalmente el comentario del código:

 # Using barycentric coordintes, any point inside can be described as: # X = p0.x * r + p1.x * s + p2.x * t # Y = p0.y * r + p1.y * s + p2.y * t # with: # r + s + t = 1 and 0 < r,s,t < 1 # then: r = 1 - s - t # and then: # X = p0.x * (1 - s - t) + p1.x * s + p2.x * t # Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t # # X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t # Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t # # X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t # Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t # # we have to solve: # # [ X - p0.x ] = [(p1.x-p0.x) (p2.x-p0.x)] * [ s ] # [ Y - p0.Y ] [(p1.y-p0.y) (p2.y-p0.y)] [ t ] # # ---> b = A*x ; ---> x = A^-1 * b # # [ s ] = A^-1 * [ X - p0.x ] # [ t ] [ Y - p0.Y ] # # A^-1 = 1/D * adj(A) # # The adjugate of A: # # adj(A) = [(p2.y-p0.y) -(p2.x-p0.x)] # [-(p1.y-p0.y) (p1.x-p0.x)] # # The determinant of A: # # D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x) # # Then: # # s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) } # t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) } # # s = s_p / D # t = t_p / D # # Recovering r: # # r = 1 - (s_p + t_p)/D # # Since we only want to know if it is insidem not the barycentric coordinate: # # 0 < 1 - (s_p + t_p)/D < 1 # 0 < (s_p + t_p)/D < 1 # 0 < (s_p + t_p) < D # # The condition is: # if D > 0: # s_p > 0 and t_p > 0 and (s_p + t_p) < D # else: # s_p < 0 and t_p < 0 and (s_p + t_p) > D # # s_p = { dY20*dX - dX20*dY } # t_p = { dX10*dY - dY10*dX } # D = dX10*dY20 - dY10*dX20 

Hay condiciones de borde molestas donde un punto está exactamente en el borde común de dos triangularjs adyacentes. El punto no puede estar en ambos ni en ninguno de los triangularjs. Necesita una forma arbitraria pero consistente de asignar el punto. Por ejemplo, dibuja una línea horizontal a través del punto. Si la línea se cruza con el otro lado del triángulo a la derecha, el punto se trata como si estuviera dentro del triángulo. Si la intersección está a la izquierda, el punto está afuera.

Si la línea en la que se encuentra el punto es horizontal, use arriba / abajo.

Si el punto está en el vértice común de múltiples triangularjs, usa el triángulo con cuyo centro el punto forma el ángulo más pequeño.

Más divertido: tres puntos pueden estar en línea recta (cero grados), por ejemplo (0,0) – (0,10) – (0,5). En un algoritmo de triangulación, la “oreja” (0,10) debe ser cortada, el “triángulo” generado es la caja degenerada de una línea recta.

Solo quiero usar algunas matemáticas vectoriales simples para explicar la solución de coordenadas baricéntricas que Andreas había dado, será mucho más fácil de entender.

  1. El área A se define como cualquier vector dado por s * v02 + t * v01, con condición s> = 0 y t> = 0. Si algún punto dentro del triángulo v0, v1, v2, debe estar dentro del Área A.

enter image description here

  1. Si restringe más s, y t pertenece a [0, 1]. Obtenemos el Área B que contiene todos los vectores de s * v02 + t * v01, con la condición s, t pertenece a [0, 1]. Vale la pena notar que la parte baja del Área B es el espejo de Triangle v0, v1, v2. El problema viene si podemos dar cierta condición de s, y t, para excluir aún más la parte baja del Área B.

enter image description here

  1. Supongamos que damos un valor s, y t está cambiando en [0, 1]. En la siguiente imagen, el punto p está en el borde de v1v2. Todos los vectores de s * v02 + t * v01 que están a lo largo de la línea del tablero por simple sum de vectores. En v1v2 y punto de cruce de la línea de puntos p, tenemos:

(1-s) | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |

obtenemos 1 – s = tp, luego 1 = s + tp. Si cualquier t> tp, que 1 = s + t donde está en línea de trazo simple, el vector es dentro del triángulo

Entonces, si damos alguna s en [0, 1], la t correspondiente debe cumplir 1> = s + t, para el vector dentro del triángulo.

enter image description here

Así que finalmente obtenemos v = s * v02 + t * v01, v está dentro del triángulo con condición s, t, s + t pertenece a [0, 1]. Luego, traduzca al punto, tenemos

p – p0 = s * (p1 – p0) + t * (p2 – p0), con s, t, s + t en [0, 1]

que es lo mismo que la solución de Andreas para resolver el sistema de ecuaciones p = p0 + s * (p1 – p0) + t * (p2 – p0), con s, t, s + t pertenecen a [0, 1].

Aquí hay una solución en python que es eficiente, documentada y contiene tres pruebas unitarias. Es de calidad profesional y está listo para ser incluido en su proyecto en la forma de un módulo tal como está.

 import unittest ############################################################################### def point_in_triangle(point, triangle): """Returns True if the point is inside the triangle and returns False if it falls outside. - The argument *point* is a tuple with two elements containing the X,Y coordinates respectively. - The argument *triangle* is a tuple with three elements each element consisting of a tuple of X,Y coordinates. It works like this: Walk clockwise or counterclockwise around the triangle and project the point onto the segment we are crossing by using the dot product. Finally, check that the vector created is on the same side for each of the triangle's segments. """ # Unpack arguments x, y = point ax, ay = triangle[0] bx, by = triangle[1] cx, cy = triangle[2] # Segment A to B side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by) # Segment B to C side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy) # Segment C to A side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay) # All the signs must be positive or all negative return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0) ############################################################################### class TestPointInTriangle(unittest.TestCase): triangle = ((22 , 8), (12 , 55), (7 , 19)) def test_inside(self): point = (15, 20) self.assertTrue(point_in_triangle(point, self.triangle)) def test_outside(self): point = (1, 7) self.assertFalse(point_in_triangle(point, self.triangle)) def test_border_case(self): """If the point is exactly on one of the triangle's edges, we consider it is inside.""" point = (7, 19) self.assertTrue(point_in_triangle(point, self.triangle)) ############################################################################### if __name__ == "__main__": suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle) unittest.TextTestRunner().run(suite) 

Hay una prueba gráfica opcional adicional para el algoritmo anterior para confirmar su validez:

 import random from matplotlib import pyplot from triangle_test import point_in_triangle ############################################################################### # The area # size_x = 64 size_y = 64 # The triangle # triangle = ((22 , 8), (12 , 55), (7 , 19)) # Number of random points # count_points = 10000 # Prepare the figure # figure = pyplot.figure() axes = figure.add_subplot(111, aspect='equal') axes.set_title("Test the 'point_in_triangle' function") axes.set_xlim(0, size_x) axes.set_ylim(0, size_y) # Plot the triangle # from matplotlib.patches import Polygon axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none')) # Plot the points # for i in range(count_points): x = random.uniform(0, size_x) y = random.uniform(0, size_y) if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g') else: pyplot.plot(x, y, '.b') # Save it # figure.savefig("point_in_triangle.pdf") 

Produciendo el siguiente gráfico:

Pruebe la función point_in_triangle

Necesitaba un punto en la verificación de triángulo en un “entorno controlable” cuando estás absolutamente seguro de que los triangularjs serán en el sentido de las agujas del reloj. Entonces, tomé el jsfiddle de Perro Azul y lo modifiqué como lo sugirió coproc para tales casos; también eliminó multiplicaciones redundantes de 0.5 y 2 porque simplemente se cancelan entre sí.

http://jsfiddle.net/dog_funtom/H7D7g/

Aquí hay un código equivalente de C # para Unity:

 public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2) { var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * px + (p0.x - p2.x) * py); var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * px + (p1.x - p0.x) * py); if (s <= 0 || t <= 0) return false; var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y); return (s + t) < A; } 

Supuestamente código de alto rendimiento que he adaptado en JavaScript (artículo a continuación):

 function pointInTriangle (p, p0, p1, p2) { return (((p1.y - p0.y) * (px - p0.x) - (p1.x - p0.x) * (py - p0.y)) | ((p2.y - p1.y) * (px - p1.x) - (p2.x - p1.x) * (py - p1.y)) | ((p0.y - p2.y) * (px - p2.x) - (p0.x - p2.x) * (py - p2.y))) >= 0; } 

pointInTriangle (p, p0, p1, p2) – para triangularjs en sentido antihorario

pointInTriangle (p, p0, p1, p2) – para triangularjs en el sentido de las agujas del reloj

Mire en jsFiddle (prueba de rendimiento incluida), también hay una verificación por separado en una función separada http://jsfiddle.net/z7x0udf7/3/

Inspirado por esto: http://www.phatcode.net/articles.php?id=459

La forma más fácil y funciona con todos los tipos de triangularjs es simplemente determinar los angularjs de los angularjs de los puntos A, B, C del punto P. Si cualquiera de los angularjs es más grande que 180.0 grados, entonces está afuera, si 180.0 está en la circunferencia y si acos te está engañando y menos de 180.0 entonces está adentro. Echa un vistazo para entender http: // math-physics -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Honestamente, es tan simple como la respuesta de Simon P. Steven, pero con ese enfoque no tienes un control sólido sobre si deseas incluir o no los puntos en los bordes del triángulo.

Mi enfoque es un poco diferente pero muy básico. Considera el siguiente triángulo;

enter image description here

Para tener el punto en el triángulo tenemos que cumplir 3 condiciones

  1. El ángulo de ACE (verde) debe ser más pequeño que el ángulo de ACB (rojo)
  2. El ángulo del ECB (azul) debe ser menor que el ángulo del ACB (rojo)
  3. El punto E y el punto C deben tener el mismo signo cuando sus valores xey se aplican a la ecuación de | AB | línea.

En este método, usted tiene control total para incluir o excluir el punto en los bordes de forma individual. Entonces puede verificar si un punto está en el triángulo, incluyendo solo el | AC | borde, por ejemplo.

Entonces mi solución en JavaScript sería la siguiente;

 function isInTriangle(t,p){ function isInBorder(a,b,c,p){ var m = (ay - by) / (ax - bx); // calculate the slope return Math.sign(py - m*px + m*ax - ay) === Math.sign(cy - m*cx + m*ax - ay); } function findAngle(a,b,c){ // calculate the C angle from 3 points. var ca = Math.hypot(cx-ax, cy-ay), // ca edge length cb = Math.hypot(cx-bx, cy-by), // cb edge length ab = Math.hypot(ax-bx, ay-by); // ab edge length return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle } var pas = t.slice(1) .map(tp => findAngle(p,tp,t[0])), // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0]) ta = findAngle(t[1],t[2],t[0]); return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p); } var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}], point1 = {x:3, y:9}, point2 = {x:7, y:9}; console.log(isInTriangle(triangle,point1)); console.log(isInTriangle(triangle,point2)); 
 bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) { float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3); return (l1>0 && l2>0 && l3>0) || (l1<0 && l2<0 && l3<0); } 

¡No puede ser más eficiente que esto! Cada lado de un triángulo puede tener una posición y orientación independientes, por lo tanto, se necesitan tres cálculos: l1, l2 y l3 con 2 multiplicaciones cada uno. Una vez que se conocen l1, l2 y l3, el resultado es solo unas pocas comparaciones básicas y operaciones booleanas de distancia.

Este es el concepto más simple para determinar si un punto está dentro o fuera del triángulo o en un arm de un triángulo. La determinación de un punto está dentro de un tringle por determinantes

El código de trabajo más simple: `

 #-*- coding: utf-8 -*- import numpy as np tri_points = [(1,1),(2,3),(3,1)] def pisinTri(point,tri_points): Dx , Dy = point A,B,C = tri_points Ax, Ay = A Bx, By = B Cx, Cy = C M1 = np.array([ [Dx - Bx, Dy - By, 0], [Ax - Bx, Ay - By, 0], [1 , 1 , 1] ]) M2 = np.array([ [Dx - Ax, Dy - Ay, 0], [Cx - Ax, Cy - Ay, 0], [1 , 1 , 1] ]) M3 = np.array([ [Dx - Cx, Dy - Cy, 0], [Bx - Cx, By - Cy, 0], [1 , 1 , 1] ]) M1 = np.linalg.det(M1) M2 = np.linalg.det(M2) M3 = np.linalg.det(M3) print(M1,M2,M3) if(M1 == 0 or M2 == 0 or M3 ==0): print("Point: ",point," lies on the arms of Triangle") elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)): #if products is non 0 check if all of their sign is same print("Point: ",point," lies inside the Triangle") else: print("Point: ",point," lies outside the Triangle") print("Vertices of Triangle: ",tri_points) points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)] for c in points: pisinTri(c,tri_points) 

`

 bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){ /* inputs: e=point.x, f=point.y a=triangle.Ax, b=triangle.Bx, c=triangle.Cx g=triangle.Ay, h=triangle.By, i=triangle.Cy */ v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b)); w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b)); if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside else return false;//is outside return 0; } 

almost perfect Cartesian coordinates converted from barycentric are exported within *v (x) and *w (y) doubles. Both export doubles should have a * char before in every case, likely: *v and *w Code can be used for the other triangle of a quadrangle too. Hereby signed wrote only triangle abc from the clockwise abcd quad.

 A---B |..\\.o| |....\\.| D---C 

the o point is inside ABC triangle for testing with with second triangle call this function CDA direction, and results should be correct after *v=1-*v; and *w=1-*w; for the quadrangle

Since there’s no JS answer,
Clockwise & Counter-Clockwise solution:

 function triangleContains(ax, ay, bx, by, cx, cy, x, y) { let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) return det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 && det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 && det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 } 

EDIT: there was a typo for det computation ( cy - ay instead of cx - ax ), this is fixed.

https://jsfiddle.net/jniac/rctb3gfL/ enter image description here

I’m using here the same method as described above: a point is inside ABC if he is respectively on the “same” side of each line AB, BC, CA. triangle inclusion example