Triangle appartient a un rectangle

Bonjour, je voudrai écrire une fonction qui me dit si un triangle appartient a une région( un rectangle donné) si plus d’un point de ce triangle appartient ce rectangle . pour cela j’ai divisé le problème en deux cas

1 _ si deux tête du triangle appartiennent au rectangle ce qui retourne true

2_si il existe un segment du rectangle qui est découpé par deux segment du triangle différent et vis versa

Mais je ne sais pas si cela englobe bien tout les cas de l’intersection et si c’est la cas comment implémenter la 2 eme partie en sachant que j’ai implémenter une fonction intersection segment (sans avoir a vérifier cas par cas (segment par segment )) sinon une méthode pour résoudre mon problème.

Merci

Salut,

Est-ce que tu sais vérifier si un point est dans un rectangle ?

Si oui, pour vérifier si deux sommets au moins d’un triangle sont dans un rectangle, prends chaque sommet du triangle et pour chacun vérifie s’il est dans le rectangle. Tu vois ?

Salut,

On est d’accord que tu vois ton triangle et ton rectangle comme des surfaces, et que tu cherches à savoir s’il y a une intersection entre ces surfaces ?

Dans ce cas, en effet, les deux cas que tu cites ne sont pas exhaustifs. Par exemple, si le rectangle est entièrement contenu dans le triangle.

Intuitivement, je dirais que le plus simple est de voir tes surfaces comme des systèmes d’inéquations, et d’en résoudre l’intersection.

Donc tu cherches à savoir si un point du contour du triangle est dans la surface définie par le rectangle ? Si oui, ta condition m’a l’air ok, mais formulée comme ça ça risque d’être un peu pénible à coder.

1 _ si deux tête du triangle appartiennent au rectangle ce qui retourne true

Pourquoi pas une seule ?

2_si il existe un segment du rectangle qui est découpé par deux segment du triangle différent et vis versa

Pourquoi pas un seul segment du triangle ? (« si il existe un segment du rectangle qui est "découpé" par un segment du triangle »)

Je pense comme Lucas.

Si tu as une intersection entre un segment du triangle et un segment du rectangle, alors il "est" dans le rectangle.
Sinon, tu testes un seul sommets du triangle, s’il est dans le rectangle alors tous les points du triangle y sont.
Sinon, le rectangle et le triangle n’ont aucun point commun.

Ou bien le rectangle est complètement contenu dans le triangle…

Arf ! Bien vu !

Merci beaucoup pour vos réponses

@ache ton raisonnement m’intéresse beaucoup, mais je n’ai pas bien compris comment ça fonctionne, tu as dit si le produit vectoriel est du même signe tu continue mais de même signe que quoi ?

Est-ce-que tu pourrai s’il te plait m’expliquer un peu plus en détails ?

La méthode que décrit @che est effectivement la bonne idée pour vérifier qu’un point est dans un polygone convexe (et en particulier pour un rectangle).

Dans le cas spécifique du rectangle on peut (de mon point de vue) faire un peu plus simple : j’ai essayé de faire un dessin sur Geogebra. Pour savoir si E est dans le rectangle ABDC, on remarque qu’il suffit de voir si le projeté de E sur (AB) (resp. (AC)) est entre A et B (resp. A et C). En traduisant ça en terme de produit scalaire, ça donne :

ou encore :

Et on peut calculer les deux produits scalaires et les deux normes au carré en restant dans les entiers.

@naomi: Le concept, c’est de faire le tour du rectangle. Donc prendre les segments $AB$, $BC$, $CD$, $DA$ (dans cet ordre) successivement. Tu va d’abord calculer le produit vectoriel entre $AB$ et $AE$ (le deuxième vecteur, c’est la ’base’ du premier et $E$, donc $AE$, $BE$, $CE$ puis $DE$). À chaque fois, cela t’indiquera de quel coté se trouve $E$ par le signe du résultat. Donc $AB$ et $AE$ doit être du même signe que $BC$ et $BE$ qui doit être du même signe que $CD$ et $CE$, idem pour $DA$ et $DE$.

@Lucas-84: Ça à l’air intéressant mais il est tard et j’ai du mal à te suivre

Par exemple, dans ma tête, $AE$ part de manière orthogonale à $AC$, mais pas trop loin. On se retrouve avec $\textbf{AB}\cdot\textbf{AE}\le||\textbf{AB}||^2$. Et du coup, dans ma tête, ça ne marche pas :/

Mais c’est peut-être parce-que je n’y est pas assez réfléchi. Je précise que je n’ai pas regardé le graphe que tu as fait car il faut se connecter (et j’ai moyen envie). Je vois ça demain.

Sinon, si jamais ton problème vient a concerner des polygones convexes plus complexes, il y a l’algorithme GJK. Ça te dis s’il y a une intersection, ou s’il n’y en a pas, la distance entre tes polygones.

(Et qui, depuis peu ne souffre plus d’une énorme erreur numérique quand la distance est faible. Si ça t’intéresse, il doit y avoir une publication de début 2017 la dessus)

Oui, je ne sais pas pourquoi j’ai parlé de sinus… je savais qu’un produit vectoriel suffisait, et qu’il fallait juste regarder le signe de la 3ème composante… n’importe quoi. Comme quoi, après minuit, faut aller au dodo.

Pour la droite AB, pour savoir si C et M sont de part et d’autre de cette droite, ou dans le même demi-plan :

• On calcule le produit vectoriel AB AC, et on regarde la 3ème composante z1.

• Puis on calcule le produit vectoriel AB AM, et on regarde la 3ème composante z2.

• Si ces 2 nombres z1 et z2 sont de même signe, alors M est dans le même demi-plan que C.

Ça doit être la fatigue, parce que je pense que c’est correct (et j’ai pas trop compris ton objection). Par exemple pour un rectangle avec un coin bas gauche en $(0,0)$ et haut droite en $(x,y)$, la condition sur $E=(x_E,y_E)$ s’écrit :

et pour peu qu’on choisisse un rectangle non dégénéré, c’est bien équivalent à :

En écrivant ça, je me rends compte que, par contre, ça ne marche pas pour un rectangle réduit à un segment ou à un point (si on considère que c’est effectivement une entrée valide).

(Désolé pour l’inscription, je maîtrise pas trop leur truc de partage. J’ai changé un truc pour essayer.)

Ah oui ! Non mais je suis d’accord.

C’est juste que le rectangle s’appele ABDC et pas ABCD x)
Je comprenais pas pourquoi tu prenais la diagonale.

Oups.

Merci beaucoup pour vos réponses merci @ache pour les détails je comprend mieux J’ai utilisé les inéquations d’un demi plan si Deux points sont tout les deux inférieure ou supérieure a l’équation de la droite ils font partie du même demi plan

Salut à tous,

Message de rappel : merci de ne pas utiliser les sujets des autres pour poser vos propres questions, sauf si la question est directement liée à la discussion. Et surtout, des recherches sur le forum ou Internet peuvent vous apporter la réponse sans même avoir à créer de nouveau sujet. Alors faîtes un petit tour dessus d’abord.

Bisous les amis.