algorithm - saber - ecuacion de la circunferencia

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

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

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-s-t>0))

y un ejemplo de salida:

Aquí hay una solución en Python que es eficiente, está documentada y contiene tres pruebas de unidad. Es de calidad profesional y está listo para ser incluido en su proyecto en forma de 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 adicional opcional 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:

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

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

Y aquí hay un código para empezar:

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) { float d1, d2, d3; bool has_neg, has_pos; d1 = sign(pt, v1, v2); d2 = sign(pt, v2, v3); d3 = sign(pt, v3, v1); has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0); has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0); return !(has_neg && has_pos); }

Escribí este código antes de un intento final con Google y encontré esta página, así que pensé en compartirlo. Es básicamente una versión optimizada de la respuesta de Kisielewicz. También busqué en el método Baricéntrico, 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 = s.x-a.x; int as_y = s.y-a.y; bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0; if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false; if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false; return true; }

En palabras, la idea es esta: ¿el punto está a la izquierda o a la derecha de ambas líneas AB y AC? Si es verdad, no puede estar dentro. 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 son diferentes. Si lo hacen, s no puede estar dentro, de lo contrario s debe estar dentro.

Algunas palabras clave en los cálculos son semiplanos de línea y el determinante (producto cruzado 2x2). Quizás una forma más pedagógica es probablemente pensar que se trata de un punto que está dentro, si está en el mismo lado (izquierda o derecha) de cada una de las líneas AB, BC y CA. Sin embargo, la forma anterior parecía un ajuste mejor para algunas optimizaciones.

Estoy de acuerdo con Andreas Brinck , las coordenadas baricéntricas son muy convenientes para esta tarea. Tenga en cuenta que no es necesario resolver un sistema de ecuaciones cada vez: solo 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 todos son positivos.

EDITAR: tenga en cuenta que la expresión anterior para el área supone que la numeración del nodo del triángulo es en sentido contrario a las agujas del reloj. 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). Sin embargo, la prueba en sí ( s>0 && t>0 && 1-st>0 ) no depende de la dirección de la numeración, ya 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, vea el comentario de coproc a continuación (lo que indica que si la orientación de los nodos de triángulos (en sentido horario o antihorario) se conoce de antemano, la división por 2*Area en las expresiones para s y t pueden ser evitados). Vea también el código jsfiddle de Perro Azul en los comentarios bajo la respuesta de Andreas Brinck .

Hay condiciones molestas en el borde donde un punto está exactamente en el borde común de dos triángulos adyacentes. El punto no puede estar en ambos, o ninguno de los triángulos. Necesita una forma arbitraria pero consistente de asignar el punto. Por ejemplo, dibuje 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á fuera.

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

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

Más diversión: tres puntos pueden estar en línea recta (cero grados), por ejemplo (0,0) - (0,10) - (0,5). En un algoritmo de triangulación, el "oído" (0,10) debe cortarse, el "triángulo" generado es el caso degenerado de una línea recta.

Honestamente, es tan simple como la respuesta de Simon P. Steven. Sin embargo, con ese enfoque no tiene un control sólido sobre si desea que se incluyan los puntos en los bordes del triángulo o no.

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

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

El ángulo de ACE (verde) debe ser más pequeño que el ángulo de ACB (rojo)
El ángulo del ECB (azul) debe ser más pequeño que el ángulo ACB (rojo)
El punto E y el punto C deben tener el mismo signo cuando sus valores x e y 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 individualmente. Por lo tanto, puede verificar si un punto está en el triángulo, incluyendo solo el | AC | borde por ejemplo.

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

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

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 cambiando componentes y negando uno,

luego adentro / afuera para cualquier lado es cuando un producto de punto del lado normal y el vértice al vector de punto, cambia de signo. Repita para otros dos (o más) lados.

Beneficios:

mucho está precalculado, por lo que es excelente para múltiples pruebas de puntos en el mismo triángulo.
Rechazo temprano de casos comunes de más puntos externos que internos. (También si la distribución de puntos ponderada a un lado, puede probar ese lado primero).

Mediante el uso de la solución analítica a las coordenadas baricéntricas (señalado por Andreas Brinck ) y:

No repartir la multiplicación sobre los términos entre paréntesis.
Evitando computar varias veces los mismos términos almacenándolos.
reduciendo las comparaciones (como lo señalan Coproc y Thomas Eding )

Uno puede minimizar el número de operaciones "costosas":

function ptInTriangle(p, p0, p1, p2) { var dX = p.x-p2.x; var dY = p.y-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.net/PerroAZUL/zdaY8/1 )

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 Kornel Kisielewicz (25 retiros, 1 almacenamiento, 15 substracciones, 6 multiplicaciones, 5 comparaciones), y podría ser incluso mejor si se necesita la detección en el sentido de las manecillas del reloj o en el sentido contrario a las agujas del reloj (lo que requiere 6 retiros, 1 adición, 2 substracciones , 2 multiplicaciones y 1 comparación en sí misma, utilizando el determinante de la solución analítica, como lo señala rhgb ).

Necesitaba un punto en la verificación de triángulos en "entorno controlable" cuando estás absolutamente seguro de que los triángulos serán en el sentido de las agujas del reloj. Entonces, tomé el jsfiddle de Perro Azul y lo modifiqué según lo sugerido por Coproc para tales casos; También se eliminaron las multiplicaciones redundantes de 0,5 y 2 porque simplemente se cancelan entre sí.

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

Aquí está el código C # equivalente 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) * p.x + (p0.x - p2.x) * p.y); var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y); 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; }

Otra función en python , más rápida que el método del desarrollador (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

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 denominan coordenadas baricéntricas del punto p .

Si conoce las coordenadas de los tres vértices y las coordenadas del punto específico, puede obtener el área del triángulo completo. Luego, calcule el área de los tres segmentos de triángulos (un punto es el punto dado y los otros dos son dos vértices cualquiera del triángulo). De este modo, obtendrás el área de los tres segmentos triangulares. Si la suma de estas áreas es igual al área total (que obtuviste anteriormente), 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ágamelo saber. Gracias.

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

Ordenar los vértices de triángulos en sus ordenadas. Esto toma en el peor de los casos tres comparaciones. Sean Y0, Y1, Y2 los tres valores ordenados. Al dibujar tres horizontales a través de ellos, se divide el plano en dos medios planos y dos losas. Sea Y 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 puntos fuera de la "losa delimitada".

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 caja delimitadora al mismo tiempo, pero también tendrá que ordenar las abscisas.

Eventualmente necesitará 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 de i, j, k (hay seis de ellas, basadas en el resultado del tipo) está fuera del alcance de esta respuesta y "queda como un ejercicio para el lector"; Para la eficiencia, deben ser codificados.

Si piensa que esta solución es compleja, observe que involucra principalmente comparaciones simples (algunas de las cuales pueden ser calculadas previamente), más 6 restas y 4 multiplicaciones en caso de que la prueba del cuadro delimitador falle. El último costo es difícil de superar ya que, en el peor de los casos, no 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 transformada 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 la integridad del cuadro delimitador (líneas de puntos).

Luego considere la transformada de "corte" 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 sabe de qué lado de la horizontal media está, basta con probar el signo con respecto a un solo lado del triángulo.

Suponiendo que calculó previamente la pendiente m , así como la X'' para los vértices de triángulos cortados y los coeficientes de las ecuaciones de los lados como X = m Y + p , necesitará en el peor de los casos

dos comparaciones de ordenadas para la clasificación vertical;
opcionalmente, una o dos comparaciones de abscisas para el rechazo de cajas de límites;
cálculo de X'' = X - m Y ;
una o dos comparaciones con las abscisas del triángulo cortado;
prueba de un signo X >< m'' Y + p'' contra el lado relevante del triángulo cortado.

Solo quiero usar un vector matemático simple para explicar la solución de coordenadas baricéntricas que Andreas había dado, será mucho más fácil de entender.

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

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 señalar que la parte baja del Área B es el espejo de Triangle v0, v1, v2. El problema viene a si podemos dar cierta condición de s, yt, para excluir aún más la parte baja del área B.

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 de guión por suma de vectores simples. En v1v2 y el punto de cruce de la línea de guión 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 la línea de doble guión, el vector está fuera del triángulo, cualquier t <= tp, que 1> = s + t donde está en una sola línea de guión, el vector es dentro del triangulo

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

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

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

que es la misma 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].

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

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

pointInTriangle (p, p0, p1, p2) - para triángulos en sentido antihorario

pointInTriangle (p, p0, p1, p2) - para triángulos en el sentido de las agujas del reloj

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

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

Una forma simple es:

encuentra los vectores que conectan el punto con cada uno de los tres vértices del triángulo y suma los ángulos entre esos vectores. Si la suma de los ángulos es 2 * pi, el punto está dentro del triángulo.

Dos buenos sitios que explican alternativas son:

blackpawn y blackpawn

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 unitaria 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) * p.X + (p0.X - p2.X) * p.Y; var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * p.X + (p1.X - p0.X) * p.Y; 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; return A < 0 ? (s <= 0 && s + t >= A) : (s >= 0 && s + t <= A); }

_{[ editar ]}
^{aceptada modificación sugerida por @Pierre;} ^{ver comentarios}

Versión de 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 haya desbordamientos. También funcionará con triángulos en sentido horario y antihorario. No funcionará con triángulos 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 del semiplano de Kornel Kisielewicz, debido a los errores de redondeo de punto flotante.

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

Como no hay respuesta de JS, la
solución de Clockwise y Counter-Clockwise:

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: hubo un error tipográfico para el cálculo de det (en cy - aylugar de cx - ax), esto es fijo.

https://jsfiddle.net/jniac/rctb3gfL/

Estoy usando aquí el mismo método descrito anteriormente: un punto está dentro de ABC si él está, respectivamente, en el "mismo" lado de cada línea AB, BC, CA.

Este es el concepto más simple para determinar si un punto está dentro o fuera del triángulo o en un brazo 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 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, tres cálculos: l1, l2 y l3 son definitivamente necesarios e involucran 2 multiplicaciones cada uno. Una vez que se conocen l1, l2 y l3, el resultado es solo algunas comparaciones básicas y operaciones booleanas de distancia.

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

Las coordenadas cartesianas casi perfectas convertidas desde baricéntricas se exportan entre * v (x) y * w (y) dobles. En ambos casos, los dobles de exportación deben tener un * carácter antes, en todos los casos, probablemente: los códigos v y * w también se pueden usar para el otro triángulo de un cuadrángulo. De esta manera, se firmó solo el triángulo abc del cuadrante de abcd en sentido horario.

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

el punto o está dentro del triángulo ABC para la prueba con el segundo triángulo, llame a esta función dirección CDA, y los resultados deben ser correctos después *v=1-*v;y *w=1-*w;para el cuadrángulo