1. #1
    Nouveau membre du Club
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    juin 2015
    Messages
    40
    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 : 40
    Points : 33
    Points
    33

    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 : 89
Taille : 20,4 Ko

  2. #2
    Expert confirmé
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    2 016
    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 016
    Points : 5 614
    Points
    5 614

    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 averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    581
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 581
    Points : 441
    Points
    441

    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
    6 988
    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 : 6 988
    Points : 22 024
    Points
    22 024

    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 averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    581
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 581
    Points : 441
    Points
    441

    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 : 89
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 confirmé
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    2 016
    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 016
    Points : 5 614
    Points
    5 614

    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 averti Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    581
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 581
    Points : 441
    Points
    441

    Par défaut

    Exact

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, 02h41
  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, 15h26
  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, 12h05
  4. Réponses: 1
    Dernier message: 21/10/2009, 15h21

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