Comment déterminer si un point se trouve dans un triangle 2D ?

Question

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

Answer 1

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

Voici des informations de grande qualité dans ce sujet sur GameDev y compris les problèmes de performance.

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

Answer 2

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

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

Le point p est à l'intérieur du triangle si 0 <= s <= 1 y 0 <= t <= 1 y s + t <= 1 .

s , t y 1 - s - t sont appelés les coordonnées barycentriques du point p .

Answer 3

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. Utilisation de 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ù Area est l'aire (signée) du triangle :

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

Évaluez simplement s , t y 1-s-t . Le point p est à l'intérieur du triangle si et seulement si elles sont toutes positives.

EDIT : Notez que l'expression ci-dessus pour la surface suppose que la numérotation des nœuds du triangle est dans le sens inverse des aiguilles d'une montre. Si la numérotation est dans le sens des aiguilles d'une montre, cette expression retournera une aire négative (mais avec une magnitude correcte). Le test lui-même ( s>0 && t>0 && 1-s-t>0 ) ne dépend pas du sens de la numérotation, cependant, puisque les expressions ci-dessus qui sont multipliées par 1/(2*Area) changent également de signe si l'orientation du nœud du triangle change.

EDIT 2 : Pour une efficacité de calcul encore meilleure, voir coproc Le commentaire de l'auteur ci-dessous (qui fait remarquer que si l'orientation des nœuds du triangle (sens horaire ou antihoraire) est connue à l'avance, la division par 2*Area dans les expressions pour s y t peut être évitée). Voir aussi Perro Azul dans les commentaires sous le titre Andreas Brinck La réponse de la Commission.

Answer 4

J'ai écrit ce code avant une dernière tentative avec Google et de trouver cette page, alors j'ai pensé que je devais 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 Wikipedia, j'ai du mal à voir en quoi elle est plus efficace (je suppose qu'il existe 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 mots, l'idée est la suivante : Le point s est-il à gauche ou à droite des deux lignes AB et AC ? Si c'est vrai, il ne peut pas être à l'intérieur. Si c'est faux, il est au moins à l'intérieur des "cônes" qui satisfont à la condition. Maintenant, puisque 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. Si c'est le cas, s ne peut pas être à l'intérieur, sinon s doit être à l'intérieur.

Quelques mots-clés dans les calculs sont les demi-plans de lignes et le déterminant (produit en croix 2x2). Peut-être qu'une manière plus pédagogique est probablement de penser qu'un point est à l'intérieur s'il est du même côté (gauche ou droite) de chacune des lignes AB, BC et CA. La méthode ci-dessus semblait cependant mieux convenir à une certaine optimisation.

Answer 5

J'ai écrit un article complet sur le test du point dans le triangle. Il montre les méthodes barycentriques, paramétriques et basées sur le produit scalaire.

Il traite ensuite du problème de précision qui se pose lorsqu'un point se trouve exactement sur un bord (avec des exemples). Enfin, il expose une toute nouvelle méthode basée sur la distance point-bord.

http://totologic.blogspot.fr/2014/01/accurate-point-in-triangle-test.html

Profitez-en !