Point à l'intérieur triangle

par **mertosl** » 18 Juin 2015, 00:45

Bonjour à tous,
Je suis entrain de développer une petit fonction en python qui me permet de savoir si un point random (sur les intervals [xmin;xmax], [ymin;ymax]) se trouve à l'intérieur d'une figure quelconque dans un repère 2D.
Pour simplifier ce programme, je me base sur des triangles.
Si le point appartient à un triangle de la figure, je le considère comme valide.
Le problème est que je ne suis pas opérationnel en mathématiques.
J'ai un triangle quelconque ABC avec A[Xa;Ya], B[Xb;Yb] et C[Xc;Yc]. Je veut savoir si M[Xm;Ym] se trouve à l'intérieur de ABC.
Si la somme des angles AMB, BMC et CMA est égale à 360°, M appartient à ABC.
Comment je calcule les angles:
AM=sqrt((Xm-Xa)^2 + (Ym-Ya)^2)
MB=sqrt((Xb-Xm)^2 + (Yb-Ym)^2)
BA=sqrt((Xa-Xb)^2 + (Ya-Yb)^2)
AMB = arccos((AM^2 + MB^2 - BA^2) / (2 * AM * MB)) * 180/Pi
Et la même méthode pour BMC et CMA.

Est-ce une bonne façon de savoir si un point se trouve à l'intérieur d'une figure quelconque?
Merci d'avance.

PS: Il me semble que si la figure est de la forme d'un C et que le point est dans le creux du C, et que le triangle traverse la figure par dessus le creux, la méthode ne fonctionne surement pas.

par **Pseuda** » 18 Juin 2015, 07:33

mertosl a écrit:Bonjour à tous,
Je suis entrain de développer une petit fonction en python qui me permet de savoir si un point random (sur les intervals [xmin;xmax], [ymin;ymax]) se trouve à l'intérieur d'une figure quelconque dans un repère 2D.
Pour simplifier ce programme, je me base sur des triangles.
Si le point appartient à un triangle de la figure, je le considère comme valide.
Le problème est que je ne suis pas opérationnel en mathématiques.
J'ai un triangle quelconque ABC avec A[Xa;Ya], B[Xb;Yb] et C[Xc;Yc]. Je veut savoir si M[Xm;Ym] se trouve à l'intérieur de ABC.
Si la somme des angles AMB, BMC et CMA est égale à 360°, M appartient à ABC.
Comment je calcule les angles:
AM=sqrt((Xm-Xa)^2 + (Ym-Ya)^2)
MB=sqrt((Xb-Xm)^2 + (Yb-Ym)^2)
BA=sqrt((Xa-Xb)^2 + (Ya-Yb)^2)
AMB = arccos((AM^2 + MB^2 - BA^2) / (2 * AM * MB)) * 180/Pi
Et la même méthode pour BMC et CMA.

Est-ce une bonne façon de savoir si un point se trouve à l'intérieur d'une figure quelconque?
Merci d'avance.

PS: Il me semble que si la figure est de la forme d'un C et que le point est dans le creux du C, et que le triangle traverse la figure par dessus le creux, la méthode ne fonctionne surement pas.

En prenant des angles géométriques (comme tu l'as fait, et non pas orientés), si le point M est à l'intérieur du triangle, les cosinus des 3 angles sont négatifs (angles obtus), et tu devrais obtenir somme des angles = 360°.
Si le point M est à l'extérieur du triangle, il y a au moins 2 angles aigus sur les 3, et l'un des angles est la somme des 2 autres.
Donc oui, cela me paraît une bonne méthode pour un triangle.

Pour un polygone convexe quelconque, on peut appliquer la même méthode.

par **mertosl** » 18 Juin 2015, 07:38

PSEUDA a écrit:En prenant des angles géométriques (comme tu l'as fait, et non pas orientés), si le point M est à l'intérieur du triangle, les cosinus des 3 angles sont négatifs (angles obtus), et tu devrais obtenir somme des angles = 360°.
Si le point M est à l'extérieur du triangle, il y a au moins 2 angles aigus sur les 3, et l'un des angles est la somme des 2 autres.
Donc oui, cela me paraît une bonne méthode pour un triangle.

Pour un polygone convexe quelconque, on peut appliquer la même méthode.

Bonjour et merci pour ta réponse.

par **mathelot** » 18 Juin 2015, 09:50

sinon, avec les barycentres

à résoudre d'inconnues

et

par **mathafou** » 18 Juin 2015, 11:02

Bonjour,

une autre idée est de considérer que M intérieur à ABC

aire(ABC) = aire(MAB)+Aire(MBC)+Aire(MCA)

et les aires se calculent simplement en prenant la valeur absolue du produit vectoriel
ce qui donne une condition simple sur les coordonnées en une seule formule d'un coup.

mébon, produit vectoriel en collège ...
ceci dit comme ce n'est pas un exo de classe mais un problème "perso" pour écrire un programme informatique, le niveau n'a pas grande importance.

par **Pseuda** » 18 Juin 2015, 11:41

Cela a été posté en collège, mais les relations métriques dans le triangle sont du niveau lycée... Bizarre tout ça. Par contre, le barycentre et le produit vectoriel ne sont plus au programme, même pas du lycée... :cry:

par **mertosl** » 18 Juin 2015, 12:05

Merci pour les différentes proposition.
Enfaite, la fonction ne fonctionnait (XD) pas bien, j'avais un problème avec les arccos, donc j'ai demandé confirmation sur ma méthode. Je pensai que c'était niveau collège, avec des triangle/cos/sin/tan. Pseuda m'a donné une astuce, c'était de regarder le signe des cosinus trouver. Ce qui me permet justement de ne pas passer par les arccos. Donc voila, je me retrouve bien avec des points de coordonnées random, dans une figure à forme quelconque. Merci pour les autres solutions.

Merci encore.

PS : Celles des barycentres était sans succès pour moi, peut-être de mauvais calcules de ma part; celle avec les aires, il fallait y penser.

par **Pseuda** » 19 Juin 2015, 08:46

J'ai écrit une bêtise plus haut. Il est faux de dire que si le point M est à l'intérieur du triangle, les 3 angles sont obtus. Mille excuses, j'ai répondu trop vite.

Pour trouver une solution avec les angles géométriques, on peut constater que la somme des 3 angles issus du point M est toujours égale à 360° que le point soit à l'intérieur ou à l'extérieur du triangle. Mais :
- dans le cas où le point est à l'intérieur du triangle, cette condition est vraie en prenant les 3 angles saillants (inférieurs à 180°), donnés par l'arccos.
- dans le cas où le point est à l'extérieur du triangle, elle n'est vraie qu'en prenant pour l'un des angles, l'angle rentrant (son complément à 360°).

Exemple :
si les 3 angles saillants sont égaux à 70°, 150°, 140°, alors somme des 3 angles saillants = 360° : le point est à l'intérieur du triangle
si les 3 angles saillants sont égaux à 70°, 30°, 100°, alors somme des 3 angles saillants <> 360°, mais 70°+30°+le complément à 100°(=260°) = 360°: le point est à l'extérieur

Cela se généralise à un polygone convexe.

par **Lostounet** » 21 Juin 2015, 17:34

Hello,

Pourquoi ne pas utiliser les équations des trois droites (AB), (AC) et (BC) ?
Les classer par pentes croissantes et trouver des conditions pour que le point M soit confiné dedans?

par **Pseuda** » 22 Juin 2015, 18:59

Lostounet a écrit:Hello,

Pourquoi ne pas utiliser les équations des trois droites (AB), (AC) et (BC) ?
Les classer par pentes croissantes et trouver des conditions pour que le point M soit confiné dedans?

C'est la solution la plus "évidente". On peut considérer les régions (demi-plans) que ces droites délimitent, et prendre les demi-plans tels que le 3ème point appartienne à ce demi-plan (par exemple, il faut prendre le demi-plan délimité par (AB) tel que C soit dedans), puis prendre l'intersection des 3 demi-plans ainsi considérés, c'est la solution cherchée.

par **MABYA** » 22 Juin 2015, 20:20

cela me ne paraît pas du tout pour une classe de 3éme

par **Ben314** » 23 Juin 2015, 01:41

Salut,
Il me semble ausi qu'avec des droites, c'est le plus rapide, mais je pense que ce n'est pas malin (et inutile) de parler de leur "pente".
Par exemple, la droite (AB) a pour équation (x-xA)(yB-yA)-(y-yA)(xB-xA)=0 et elle sépare le plan en deux demi plans selon que (x-xA)(yB-yA)-(y-yA)(xB-xA) est positif ou négatif.
Donc, pour voir si un point M:(x,y) est dans le même demi-plan délimité par (AB) que le point C, il suffit de regarder si (x-xA)(yB-yA)-(y-yA)(xB-xA) et (xC-xA)(yB-yA)-(yC-yA)(xB-xA) sont de même signe ou pas.

Idem pour les deux autres droites.

par **mathafou** » 23 Juin 2015, 08:10

Ben314 a écrit: il suffit de regarder si (x-xA)(yB-yA)-(y-yA)(xB-xA) et (xC-xA)(yB-yA)-(yC-yA)(xB-xA) sont de même signe ou pas

on aura bien entendu remarqué que (x-xA)(yB-yA)-(y-yA)(xB-xA) est (la composante z) du produit vectoriel

, etc ...
le calcul de ces expressions étant donc le même que celui que je proposais pour calculer avec les aires
seul l'usage qui en est fait change ...

on peut généraliser directement le critère "aire du polygone = valeur absolue de la somme algébrique égal? somme des valeurs absolues" si le polygone est convexe
si le polygone est peut-être convexe (sans être croisé, l'intérieur d'un polygone croisé est "difficile" à définir proprement !) que ce soit avec les signes ou avec les aires, il faut le faire triangle par triangle

PS

cela me ne paraît pas du tout pour une classe de 3éme

le produit vectoriel non plus, mais déja Python en 3ème ? et la formule d'Al-Kashi citée dans la demande initiale ?

par **Ben314** » 23 Juin 2015, 08:47

mathafou a écrit:on aura bien entendu remarqué que (x-xA)(yB-yA)-(y-yA)(xB-xA) est (la composante z) du produit vectoriel , etc ...

On aura aussi bien entendu remarqué que le produit vectoriel n'a rien a voir avec les problème planaire et que la "composante en z du produit vectoriel" n'est rien d'autre que.. le déterminant des deux vecteurs de R² (qui correspond effectivement à la surface du parallélogramme)
Après, et... en général, c'est effectivement en écrivant que det(AM,AB)=0 que l'on traduit le fait que M est sur la droite (AB).

par **Lostounet** » 23 Juin 2015, 09:51

Ah j'ai confondu l'algorithme de l'enveloppe convexe sur lequel je travaille où il y a une histoire de pentes haha effectivement je voulais travailler sur les demi-plans positif/négatif pour voir si M était dedans.

Après je ne sais pas si c'est la seule méthode élémentaire possible... Ben, est-il possible d'appliquer "ray-casting algorithm" qui consiste à faire passer un rayon lumineux vers le triangle: s'il y a deux intersections, M est dehors. Si une seule, il est dedans?

par **Pseuda** » 23 Juin 2015, 10:04

D'un point de vue rapidité d'écriture du programme informatique, il me paraît quand même plus rapide de calculer les 3 arccos, de faire la somme et de voir si la somme fait 360° (le point est dedans) ou non (le point est dehors), que d'établir les 3 équations de droites, de déterminer les 3 inéquations (de quel côté il faut se trouver) et de les vérifier une par une.

Mais d'un point de vue mathématique, la solution avec les droites est celle qui est la plus intuitive.

par **Lostounet** » 23 Juin 2015, 10:09

Je croyais que les fonctions trigonométriques étaient plus coûteuses (en temps) que les expressions numériques avec * / + - ??

Ou alors tu parles de la rapidité d'implémentation

par **Pseuda** » 23 Juin 2015, 10:18

Lostounet a écrit:Je croyais que les fonctions trigonométriques étaient plus coûteuses (en temps) que les expressions numériques avec * / + - ??

Ou alors tu parles de la rapidité d'implémentation

Oui à la 2ème question. Dans la solution avec les arccos, il y a 4 calculs et un test (= ou 360°) oui/non, dans la solution avec les droites il y a 3 équations à déterminer (comment faire avec un programme ?), 3 tests pour les inéquations, encore 3 tests oui/non pour le point M (du bon côté ou pas), et encore un test (il ne faut que des oui).

par **mathafou** » 23 Juin 2015, 10:54

PSEUDA a écrit:dans la solution avec les droites il y a 3 équations à déterminer (comment faire avec un programme ?)

mais le programme n'a pas à calculer les équations de droites !! juste à calculer ce qui en résulte : le signe de l'expression citée
la considération des équations est uniquement dans le raisonnement.
raisonnement qui se matérialise par la simple expression :
signe (ou directement la valeur) de (x-xA)(yB-yA)-(y-yA)(xB-xA) etc ( = et autres expressions semblables)
rien d'autre n'est à calculer que cette formule là.

par **Pseuda** » 23 Juin 2015, 12:17

mathafou a écrit:mais le programme n'a pas à calculer les équations de droites !! juste à calculer ce qui en résulte : le signe de l'expression citée
la considération des équations est uniquement dans le raisonnement.
raisonnement qui se matérialise par la simple expression :
signe (ou directement la valeur) de (x-xA)(yB-yA)-(y-yA)(xB-xA) etc ( = et autres expressions semblables)
rien d'autre n'est à calculer que cette formule là.

Ah oui c'est vrai. Il faut que le signe de l'expression (équation de la droite (AB)) soit le même avec M qu'avec C, etc... . Donc cela revient pratiquement au même. :zen:

Point à l'intérieur triangle

Point à l'intérieur triangle

Qui est en ligne