Discussion :

[Kewlcool]

Bonjour à tous,

Je voudrais savoir si il y'a une librairie qui permet de transformer un polygone complexe en triangles.
Concrètement l'idéal serait de passer en entré les sommets du polygone et que la fonction retourne les sommets de tous les triangles.

Auriez-vous une idée ?

Merci d'avance !

[Sivrît]

Je n'en connais pas en particulier mais ça devrait assez facilement se trouver. Le mot clef à chercher est "triangulation", delaunay par exemple. "polygon triangulation" en anglais.

[Fabien Henon]

Normalement comme tu connais les sommets de ton polygone il me semble que tu dois pouvoir faire ça assez facilement toi même.
Ne suffirait il pas de garder les sommets de ton polygon mais de les afficher en triangle strip?

[bafman]

Normalement comme tu connais les sommets de ton polygone il me semble que tu dois pouvoir faire ça assez facilement toi même.
Ne suffirait il pas de garder les sommets de ton polygon mais de les afficher en triangle strip?

ce n'est pas aussi simple que ça car il existe plusieurs triangulation possible pour un jeu de vertex donné...

[Kewlcool]

Merci de vos réponses. J'ai trouvé un certain nombre de chose et je pense m'orienter sur la triangulation de delaunay. Le problème que j'ai actuellement c'est que tous les algo que j'ai trouvé découpe le polygone en triangle, mais il y a un certain nombre de trianglez qui sont inutiles et qui pourrait être supprimé. La triangulation de delaunay permet de résoudre cela ?

Merci bien.

[HanLee]

Il est convexe ou pas ton polygone?

[plegat]

...mais il y a un certain nombre de trianglez qui sont inutiles et qui pourrait être supprimé. La triangulation de delaunay permet de résoudre cela ?

Oui (enfin, si on va jusqu'au bout!)
Mais qu'est-ce exactement qu'un triangle "inutile"???

Si c'est un triangle de surface nulle, tu le supprimes, point barre.

Si c'est un des triangles externes à ton polygone (vu que normalement avec delaunay tu encadres ton polygone par un rectangle), il y a toute une procédure à effectuer afin de retrouver la frontière de ton polygone. Ensuite il faut trier tes triangles en partant de l'extérieur (donc des triangles ayant au moins un sommet sur les sommets du rectangle englobant) et en allant vers la frontière (il faut gérer les voisins au passage afin de savoir où aller dès qu'on atteint la frontière du polygone). Normalement à la fin il ne reste que ton polygone triangulé.

Le net regorge de sources et de doc pour la triangulation de delaunay, c'est la base des triangulations...