Discussion :

[zedrummer]

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.

[tbc92]

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

[zedrummer]

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.

[tbc92]

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,

[zedrummer]

Merci encore