1. #1
    Nouveau membre du Club
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    juin 2015
    Messages
    42
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Chercheur en informatique

    Informations forums :
    Inscription : juin 2015
    Messages : 42
    Points : 37
    Points
    37

    Par défaut Détection d'un objet dans un triangle

    Bonjour à tous,
    Svp j'ai un exercice à résoudre concernant la détection des objets dans un triangle en 2D.
    La figure ci-dessous explique mon problème. Il s'agit de détecter des objets, dans cet exemple des carrées.
    En fait, il y a différents cas pour résoudre le problème:
    -Un carré noir : je le détect pas.
    -Un carré rouge : je le détecte en entier.
    -Un carré vert : je le détecte partiellement (aussi je dois récupérer la parite détéctée).
    Comme données, j'ai l'angle et la hauteur (distance) de ce triangle.
    Des suggestions svp ?
    Merci
    Nom : aaa.jpg
Affichages : 131
Taille : 20,4 Ko

  2. #2
    Expert éminent
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    2 119
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : mai 2010
    Messages : 2 119
    Points : 6 051
    Points
    6 051

    Par défaut

    Pour ma part il faut faire plusieurs test:
    4 test avec les points (s'ils sont dans le triangle ou non).
    4 autre test segment /triangle (ou 3x segment/segment) (si 2 segment se croise alors collision).

    Bien sur si un seul est vrai , inutile de tester les autres .
    Le test avec les points étant le plus rapide (et sûrement le cas le plus courant) c'est celui que tu devrait tester en premier

  3. #3
    Membre confirmé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 590
    Points : 450
    Points
    450

    Par défaut

    Par soucis de performance, un premier test permet d'écarter des candidats à un coût algorithmique très faible :

    si le carré n'est pas dans le rectangle englobant du triangle, alors il est impossible qu'il soit dans le triangle.

    Si ça renvoie true alors tu lances l'algo suggéré par Kannagi

  4. #4
    Responsable Modération
    Avatar de Obsidian
    Homme Profil pro
    Chercheur d'emploi
    Inscrit en
    septembre 2007
    Messages
    7 069
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur d'emploi
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2007
    Messages : 7 069
    Points : 22 362
    Points
    22 362

    Par défaut

    Hello,

    Citation Envoyé par mok_tun Voir le message
    Bonjour à tous,
    Svp j'ai un exercice à résoudre concernant la détection des objets dans un triangle en 2D.
    La figure ci-dessous explique mon problème. Il s'agit de détecter des objets, dans cet exemple des carrées.
    Tant que ce ne sont que des carrés et qu'ils ont tous la même taille, ça ne pose pas trop de problème. Si tu dois en revanche, à terme, être capable de « voir » n'importe quel polygone en 2D (fussent-ils éventuellement extrudés verticalement, ce qui est le principe de DOOM et DOOM II, dans les années 1990), alors tu auras déjà des difficultés s'ils sont concaves par endroits. Le plus simple consistant alors à les découper en plusieurs polygones strictement connexes : BSP.

    Ensuite, beaucoup des techniques exposées ci-dessus te feront gagner beaucoup de temps mais aucune d'elle n'est parfaite en l'état. Il se peut très bien que le centre de gravité de ta figure soit en dehors du triangle mais que les parties extérieures du polygone « mordent » dessus quand même. Il se peut également que tous les sommets soient en dehors du triangle mais que les côtés traversent quand même un coin de celui-ci. Une bonne approche, assez rapide, consiste alors à détecter une intersection entre un segment de ton polygone et chacun des trois segments de ton triangle.

    Avec cela, tu seras capable de détecter les polygones qui « franchissent la frontière » mais pas ceux qui sont déjà entièrement dedans. Pour cela, le plus simple est de vérifier si au moins un des sommets est à l'intérieur du triangle, chose qui peut s'optimiser grandement au vu de la forme de la disposition du triangle. Il suffit de vérifier si le sommet est au dessus du point le plus bas du triangle mais dans la limite d'une hauteur h (donc en faisant une simple soustraction et en vérifiant si le résultat est compris entre 0 et h), puis de vérifier si son abscisse est sur l'axe, avec une tolérance proportionnelle à la hauteur (avec une simple règle de trois).

    Ces deux approches combinées te permettront de détecter tes polygones mais, surtout si tu dois ensuite estimer la surface intrusive, tout le problème se rapporte en fait à vérifier si l'intersection de tes deux surfaces (dans le sens ensembliste du terme : ∩) est non-vide. Dans ce cas, tu serais peut-être intéressé par faire directement de la CSG.

  5. #5
    Membre confirmé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 590
    Points : 450
    Points
    450

    Par défaut

    Citation Envoyé par mok_tun Voir le message
    Bonjour à tous,
    En fait, il y a différents cas pour résoudre le problème:
    -Un carré noir : je le détect pas.
    -Un carré rouge : je le détecte en entier.
    -Un carré vert : je le détecte partiellement (aussi je dois récupérer la parite détéctée).
    Nom : aaa.jpg
Affichages : 131
Taille : 20,4 Ko

    Bonjour,

    Pour te répondre en prenant plus le temps :

    Soient C ton carré et T ton triangle. Soit la fonction EvaluerCarreDansTriangle qu'on nomme ECDT, qui renvoie un booléen, et Un tableau P de points (ceus qui sont dans T).

    Algo :

    1/ Si aucun points de C sont dans le rectangle englobant de T, ECDT renvoie false. Cout très faible pour éliminer facilement des candidats
    2/ Sinon, boucler sur tous les points pi de C et calculer s'ils sont présents dans T, si oui: ajouter pi dans dans P, et en fin de boucle renvoyer true et P

    Pour calculer si un point est présent dans un polygône :

    https://jeux.developpez.com/tutoriel...omplexes/#LIII

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    bool Collision(Point tab[],int nbp,Point P)
    {
      int i;
      for(i=0;i<nbp;i++)
      {
         Point A = tab[i];
         Point B;
         if (i==nbp-1)  // si c'est le dernier point, on relie au premier
             B = tab[0];
         else           // sinon on relie au suivant.
             B = tab[i+1];
         Vecteur D,T;
         D.x = B.x - A.x;
         D.y = B.y - A.y;
         T.x = P.x - A.x;
         T.y = P.y - A.y;
         float d = D.x*T.y - D.y*T.x;
         if (d<0)
            return false;  // un point à droite et on arrête tout.
      }
      return true;  // si on sort du for, c'est qu'aucun point n'est à gauche, donc c'est bon.
    }

  6. #6
    Expert éminent
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    2 119
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : mai 2010
    Messages : 2 119
    Points : 6 051
    Points
    6 051

    Par défaut

    @guitz
    Le test avec seulement des points n'est pas exhaustive.
    Il se peut qu'il y est des collisions avec un triangle sans que aucun point ne se trouve dans a l'intérieur du triangle.
    (D'ou qu'il faut rajouter des collision segment/segment en plus ).

  7. #7
    Membre confirmé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 590
    Points : 450
    Points
    450

    Par défaut

    Exact

  8. #8
    Membre expérimenté Avatar de Astraya
    Homme Profil pro
    Consommateur de café
    Inscrit en
    mai 2007
    Messages
    855
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France

    Informations professionnelles :
    Activité : Consommateur de café
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mai 2007
    Messages : 855
    Points : 1 525
    Points
    1 525

    Par défaut

    Bonjour,

    Je vais couper court au débat sur comment faire le test ^^

    Le seul test valable et performant est le test Cone2D ( Triangle ) avec 4 segments ( Carré ).
    Les coordonnées de ton Triangle sont polaire il faut donc que tu en déduise les 3 points de ton triangle pour le test de collision.
    De plus tu dois non seulement trouver si collision il y a mais aussi ou les collisions ont lieux ( Il s'agit donc de trouver les points d'intersections entre les 4 segments de tes carrés avec le triangle )

    Il existe des librairies qui font très bien cela et je te conseille fortement de t’en inspirée et surtout de comprendre les mathématique derrière cela.
    GeomtricTools est une excellente source de savoir de ce coté la ==> https://www.geometrictools.com/Source/Mathematics.html


    Pour la suite de l'explication je te conseille de prendre papier et crayon:

    De son coté, il part du principe simple:
    - Ton carré n'est que 4 segments.
    - Si un segment intersecte le triangle il y a collision.
    - Si la droite ( ton segment infini ) ne collisionne pas ton triangle tu n'as pas de collision de segment a tester.

    Donc il faut que tu fasse dans l'ordre:
    1- La collision d'une droite avec un triangle ( récupéré le 2 points max de collision )
    2- Tu utilises cet algorithme pour faire le second test ( très rapide ) du segment qui se base sur ta droite.
    - Si les points de collision de ta droite sont sur ton segment, le segment collision et le point d'intersection est celui de la droite également.
    - Si les points de collision de ta droite ne sont pas sur ton segment ( 0 collision )

    Une optimisation importante est de ne pas représenter ton segment comme 2 points. mais comme un point au centre de ton segment, une direction ( Vecteur unitaire ) et une distance ( Extent ).
    Une autre est de représenter ta droite comme un point et une direction ( Tu devineras que le point de la droite est le centre de ton segment, que la direction de ta droite est la direction de ton segment ). L'Extent de ton segment n'est quand a lui plus que la distance absolue du point de ta droite/segment.

    Le test de la droite ne te donneras pas les points d'intersection directement mais la distance entre le point de ta droite et le point d'intersection.
    Le test du segment utilisera la distance donné par le test de la droite en comparant à son Extent. Donc si (Distance Absolue Intersection Droite <= Extent) == Intersection!
    Et le point n'est autre que (Point Segment)*Direction*(Distance Intersection Droite). Et ce pour les 2 distances du test de la droite.

    Ce test est extrêmement simple mais à un défaut. il te donnera aucune intersection si le triangle est entièrement dans le carré.
    Pour palier à ce problème, tu peux prendre un autre test qui est le test d'une OBB2D avec 3 segments (triangle) et le test se trouve ici ( https://www.geometrictools.com/GTEng...OrientedBox2.h )

    Pour info les TIQuery sont les Test Intersection Query et les FIQuery sont les Find Intersection Query ( le premier test juste, le 2nd trouve les points d'intersections )
    Homer J. Simpson


Discussions similaires

  1. Détection d'un objet dans une portée sous la forme pyramide
    Par mok_tun dans le forum Général Algorithmique
    Réponses: 1
    Dernier message: 04/08/2017, 03h41
  2. Détection d'un objet dans une portée sous la forme pyramide
    Par mok_tun dans le forum Développement 2D, 3D et Jeux
    Réponses: 1
    Dernier message: 02/07/2017, 16h26
  3. Optique (détection d'objet dans un faisceau laser)
    Par nablovic dans le forum Général Algorithmique
    Réponses: 0
    Dernier message: 16/04/2012, 13h05
  4. Réponses: 1
    Dernier message: 21/10/2009, 16h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo