Triangle appartient a un rectangle

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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

+0 -0

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 ?

Le saviez-vous ? Chaque -1 que vous mettez vous fait gagner un point de QI.

+1 -0

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.

Édité par ache

ache.one                                                            🦊

+0 -0

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.

ache

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

I don’t mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+0 -0

Cette réponse a aidé l'auteur du sujet

Pour savoir si un point est dans un rectangle…

Soit ABCD notre rectangle, et soit M le point étudié. La droite AB coupe le plan en 2. Par rapport à cette droite, C est dans un des 2 demi-plans ; Si M n’est pas dans le même demi-plan que C, alors M n’est pas dans le rectanle ABCD, fin du traitement.

Et rebelote, mais en prenant la droite BC, puis la droite CD et enfin la droite DA. A chaque fois, on divise le plan en 2 demi-plan, et si M est dans le bon demi-plan, on continue.

Reste à trouver le bon traitement pour dire : A partir d’une droite AB, et de 2 points C et M, est ce que C et M sont de part-et d’autre de la droite AB, ou du même côté. 2 angles à calculer , 2 sinus à calculer … et ça va le faire.

+0 -0

Cette réponse a aidé l'auteur du sujet

@elegance: L’idée est là, mais pour le traitement, mieux vaut éviter de calculer des angles et des sinus.

Ça se fait assez bien avec un produit vectoriel en fait. Ça évite d’avoir à utiliser des valeurs flottantes.

Supposons que tu aies un rectangle ABCD et un point à tester. E …

Tu fais le produit vectoriel entre AB et AE … Puis tant que c’est du même signe, tu continues avec BC et BE …

Sachant que le produit vectoriel de deux vecteurs se calcule vraiment simplement, ça simplifie pas mal la tâche. Et pour peut qu’à la base tu utilises des coordonées entières, tu as pas besoin de toucher au flottant.

PS: C’est en gros, l’idée, mais il y a quelque petits détails à régler (comme par exemple si AB et AE donne 0 alors on prend le signe du produit vectoriel entre BC et BE, sauf si celui-ci aussi est nul … Dans ce cas, B et E sont confondus, …)

ache.one                                                            🦊

+1 -0
Auteur du sujet

Merci beaucoup pour vos réponses :D

@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 ?

+0 -0

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 :

$$0\le \frac{\textbf{AB}\cdot \textbf{AE}}{||\textbf{AB}||}\le ||\textbf{AB}||\; \text{et} \;0\le \frac{\textbf{AC}\cdot \textbf{AE}}{||\textbf{AC}||}\le ||\textbf{AC}||$$

ou encore :

$$0\le \textbf{AB}\cdot \textbf{AE}\le ||\textbf{AB}||^2\; \text{et} \;0\le \textbf{AC}\cdot \textbf{AE}\le ||\textbf{AC}||^2$$

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

Édité par Lucas-84

@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 O_o

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.

ache.one                                                            🦊

+0 -0

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)

+0 -0

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.

Édité par elegance

+0 -0

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

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.

ache

Ç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 :

$$0\le x_Ex\le x^2\; \text{et} \; 0\le y_E y\le y^2$$

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

$$0\le x_E\le x\; \text{et} \; 0\le y_E\le y$$

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.

ache.one                                                            🦊

+1 -0
Auteur du sujet

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

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte