Discussion :

[ines ben alaya]

Bonjour,
Merci de bien vouloir m'aider à résoudre le problème suivant,
Comment je peux déterminer si un point est à l'intérieur d'un triangle sachant que les trois points du triangle sont connus (x,y,z) et aussi les coordonnées du point.
je travaille en 3D.
Merci d'avance.

[Flodelarab]

Bonjour

Déjà, il doit être dans le plan des trois points. Donc après avoir défini le vecteur normal par un produit vectoriel, l'équation du plan tombe tout cuit.

[dourouc05]

Ensuite, pour l'appartenance au triangle lui-même, le point doit être une combinaison convexe des trois points du triangle, c'est-à-dire qu'il peut s'écrire sous la forme

Par exemple, regarde les coordonnées barycentriques.

Rien en dehors de la portée d'une recherche Google pas trop évoluée.

[DonQuiche]

Bonjour

Déjà, il doit être dans le plan des trois points. Donc après avoir défini le vecteur normal par un produit vectoriel, l'équation du plan tombe tout cuit.

Malheureusement le calcul de la normale pose des problèmes de stabilité numérique.

Dans mes souvenirs il vaut vérifier que (A, M) sont du même côté par rapport (BC), que (B, M) sont du même côté par rapport (AC), etc.

J'ai un bout de code qui traîne qui fait ça :

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    public static bool IsInTriangle(this Vector3 v, Vector3 A, Vector3 B, Vector3 C)
    {
        return
            ArePQOnSameSideInRespectToAB(v, A, B, C) &&
            ArePQOnSameSideInRespectToAB(v, B, A, C) &&
            ArePQOnSameSideInRespectToAB(v, C, A, B);
    }
 
    static bool ArePQOnSameSideInRespectToAB(Vector3 P, Vector3 Q, Vector3 A, Vector3 B)
    {
        var AB = B - A;
        var AP = P - A;
        var AQ = Q - A;
 
        AB.Normalize();
        AP.Normalize();
        AQ.Normalize();
 
        var cross1 = Vector3.Cross(AB, AP);
        if (cross1.IsEpsilon()) return false; // Si P est placé sur AB, on considère que les deux points ne sont pas du même côté
 
        var cross2 = Vector3.Cross(AB, AQ);
        if (cross2.IsEpsilon()) return false; // Si Q est placé sur AB, on considère que les deux points ne sont pas du même côté
 
        return Vector3.Dot(cross1, cross2) > 0;
    }

[Flodelarab]

Malheureusement le calcul de la normale pose des problèmes de stabilité numérique.

Je ne comprends pas. Est-ce que tu veux dire que la précision des facteurs obtenus ne sera pas assez grande ?

[DonQuiche]

Je ne comprends pas. Est-ce que tu veux dire que la précision des facteurs obtenus ne sera pas assez grande ?

Oui. Dans le cas d'un triangle très allongé.

Cela dit à la relecture j'ai des doutes. Le IsEpsilon sent la mauvaise pratique, et les deux tests associés sont probablement nécessaires mais j'ai un doute. Ça marchait pour le domaine considéré mais bon...

[souviron34]

Le IsEpsilon sent la mauvaise pratique

Au contraire....

Les opérations numériques sur des flottants et les comparaisons qui en découlent ne sont pas exactes dans la mesure où (à part le remplissage systématique par des 0 quand on passe un calcul, ce qui n'est pas fait par défaut) dire "a = b" en flottant n'a pas vraiment de sens...

Il faut prendre en compte la précision des données, et non pas celle des calculs..

Donc il est au contraire de bonne pratique d'utiliser des choses comme "isepsilon"



PS : et c'est une erreur commune de jeune de penser qu'on peut programmer "if ( a == b )" avec des réels... Je l'ai encore vu il y a peu dans un code que j'avais écris et qu'un jeune stagiaire a révisé... Evidemment le code ne faisait plus ce qu'il devait faire...