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

¿Hay una 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 de qué lado del semiplano creado por los bordes es el punto.

Aquí hay información de alta calidad en este tema en GameDev , incluidos 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)
{
    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);
}

Resuelve el siguiente sistema de ecuaciones:

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

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

s, ty 1 - s - tse denominan coordenadas barcéntricas del punto p.

Estoy de acuerdo con Andreas Brinck , las coordenadas barcé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 Areaestá el área (firmada) del triángulo:

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

Solo evalúa s , ty 1-s-t. El puntop 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 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). s>0 && t>0 && 1-s-t>0Sin embargo, la prueba en sí ( ) no depende de la dirección de la numeración, ya que las expresiones anteriores se multiplican por1/(2*Area) también cambian de signo si cambia la orientación del nodo triangular.

EDITAR 2: para una eficiencia computacional aún mejor, vea el comentario de coproc a continuación (que señala que si la orientación de los nodos triangulares (en sentido horario o antihorario) se conoce de antemano, la división por 2*Areaen las expresiones para sy tpuede ser evitado). Vea también el código jsfiddle del Perro Azul en los comentarios bajo la respuesta de Andreas Brinck .

Escribí este código antes de un intento final con Google y de encontrar esta página, así que pensé en compartirlo. Básicamente es una versión optimizada de la respuesta de Kisielewicz. También examiné el método barcéntrico, pero a juzgar por el artículo de Wikipedia, me resulta difícil 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: ¿está el punto s a la izquierda o a la derecha de ambas líneas AB y AC? Si es verdad, no puede estar adentro. Si es falso, es al menos dentro de los "conos" que satisfacen la condición. Ahora, como sabemos que un punto dentro de un trigón (triángulo) debe estar al mismo lado de AB que BC (y también CA), verificamos si difieren. Si lo hacen, s posiblemente no puede estar adentro, de lo contrario s debe estar adentro.

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 sea pensar en él como un punto dentro si está del mismo lado (izquierda o derecha) a cada una de las líneas AB, BC y CA. Sin embargo, la forma anterior parecía encajar mejor para cierta 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 puede ser evitado si sy ttienen signos opuestos. Verifiqué el comportamiento correcto con una prueba unitaria bastante exhaustiva.

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 ]}
^{acepta modificación sugerida por @Pierre; ver comentarios}

Versión Java del método barcé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 barcé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 triangulares, por lo que es probable que sea menos consistente que la versión de medio plano del borde de Kornel Kisielewicz, debido a errores de redondeo de coma flotante.

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

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, entonces el punto está dentro del triángulo.

Dos buenos sitios que explican alternativas son:

blackpawn y wolfram

Al usar la solución analítica a las coordenadas barcéntricas (señalado por Andreas Brinck ) y

• no distribuir la multiplicación sobre los términos entre paréntesis
• evitando calcular varias veces los mismos términos almacenándolos
• reducción de las comparaciones (como lo señalaron coproc y Thomas Eding )

Se 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 puede pegarse en Perro Azul jsfiddle o probarlo haciendo clic en "Ejecutar fragmento de código" a continuación

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    var sign = A < 0 ? -1 : 1;
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign;
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign;
    
    return s > 0 && t > 0 && (s + t) < 2 * A * sign;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

Llevando a:

• variable "retiradas": 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 restas, 6 multiplicaciones, 5 comparaciones), y podría ser aún mejor si se necesita la detección en sentido horario / antihorario (que requiere 6 retiros, 1 suma, 2 restas , 2 multiplicaciones y 1 comparación en sí misma, utilizando el determinante de la 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,

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

Beneficios:

• mucho se calcula previamente, por lo que es excelente para pruebas de puntos múltiples en el mismo triángulo.

• Rechazo temprano del caso común de más puntos externos que internos. (también si la distribución de puntos se pondera 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-s-t>0))

y un ejemplo de salida:

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

Ordena los vértices del triángulo en sus ordenadas. Esto lleva, 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, divide el plano en dos medios planos y dos losas. Deje Y ser 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 delimitadora".

Opcionalmente, puede proporcionar una prueba en las abscisas para el 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 deberá ordenar las abscisas.

Eventualmente, deberá 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 i, j, k combinaciones (hay seis de ellas, basadas en el resultado del género) está fuera del alcance de esta respuesta y "se dejó como ejercicio para el lector"; para mayor eficiencia, deben estar codificados.

Si cree que esta solución es compleja, observe que implica principalmente comparaciones simples (algunas de las cuales pueden calcularse previamente), más 6 restas y 4 multiplicaciones en caso de que falle la prueba del cuadro delimitador. 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 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értices, utilizando dos comparaciones.

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

Luego considere la transformación de "corte" dada por X'= X - m Y, Y' = Y, donde mes la pendiente DX/DYpara el borde más alto. Esta transformación hará que este lado del triángulo sea vertical. Y dado que sabe de qué lado del centro horizontal está, es suficiente probar el signo con respecto a un solo lado del triángulo.

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

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

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 del triángulo (un punto es el punto dado y los otros dos son dos vértices del triángulo). Por lo tanto, obtendrá el área de los tres segmentos triangulares. Si la suma de estas áreas es igual al área total (que obtuvo 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, avíseme. Gracias.

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

Como no hay una respuesta JS, la
solución en sentido horario y antihorario:

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 

}

EDITAR: hubo un error tipográfico para el cómputo det (en cy - aylugar de cx - ax), esto se corrigió.

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

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 

}






let width = 500, height = 500

// clockwise
let triangle1 = {

	A : { x: 10, y: -10 },
	C : { x: 20, y: 100 },
	B : { x: -90, y: 10 },
	
	color: '#f00',

}

// counter clockwise
let triangle2 = {

	A : { x: 20, y: -60 },
	B : { x: 90, y: 20 },
	C : { x: 20, y: 60 },

	color: '#00f',
	
}


let scale = 2
let mouse = { x: 0, y: 0 }






// DRAW >

let wrapper = document.querySelector('div.wrapper')

wrapper.onmousemove = ({ layerX:x, layerY:y }) => {
	
	x -= width / 2
	y -= height / 2
	x /= scale
	y /= scale
	
	mouse.x = x
	mouse.y = y
	
	drawInteractive()

}

function drawArrow(ctx, A, B) {

	let v = normalize(sub(B, A), 3)
	let I = center(A, B)
	
	let p
	
	p = add(I, rotate(v, 90), v)
	ctx.moveTo(p.x, p.y)
	ctx.lineTo(I.x, I .y)
	p = add(I, rotate(v, -90), v)
	ctx.lineTo(p.x, p.y)

}

function drawTriangle(ctx, { A, B, C, color }) {

	ctx.beginPath()
	ctx.moveTo(A.x, A.y)
	ctx.lineTo(B.x, B.y)
	ctx.lineTo(C.x, C.y)
	ctx.closePath()
	
	ctx.fillStyle = color + '6'
	ctx.strokeStyle = color
	ctx.fill()
	
	drawArrow(ctx, A, B)
	drawArrow(ctx, B, C)
	drawArrow(ctx, C, A)
	
	ctx.stroke()

}

function contains({ A, B, C }, P) {

	return triangleContains(A.x, A.y, B.x, B.y, C.x, C.y, P.x, P.y)

}

function resetCanvas(canvas) {

	canvas.width = width
	canvas.height = height
	
	let ctx = canvas.getContext('2d')

	ctx.resetTransform()
	ctx.clearRect(0, 0, width, height)
	ctx.setTransform(scale, 0, 0, scale, width/2, height/2)
	
}

function drawDots() {

	let canvas = document.querySelector('canvas#dots')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	let count = 1000

	for (let i = 0; i < count; i++) {

		let x = width * (Math.random() - .5)
		let y = width * (Math.random() - .5)
		
		ctx.beginPath()
		ctx.ellipse(x, y, 1, 1, 0, 0, 2 * Math.PI)
		
		if (contains(triangle1, { x, y })) {
		
			ctx.fillStyle = '#f00'
		
		} else if (contains(triangle2, { x, y })) {
		
			ctx.fillStyle = '#00f'
		
		} else {
		
			ctx.fillStyle = '#0003'
		
		}

		
		ctx.fill()
		
	}
	
}

function drawInteractive() {

	let canvas = document.querySelector('canvas#interactive')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	ctx.beginPath()
	ctx.moveTo(0, -height/2)
	ctx.lineTo(0, height/2)
	ctx.moveTo(-width/2, 0)
	ctx.lineTo(width/2, 0)
	ctx.strokeStyle = '#0003'
	ctx.stroke()
	
	drawTriangle(ctx, triangle1)
	drawTriangle(ctx, triangle2)
	
	ctx.beginPath()
	ctx.ellipse(mouse.x, mouse.y, 4, 4, 0, 0, 2 * Math.PI)
	
	if (contains(triangle1, mouse)) {
	
		ctx.fillStyle = triangle1.color + 'a'
		ctx.fill()
		
	} else if (contains(triangle2, mouse)) {
	
		ctx.fillStyle = triangle2.color + 'a'
		ctx.fill()
		
	} else {
	
		ctx.strokeStyle = 'black'
		ctx.stroke()
		
	}
	
}

drawDots()
drawInteractive()










// trigo

function add(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	return { x, y }

}

function center(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	x /= points.length
	y /= points.length
	
	return { x, y }

}

function sub(A, B) {

	let x = A.x - B.x
	let y = A.y - B.y
	
	return { x, y }

}

function normalize({ x, y }, length = 10) {

	let r = length / Math.sqrt(x * x + y * y)
	
	x *= r
	y *= r
	
	return { x, y }

}

function rotate({ x, y }, angle = 90) {

	let length = Math.sqrt(x * x + y * y)
	
	angle *= Math.PI / 180
	angle += Math.atan2(y, x)
	
	x = length * Math.cos(angle)
	y = length * Math.sin(angle)
	
	return { x, y }

}

* {
	margin: 0;
}

html {
	font-family: monospace;
}

body {
	padding: 32px;
}

span.red {
	color: #f00;
}

span.blue {
	color: #00f;
}

canvas {
	position: absolute;
	border: solid 1px #ddd;
}

<p><span class="red">red triangle</span> is clockwise</p>
<p><span class="blue">blue triangle</span> is couter clockwise</p>
<br>
<div class="wrapper">
	<canvas id="dots"></canvas>
	<canvas id="interactive"></canvas>
</div>

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

Solo quiero usar algunas matemáticas vectoriales simples para explicar la solución de coordenadas barcéntricas que Andreas ha 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 la condición s> = 0 yt> = 0. Si algún punto dentro del triángulo v0, v1, v2, debe estar dentro del Área A.

2. Si restringe aún más s, yt 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 del Triángulo v0, v1, v2. El problema surge si podemos dar cierta condición de s, y t, para excluir aún más la parte baja del Área B.

3. 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 trazos por suma vectorial simple. En v1v2 y punto de cruce de 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 la línea de un solo guión, el vector es dentro del triangulo.

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

Entonces, 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 traduce 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 forma de módulo tal cual.

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:

Hay condiciones de borde molestas donde un punto está exactamente en el borde común de dos triángulos adyacentes. El punto no puede estar en ambos, ni en 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á 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 varios triángulos, use 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, el "oído" (0,10) debe ser cortado, el "triángulo" generado es el caso degenerado de una línea recta.

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 triángulo 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)

La forma más fácil y funciona con todo tipo de triángulos es simplemente determinar los ángulos de los ángulos de los puntos P, A, B y C. Si alguno de los ángulos es mayor que 180.0 grados, entonces está afuera, si 180.0 está en la circunferencia y si te está engañando y menos de 180.0, entonces está adentro. http: // math-physics -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

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

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

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

1. El ángulo ACE (verde) debe ser menor que el ángulo ACB (rojo)
2. El ángulo BCE (azul) debe ser menor que el ángulo ACB (rojo)
3. 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, 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.

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

function isInTriangle(t,p){

  function isInBorder(a,b,c,p){
    var m = (a.y - b.y) / (a.x - b.x);                     // calculate the slope
    return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y);
  }
  
  function findAngle(a,b,c){                               // calculate the C angle from 3 points.
    var ca = Math.hypot(c.x-a.x, c.y-a.y),                 // ca edge length
        cb = Math.hypot(c.x-b.x, c.y-b.y),                 // cb edge length
        ab = Math.hypot(a.x-b.x, a.y-b.y);                 // 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, 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 unas pocas comparaciones básicas y operaciones booleanas de distancia.

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 sentido horario

Mire en jsFiddle (prueba de rendimiento incluida), también hay comprobación de bobinado en una función separada. O presione "Ejecutar fragmento de código" a continuación

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

document.querySelector('#performance').addEventListener('click', _testPerformance);

test();

function test() {
    var result = checkClockwise(triangle.a, triangle.b, triangle.c) ? pointInTriangle(point, triangle.a, triangle.c, triangle.b) : pointInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function _testPerformance () {
	var px = [], py = [], p0x = [], p0y = [], p1x = [], p1y = [], p2x = [], p2y = [], p = [], p0 = [], p1 = [], p2 = [];
    
	for(var i = 0; i < 1000000; i++) {
    p[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p0[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p1[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p2[i] = {x: Math.random() * 100, y: Math.random() * 100};
  }
  console.time('optimal: pointInTriangle');
  for(var i = 0; i < 1000000; i++) {
    pointInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('optimal: pointInTriangle');

  console.time('original: ptInTriangle');
  for(var i = 0; i < 1000000; i++) {
  	ptInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('original: ptInTriangle');
}

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

function ptInTriangle(p, p0, p1, 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;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}