Comment déterminer si un point est dans un triangle 2D? [fermé]

Existe-t-il un moyen facile de déterminer si un point se trouve à l'intérieur d'un triangle? C'est 2D, pas 3D.

En général, l'algorithme le plus simple (et tout à fait optimal) vérifie de quel côté du demi-plan créé par les bords se trouve le point.

Voici quelques informations de haute qualité dans cette rubrique sur GameDev , y compris les problèmes de performances.

Et voici un code pour vous aider à démarrer:

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

Résolvez le système d'équation suivant:

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

Le point pest à l'intérieur du triangle si 0 <= s <= 1et 0 <= t <= 1et s + t <= 1.

s, tet 1 - s - tsont appelées les coordonnées barycentriques du point p.

Je suis d'accord avec Andreas Brinck , les coordonnées barycentriques sont très pratiques pour cette tâche. Notez qu'il n'est pas nécessaire de résoudre un système d'équations à chaque fois: il suffit d'évaluer la solution analytique. En utilisant la notation d' Andreas , la solution est:

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

où Areaest la zone (signée) du triangle:

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

Évaluez simplement s, tet 1-s-t. Le point pest à l'intérieur du triangle si et seulement s'ils sont tous positifs.

EDIT: Notez que l'expression ci-dessus pour la zone suppose que la numérotation des nœuds triangulaires est dans le sens antihoraire. Si la numérotation est dans le sens horaire, cette expression renvoie une zone négative (mais avec une amplitude correcte). s>0 && t>0 && 1-s-t>0Cependant, le test lui-même ( ) ne dépend pas de la direction de la numérotation, car les expressions ci-dessus qui sont multipliées par 1/(2*Area)changent également de signe si l'orientation du nœud triangulaire change.

EDIT 2: Pour une efficacité de calcul encore meilleure, voir le commentaire de coproc ci-dessous (ce qui fait que si l'orientation des nœuds triangulaires (dans le sens horaire ou antihoraire) est connue à l'avance, la division par 2*Areadans les expressions pour set tpeut être évité). Voir aussi le code jsfiddle de Perro Azul dans les commentaires sous la réponse d' Andreas Brinck .

J'ai écrit ce code avant une dernière tentative avec Google et trouver cette page, alors j'ai pensé le partager. Il s'agit essentiellement d'une version optimisée de la réponse de Kisielewicz. J'ai également examiné la méthode barycentrique, mais à en juger par l'article de Wikipédia, j'ai du mal à voir comment elle est plus efficace (je suppose qu'il y a une équivalence plus profonde). Quoi qu'il en soit, cet algorithme a l'avantage de ne pas utiliser la division; un problème potentiel est le comportement de la détection des bords en fonction de l'orientation.

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 termes, l'idée est la suivante: le point s est-il à gauche ou à droite des lignes AB et AC? Si c'est vrai, ça ne peut pas être à l'intérieur. Si elle est fausse, c'est au moins à l'intérieur des "cônes" qui remplissent la condition. Maintenant que nous savons qu'un point à l'intérieur d'un trigone (triangle) doit être du même côté de AB que BC (et aussi CA), nous vérifions s'ils diffèrent. S'ils le font, il est impossible qu'ils soient à l'intérieur, sinon ils doivent être à l'intérieur.

Certains mots-clés dans les calculs sont les demi-plans de ligne et le déterminant (produit croisé 2x2). Peut-être qu'une manière plus pédagogique est probablement de le considérer comme un point se trouvant à l'intérieur même s'il est du même côté (gauche ou droite) pour chacune des lignes AB, BC et CA. Cependant, la méthode ci-dessus semblait mieux adaptée à une certaine optimisation.

Version C # de la méthode barycentrique publiée par andreasdr et Perro Azul. Notez que le calcul d'aire peut être évité si set tont des signes opposés. J'ai vérifié le comportement correct avec un test unitaire assez approfondi.

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

_{[ modifier ]}
^{accepté la modification suggérée par @Pierre; voir les commentaires}

Version Java de la méthode barycentrique:

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

Le code ci-dessus fonctionnera avec précision avec des entiers, en supposant qu'aucun débordement. Il fonctionnera également avec des triangles dans le sens horaire et antihoraire. Cela ne fonctionnera pas avec les triangles colinéaires (mais vous pouvez le vérifier en testant det == 0).

La version barycentrique est la plus rapide si vous allez tester différents points avec le même triangle.

La version barycentrique n'est pas symétrique dans les 3 points triangulaires, elle est donc probablement moins cohérente que la version demi-plan de bord de Kornel Kisielewicz, en raison d'erreurs d'arrondi à virgule flottante.

Crédit: J'ai créé le code ci-dessus à partir de l'article de Wikipedia sur les coordonnées barycentriques.

Un moyen simple consiste à:

trouver les vecteurs reliant le point à chacun des trois sommets du triangle et additionner les angles entre ces vecteurs. Si la somme des angles est de 2 * pi, le point se trouve à l'intérieur du triangle.

Deux bons sites qui expliquent les alternatives sont:

blackpawn et wolfram

En utilisant la solution analytique aux coordonnées barycentriques (signalées par Andreas Brinck ) et:

• ne pas distribuer la multiplication sur les termes entre parenthèses
• éviter de calculer plusieurs fois les mêmes termes en les stockant
• réduire les comparaisons (comme l'ont souligné Coproc et Thomas Eding )

On peut minimiser le nombre d'opérations "coûteuses":

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

Le code peut être collé dans Perro Azul jsfiddle ou l'essayer en cliquant sur "Exécuter l'extrait de code" ci-dessous

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>

Menant à:

• variable "rappels": 30
• stockage variable: 7
• ajouts: 4
• soustractions: 8
• multiplications: 6
• divisions: aucune
• comparaisons: 4

Cela se compare assez bien à la solution Kornel Kisielewicz (25 rappels, 1 stockage, 15 soustractions, 6 multiplications, 5 comparaisons), et pourrait être encore mieux si une détection dans le sens horaire / antihoraire est nécessaire (ce qui prend 6 rappels, 1 ajout, 2 soustractions , 2 multiplications et 1 comparaison en soi, en utilisant le déterminant de la solution analytique, comme le souligne rhgb ).

Ce que je fais, c'est précalculer les trois faces normales,

• en 3D par produit croisé du vecteur latéral et du vecteur normal de face.

• en 2D en échangeant simplement les composants et en les annulant,

puis à l'intérieur / à l'extérieur pour n'importe quel côté, c'est quand un produit scalaire du côté normal et du vecteur sommet à point change de signe. Répétez l'opération pour les deux autres côtés (ou plus).

Avantages:

• beaucoup est précalculé, donc idéal pour les tests en plusieurs points sur le même triangle.

• rejet précoce du cas commun de points plus extérieurs qu'intérieurs. (également si la distribution des points est pondérée d'un côté, vous pouvez tester ce côté en premier.)

Voici une implémentation Python efficace :

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))

et un exemple de sortie:

Si vous recherchez la vitesse, voici une procédure qui pourrait vous aider.

Trier les sommets triangulaires sur leurs ordonnées. Cela prend au pire trois comparaisons. Soit Y0, Y1, Y2 les trois valeurs triées. En dessinant trois horizontales à travers eux, vous divisez l'avion en deux demi-plans et deux dalles. Soit Y l'ordonnée du point de requête.

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

Coûte deux autres comparaisons. Comme vous le voyez, un rejet rapide est obtenu pour les points en dehors de la "dalle de délimitation".

En option, vous pouvez fournir un test sur les abscisses pour un rejet rapide à gauche et à droite (X <= X0' or X >= X2' ). Cela implémentera un test de boîte de délimitation rapide en même temps, mais vous devrez également trier les abscisses.

Finalement, vous devrez calculer le signe du point donné par rapport aux deux côtés du triangle qui délimitent la dalle pertinente (supérieure ou inférieure). Le test a la forme:

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

La discussion complète de i, j, k combinaisons (il y en a six, sur la base du résultat du genre) est hors de portée de cette réponse et «laissée comme exercice au lecteur»; pour plus d'efficacité, ils doivent être codés en dur.

Si vous pensez que cette solution est complexe, notez qu'elle implique principalement des comparaisons simples (dont certaines peuvent être précalculées), plus 6 soustractions et 4 multiplications en cas d'échec du test de la boîte englobante. Ce dernier coût est difficile à battre car dans le pire des cas, vous ne pouvez pas éviter de comparer le point de test avec deux côtés (aucune méthode dans les autres réponses n'a un coût inférieur, certains l'aggravent, comme 15 soustractions et 6 multiplications, parfois des divisions).

MISE À JOUR: Plus rapide avec une transformation de cisaillement

Comme expliqué ci-dessus, vous pouvez rapidement localiser le point à l'intérieur de l'une des quatre bandes horizontales délimitées par les trois ordonnées du sommet, en utilisant deux comparaisons.

Vous pouvez éventuellement effectuer un ou deux tests X supplémentaires pour vérifier l'insidicité de la zone de délimitation (lignes pointillées).

Considérons alors la transformée de "cisaillement" donnée par X'= X - m Y, Y' = Y, où mest la pente DX/DYdu bord le plus haut. Cette transformation rendra ce côté du triangle vertical. Et puisque vous savez de quel côté de l'horizontale moyenne vous vous trouvez, il suffit de tester le signe par rapport à un seul côté du triangle.

En supposant que vous ayez précalculé la pente m, ainsi que les X'sommets du triangle cisaillé et les coefficients des équations des côtés X = m Y + p, vous aurez besoin dans le pire des cas

• deux comparaisons ordonnées pour la classification verticale;
• éventuellement une ou deux comparaisons d'abscisses pour le rejet de la boîte englobante;
• calcul de X' = X - m Y;
• une ou deux comparaisons avec les abscisses du triangle cisaillé;
• un test de signe X >< m' Y + p'contre le côté pertinent du triangle cisaillé.

Si vous connaissez les coordonnées des trois sommets et les coordonnées du point spécifique, vous pouvez obtenir l'aire du triangle complet. Ensuite, calculez l'aire des trois segments du triangle (un point étant le point donné et les deux autres étant deux sommets quelconques du triangle). Ainsi, vous obtiendrez l'aire des trois segments triangulaires. Si la somme de ces zones est égale à la surface totale (que vous avez obtenue précédemment), alors le point doit être à l'intérieur du triangle. Sinon, le point n'est pas à l'intérieur du triangle. Cela devrait fonctionner. S'il y a des problèmes, faites-le moi savoir. Je vous remercie.

Autre fonction en python , plus rapide que la méthode du développeur (pour moi du moins) et inspirée de la solution 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  )

Vous pouvez le tester avec:

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')

Cela prend beaucoup de temps à tracer, mais cette grille est testée en 0,0195319652557 secondes contre 0,0844349861145 secondes du code du développeur .

Enfin le commentaire du code:

# 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

Puisqu'il n'y a pas de réponse JS, la solution
Clockwise & 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: il y avait une faute de frappe pour le calcul de det ( cy - ayau lieu de cx - ax), cela est fixe.

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>

J'utilise ici la même méthode que celle décrite ci-dessus: un point est à l'intérieur de ABC s'il est respectivement du "même" côté de chaque ligne AB, BC, CA.

Je veux juste utiliser des mathématiques vectorielles simples pour expliquer la solution de coordonnées barycentriques qu'Andreas avait donnée, elle sera beaucoup plus facile à comprendre.

1. La zone A est définie comme tout vecteur donné par s * v02 + t * v01, avec la condition s> = 0 et t> = 0. Si un point à l'intérieur du triangle v0, v1, v2, il doit être à l'intérieur de la zone A.

2. Si restreindre davantage s, et t appartient à [0, 1]. Nous obtenons la zone B qui contient tous les vecteurs de s * v02 + t * v01, avec la condition s, t appartient à [0, 1]. Il convient de noter que la partie basse de la zone B est le miroir du triangle v0, v1, v2. Le problème vient de si nous pouvons donner une certaine condition de s, et t, pour exclure davantage la partie basse de la zone B.

3. Supposons que nous donnons une valeur s, et t change dans [0, 1]. Dans l'image suivante, le point p est sur le bord de v1v2. Tous les vecteurs de s * v02 + t * v01 qui sont le long de la ligne de tiret par simple somme vectorielle. À v1v2 et au point de croisement de la ligne pointillée p, nous avons:

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

on obtient 1 - s = tp, puis 1 = s + tp. Si tout t> tp, dont 1 <s + t où est sur la double ligne de tiret, le vecteur est en dehors du triangle, tout t <= tp, qui 1> = s + t où est sur la ligne de tiret simple, le vecteur est à l'intérieur du triangle.

Alors si nous avons donné n'importe quel s dans [0, 1], le t correspondant doit rencontrer 1> = s + t, pour le vecteur à l'intérieur du triangle.

Donc, finalement, nous obtenons v = s * v02 + t * v01, v est à l'intérieur du triangle avec la condition s, t, s + t appartient à [0, 1]. Ensuite, traduisez au point, nous avons

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

qui est la même que la solution d'Andreas pour résoudre le système d'équation p = p0 + s * (p1 - p0) + t * (p2 - p0), avec s, t, s + t appartiennent à [0, 1].

Voici une solution en python qui est efficace, documentée et contient trois unittests. Il est de qualité professionnelle et prêt à être intégré dans votre projet sous la forme d'un module tel quel.

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)

Il existe un test graphique supplémentaire facultatif pour l'algorithme ci-dessus pour confirmer sa validité:

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")

Produire le graphique suivant:

Il existe des conditions de bord embêtantes où un point est exactement sur le bord commun de deux triangles adjacents. Le point ne peut pas être dans les deux ni dans aucun des triangles. Vous avez besoin d'une manière arbitraire mais cohérente d'attribuer le point. Par exemple, tracez une ligne horizontale passant par le point. Si la ligne coupe avec l'autre côté du triangle à droite, le point est traité comme s'il était à l'intérieur du triangle. Si l'intersection est à gauche, le point est à l'extérieur.

Si la ligne sur laquelle se trouve le point est horizontale, utilisez dessus / dessous.

Si le point se trouve sur le sommet commun de plusieurs triangles, utilisez le triangle dont le centre forme le point le plus petit.

Plus amusant: trois points peuvent être en ligne droite (zéro degré), par exemple (0,0) - (0,10) - (0,5). Dans un algorithme de triangulation, l'oreille (0,10) doit être coupée, le "triangle" généré étant le cas dégénéré d'une ligne droite.

Il s'agit du concept le plus simple pour déterminer si un point se trouve à l'intérieur ou à l'extérieur du triangle ou sur un bras d'un triangle.

La détermination d'un point est à l'intérieur d'un triangle par des déterminants:

Le code de travail le plus 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 manière la plus simple et qui fonctionne avec tous les types de triangles est simplement de déterminer les angles des angles des points P, A, B et C. Si l' un des angles sont plus grands que 180,0 degrés , alors il est à l' extérieur, si 180,0 alors il est sur la circonférence et si ACOS triche sur vous et moins de 180,0 alors il est inside.Take un regard pour comprendre http: //-math physique -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Honnêtement, c'est aussi simple que la réponse de Simon P Steven mais avec cette approche, vous n'avez pas un contrôle solide sur si vous voulez que les points sur les bords du triangle soient inclus ou non.

Mon approche est un peu différente mais très basique. Considérez le triangle suivant;

Pour avoir le point dans le triangle, nous devons satisfaire 3 conditions

1. L'angle ACE (vert) doit être inférieur à l'angle ACB (rouge)
2. L'angle ECB (bleu) doit être inférieur à l'angle ACB (rouge)
3. Le point E et le point C doivent avoir le même signe lorsque leurs valeurs x et y sont appliquées à l'équation de | AB | ligne.

Dans cette méthode, vous avez le contrôle total pour inclure ou exclure le point sur les bords individuellement. Vous pouvez donc vérifier si un point est dans le triangle comprenant uniquement le | AC | bord par exemple.

Donc ma solution en JavaScript serait la suivante;

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

Ça ne peut pas être plus efficace que ça! Chaque côté d'un triangle peut avoir une position et une orientation indépendantes, d'où trois calculs: l1, l2 et l3 sont définitivement nécessaires impliquant 2 multiplications chacun. Une fois l1, l2 et l3 connus, le résultat n'est qu'à quelques comparaisons de base et opérations booléennes.

Code supposément performant que j'ai adapté en JavaScript (article ci-dessous):

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) - pour les triangles antihoraires
• pointInTriangle(p, p0, p1, p2) - pour les triangles dans le sens horaire

Regardez dans jsFiddle (test de performance inclus), il y a aussi une vérification de l'enroulement dans une fonction séparée. Ou appuyez sur "Exécuter l'extrait de code" ci-dessous

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