IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Triangle intérieur à un polygone ou extérieur


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Septembre 2013
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Lycéen
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Septembre 2013
    Messages : 25
    Points : 15
    Points
    15
    Par défaut Triangle intérieur à un polygone ou extérieur
    Bonjour

    J'essaie de coder la méthode des oreilles pour trianguler un polygone (convertir un polygone en plusieurs triangles pour l'afficher avec OpenGL).

    Selon Wikipedia:
    Une manière de trianguler un polygone simple est d'utiliser le fait que tout polygone simple à au moins quatre sommets possède au moins deux « oreilles »3. Une oreille est un triangle avec deux arêtes appartenant à la frontière du polygone, et la troisième située à l'intérieur du polygone. L'algorithme consiste à trouver une telle oreille4, à la retirer du polygone, ce qui donne un nouveau polygone qui répond toujours aux conditions, et à répéter l'opération jusqu'à ce qu'il n'y ait plus qu'un seul triangle.
    L'avantage de cette méthode est qu'elle s'applique aussi à des polygones concaves.
    L'algorithme semble relativement simple à mettre en œuvre, simplement se pose la question initiale: Comment savoir si la 3° arête est située à l'intérieur du polygone? Ça me semblait simple, mais en fait ça ne l'est pas du tout.

    Merci
    Cordialement
    Cathy L.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Ton polygone d'origine, c'est une succession de points. On va supposer que les points sont classés dans le sens des aiguilles d'une montre. Si ce n'est pas le cas, tu prends tous tes points, et tu les lis dans le sens inverse, et ils tournent t alors dans le sens des aiguilles d'une montre.

    Notre polygone est constitué des points (A , B, C, D, E, F, etc)
    Je prends le triangle (A,B,C)

    Calcule (xb-xa)*(yc-ya) - (xc-xa)*(yb-ya). Le signe de ce calcul va te dire si le triangle est 'clock-wise' ou 'non-clock-wise'. Je ne sais plus si le signe positif correspond aux triangles intérieurs ou extérieurs, mais tu peux faire l'expérience et tu trouveras rapidement la réponse.
    Si ce calcul donne 0, c'est le cas limite, c'est que les 3 points A B et C sont alignés, mais dans ton cas, ça ne devrait pas arriver.

    Pour plus de recherche sur le sujet, tu peux taper 'Produit Vectoriel' sur Google
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Septembre 2013
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Lycéen
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Septembre 2013
    Messages : 25
    Points : 15
    Points
    15
    Par défaut
    D'abord merci beaucoup de vous intéresser à mon cas.

    J'ai donc compris que si je sais dans quel sens tournent mes points, avec le produit vectoriel je peux déterminer si trois points successifs forment un triangle faisant partie du polygone ou non, c'est bien ça?

    Comme j'utilise des fichiers que je télécharge sur internet et qui décrivent ces polygones, je suis obligé de déterminer mathématiquement si le polygone est décrit dans le sens des aiguilles d'une montre ou non, j'ai trouvé ça:
    Je crois que c'est possible de regarder si ton polygone est défini dans le sens horaire avec uniquement un seul point. Le principe est le suivant :

    Prendre le point avec l'ordonnée y la plus élevée dans ta liste de points.
    Déterminer les deux arêtes associées au point, et noter leur angle orienté avec l'axe (Ox)
    En considérant ton tableau de triangles sous forme cyclique, si l'arête qui apparaît dans le triangle suivant est celle dont l'angle orienté est le moins grand, ton polygone est dans le sens trigonométrique. Sinon, il est dans le sens horaire.

    La méthode se base sur le fait que le point à l'ordonnée la plus élevée appartient nécessairement à l'enveloppe convexe de ton polygone, ainsi ça ne peut pas être un point intérieur. De plus, les deux points voisins seront situés sur le demi plan des ordonnées inférieures. Si ton polygone n'est pas croisé, l'angle orienté suffit alors à déterminer le sens.

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Ce que tu as trouvé me parait très bien. Il y a une condition qui me paraît un peu compliquée à traduire en langage informatique :
    si l'arête qui apparaît dans le triangle suivant est celle dont l'angle orienté est le moins grand,
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Membre à l'essai
    Homme Profil pro
    Lycéen
    Inscrit en
    Septembre 2013
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Lycéen
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Septembre 2013
    Messages : 25
    Points : 15
    Points
    15
    Par défaut
    Merci encore

Discussions similaires

  1. Point à l'intérieur d'un triangle ?
    Par remi77 dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 15/05/2017, 15h49
  2. Réponses: 5
    Dernier message: 08/03/2011, 23h29
  3. Objets de base (cube, triangles, polygones etc)
    Par crischprolch dans le forum OpenGL
    Réponses: 10
    Dernier message: 02/04/2008, 15h31
  4. Réponses: 3
    Dernier message: 02/07/2007, 11h32
  5. [Algo] Point à l'intérieur d'un polygone ?
    Par kebby dans le forum C++Builder
    Réponses: 5
    Dernier message: 23/05/2003, 14h22

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