Version imprimable
Bonjour
Je suis face a un exercice de programmation qui me donne quelques soucis, voici l'enoncé:
Soit un triangle defini par trois points A(x...,y...) B(x...;y....) C(x....,Y.....)
Ecrire le code qui verifie si oui ou non un quatrieme point D(x...,y....) se trouve a l'interieur de ce triangle.
Si vous avez des suggestions :idea: :?:
A bientot
Rémi :)
C'est assez simple, mais il s'agit d'un pb de mathématique.. Voila la solution:
Avec les trois points, tu calcules les équations de tes trois droites. Une fois que tu a les équations, voila l'algorithme:
Pour chaque droite, tu vérifies que le point D appartient au même demi plan que celui contenant le troisième point de ton triangle.
Avec un exmple:
tu consideres les points A et B, tu as l'auqtion de la droite (AB)., Si D appartient au même demi plan que C (demi plan definis par rapport à la droite AB), tu as verifies une des trois conditions.
Ensuites, tu consideres les points A et C, tu calcules l'equation de la droite (AC), si D appartient au même demi plan que B, tu as deux confditions sur trois
Ensuite tu consideres les points B et C. Si D appartient au même demi plan que A, c'est gagné...
Par contre, si une des trois conditions n'est pas remplies, ton point n'est pas dans le triangle.
Ton programme se code tres vite, si tu veux jouer le beau gosse ecrit un programme qui calcule ce genre de chose pour un polygone à n cotes, c'est plus marrant!
N'hesites pas si tu as des questions. Bon courage. Bye
Des pistes dans un triangle ABC où on veut savoir si M est à l'intérieur du triangle:
Avec les coordonées barycentriques
On détermine les coordonnées barycentriques de M par rapport à A, B, C
un point est à l'intérieur d'un triangle ABC si et seulement si ses coordonnées barycentriques sont toutes les trois positivers
Avec des demi-plans
La droite (AB) d'équation ax + by + c = 0 partage le plan en deux régions. Dans l'une les coordoonées des points vérifient ax + by + c < 0, dans l'autre ax + by + c > 0.
Pour savoir si les points C et M sont dans le même demi-plan, il suffit de tester si la formule ax + by + c appliquée à leurs coordonnées donne le même signe.
Enfin, le triangle ABC est défini comme l'intersection des trois demi-plans:
- le demi-plan de bord (AB) contenant C
- le demi-plan de bord (AC) contenant B
- le demi-plan de bord (BC) contenant A
Avec des produits vectoriels
M est dans le triangle si et seulement si les trois conditions suivantes sont vérifiées:
(vect(AB) ^ vect(AM)) . (vect(AM) ^ vect(AC)) >= 0
(vect(BA) ^ vect(BM)) . (vect(BM) ^ vect(BC)) >= 0
(vect(CA) ^ vect(CM)) . (vect(CM) ^ vect(CB)) >= 0
où ^ désigne le produit vectoriel de deux vecteurs
. désigne le produit scalaire
A mon avis, cete méthode devrait être efficace. il suffit de te procurer un bon formulaire.
P.S. Pourrais-tu éditer ton premier message et mettre un titre plus explicite (c'est plus facile à lire pour les habitués du forum) du style "point intérieur à un triangle ?"
Il me semble aussi que tu peux faire en calculant les angles:
si la somme des trois angles ADC, CDB, BDA est égale à 360 degrés, alors le point D est à l'intérieur du triangle (il faut tenir compte de l'orientation)
La réponse pratique en Delphi ici (et sur le Net en C à l'adresse donnée par Maamar au post sur les algos géométriques) :
http://www.geometryalgorithms.com/
Facile, non ? Et adaptable ...Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
W00t, déterrage puissance 6 années, qui dit mieux ?
Bon, le code ci dessus m'a bien aidé, sauf qu'il est faux, donc je corrige !
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Peut-on faire la même chose en 3D?
La formule que Scorpi0 a donnée est elle toujours valable?
Hello,
Est-ce qu'on peut utiliser le déterminant pour calculer l'aire du triangle (on va dire ABC), et ensuite calculer l'aire des trois triangles formés par A,B,C et le quatrieme point D dont on veut savoir si il est à l'intérieur ou non?
et si Aire(ADC)+Aire(ADB)+Aire(CDB)=Aire(ABC) alors D est à l'interieur de ABC?
avec, Aire()=det()/2.
On peut utiliser cette méthode en 3D pour un point dans un tétraèdre.
Bonjour,
Il y a un article de blog qui explique deux méthodes de détermination d'un point à un triangle, et propose une application en C++.
C'est très intéressant.
le calcul de la position d'un point par rapport à un triangle peut se faire par calcul de déterminant de trois triangles virtuels
soit ABC les sommets du triangle dans l'ordre contraire aux aiguilles d'une montre (ordre topographique) et M le 4eme point . On à 3 triangles virtuels ABM , AMC, MBC soit D le déterminant calculé avec les sommets ABC
| xa ya 1 |
D= | xb yb 1 |
| xc yc 1 |
on calcul le signe des trois déterminants des triangles virtuels on a 3 possibilités
1 - les trois déterminants sont tous positifs ==> le point M appartient au triangle ABC
2 - un déterminant est nul ==> le point M appartient à un côté du triangle (si deux déterminants nuls ==> M confondu avec sommet )
3 - un déterminant est négatif ==> M est à droite du cote du triangle
le problème sérieux qui se pose dans certaines situations est le calcul exact de D (ou la détermination de son signe ) à cause des flottants (un calcul avec des nombres entiers ne pose pas de difficultés particulières)