Vérifier l'appartenance d'un point à un triangle

Version imprimable

02/07/2015, 14h43
ines ben alaya

Vérifier l'appartenance d'un point à un triangle

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.
02/07/2015, 14h53
Flodelarab

Bonjour :coucou:

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.
02/07/2015, 16h36
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
$Formule mathématique$
Par exemple, regarde les coordonnées barycentriques.

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

Citation:

Envoyé par Flodelarab

Bonjour :coucou:

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:

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

03/07/2015, 10h56
Flodelarab

Citation:

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 ?
03/07/2015, 11h26
DonQuiche

Citation:

Envoyé par Flodelarab

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...
07/07/2015, 19h32
souviron34

Citation:

Envoyé par DonQuiche

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" :D

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... :roll:
07/07/2015, 19h43
DonQuiche

Citation:

Envoyé par souviron34

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" :D

C'est l'usage d'un epsilon global qui est absurde : le epsilon à considérer est spécifique à chaque opération en fonction de la magnitude attendue du résultat.
07/07/2015, 22h38
souviron34

Citation:

Envoyé par DonQuiche

C'est l'usage d'un epsilon global qui est absurde : le epsilon à considérer est spécifique à chaque opération en fonction de la magnitude attendue du résultat.

ça dépend..

Tu peux par exemple dire que e-08 est ton epsilon global, si tes données sont à e-05..

Si tu fais un soft avec beaucoup de maths, ça va être très compliqué de faire un epsilon par opération, d'autant plus qu'en général tu vas vérifier seulement des différences (et pour bien faire il faudrait même que ce soit des différences relatives)

if ( abs(a-b) <= epsilon )

if ( (abs(a-b)/((a+b)/2)) <= epsilon )

Alors bien entendu ça dépend et des données et des problèmes.. J'ai cependant trouvé qu'en général e-08 est une bonne limite pratico-pratique... (y compris purement en usage "non relatif"), en particulier pour le genre de calcul comme ci-dessus.. Mais on peut bien entendu s'en passer..
07/07/2015, 23h47
DonQuiche

Citation:

Envoyé par souviron34

ça dépend..

Tu peux par exemple dire que e-08 est ton epsilon global, si tes données sont à e-05..

Reprends mon exemple : on y faisait un produit vectoriel entre deux vecteurs normalisés. Autrement dit on calcule un sinus. Or le sinus, lui, a une magnitude indépendante des distances de ton problème.

Imagine maintenant que ton programme doive se cantonner à des réels 32 bits, soit 6-7 décimales seulement (*). Si maintenant les distances max de ton problème sont de l'ordre du kilomètre alors tu dois avoir un epsilon de 1E-2 ou davantage. C'est clairement insuffisant pour ton sinus. Et des pb vont aussi se poser avec un carré, un exponentiel ou autre.

Bref, pas d'epsilon global, un epsilon se choisit en fonction de l'opération réalisée.

(*) Pour réduire la bande passante nécessaire ou parce que tu travailles sur GPU (même si certains supportent le 64 bits aujourd'hui, avec un coût important en performances)
08/07/2015, 04h57
souviron34

Citation:

Envoyé par DonQuiche

Reprends mon exemple : on y faisait un produit vectoriel entre deux vecteurs normalisés. Autrement dit on calcule un sinus. Or le sinus, lui, a une magnitude indépendante des distances de ton problème.

On peut donc lui appliquer un epsilon :P

Citation:

Envoyé par DonQuiche

Imagine maintenant que ton programme doive se cantonner à des réels 32 bits, soit 6-7 décimales seulement (*). Si maintenant les distances max de ton problème sont de l'ordre du kilomètre alors tu dois avoir un epsilon de 1E-2 ou davantage. C'est clairement insuffisant pour ton sinus. Et des pb vont aussi se poser avec un carré, un exponentiel ou autre.

* mais personne en calcul normal sur des 32 bits n'utilise des floats, mais des doubles, pour des calculs..

J'ai toujours fonctionné avec des 32 bits, et des distances entre 1 mètre et 40 000 kms.. Exprimées en mètres, ça ne pose aucun problème. Et si tu normalises, et que tu vas de 1 mètre à 40 000 000 mètres, en double précision ça ne pose strictement aucun problème non plus..

De plus, 1 cm quand tu as des données de 1 km c'est pas absurde... Mais tu t'en fous, parce que e-08 ça marche aussi (tu as 14 bits au minimum à ta disposition pour des floats, et plus de 28 pour des doubles, que ce soit pour l'exposant ou la mantisse) . Donc, que tu aies 1000000.2000000000 et 1000000.2000000004 tu pourras dire qu'ils sont égaux, et inversement 1000000.20000000 et 1000000.20000001 qu'ils sont différents.... Et si tu les exprimes en km, c'est kifkif.. Tout dépend des données initiales, mais pour les calculs ça change rien..

Même pour des carrés : quand tu calcules des distances, si tu veux tester si 2 distances sont égales, même en ayant juste pris le carré, sans la racine, ça marche aussi..(et surtout si tu prends le relatif, ça n'a plus aucune importance) .

Mais ce e-08 est empirique.. Je l'ai constaté juste comme étant stable : e-06 est trop gros, et e-10 est trop sensible justement aux aléas de calculs et de représentations et de troncature **.. C'est mon coté physicien.. :oops:

M'enfin, je ne vais pas refaire le topo sur les ordres de grandeur, les échelles, et les précisions, déjà donné plusieurs fois.. Ni m'engueuler avec toi là-dessus..

Je réitère cependant que c'est au contraire une bonne pratique de manière générale, surtout si c'est utilisé en relatif.. (comme ton sinus) :

if ( (abs(a-b)/(abs(a+b)/2)) <= epsilon )

** et d'initialisation : souvent 4.50 ne donnera pas 4.50000000000000000000 mais il y aura quelque chose vers e-09 ou e-10...