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?

[Kewlcool]

Il est concave.

[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...

[Kewlcool]

Les triangles inutiles c'est les triangles inclus dans d'autres triangles possible composant le polygone.
Le premier schéma, si j'ai bien compris, c'est le rendu de la triangulation de delaunay.



Le second schéma avec les segments rouges c'est le nombre de triangle que j'aimerai avoir au final.



Et ce dernier schéma c'est pour un polygone concave.


Je n'ai peut être pas bien compris triangulation de delaunay, mais le but de tout ça est d'avoir le moins de triangle composant un polygone donné.

[plegat]

Les triangles inutiles c'est les triangles inclus dans d'autres triangles possible composant le polygone.

Ce ne sont pas des triangles "inutiles"... par contre il y a plein de points inutiles, si tu vas par là.
Si tu parles de polygone, il n'y a que les points de la frontière de définis, donc tu n'auras pas de triangles "inutiles" (vu que ceux-ci sont construits via les points intérieurs au polygone). Si tu as ces fameux triangles, c'est que tu as fournis des points intérieurs (auquel cas tu ne triangules pas un polygone... mais une surface)... ou que l'algo utilise une taille limite d'éléments et va découper les triangles trop gros en plus petits.

Donc, la solution:
- si tu as fourni des points intérieurs, supprime-les et n'utilise que les points de la frontière du polygone
- si tu n'as pas fournis de points intérieurs, regarde si l'algo utilise une taille limite d'éléments (aire, longueur de côté,...), et si oui augmente-la.

Attention également au respect de la frontière... j'espère que les algos que tu as utilisé en tiennent compte...

[Kewlcool]

ou que l'algo utilise une taille limite d'éléments et va découper les triangles trop gros en plus petits.

Ha yes bien vu ! j'avais pas capté la taille maximum, merci bien je pense que la ça va le faire !

Quand tu parles du respect de la frontière c'est pour les polygone concaves ? Que je n'ai pas de triangle hors du polygone ? Ou c'est autre chose ?

En tout cas merci c'est beaucoup plus logique en effet !

[plegat]

Quand tu parles du respect de la frontière c'est pour les polygone concaves ? Que je n'ai pas de triangle hors du polygone ? Ou c'est autre chose ?

C'est autre chose!
Ca dépend si l'algo est complet ou pas... si il est complet, tu dois fournir en données ta liste de point, ainsi que les segments permettant de définir le polygone (ou n'importe quelle autre méthode permettant de classer les points afin de tracer le périmètre du polygone). Normalement, après l'insertion de tous les points dans l'algorithme, tu obtiens une triangulation de ton espace de travail, mais tu ne retrouves pas exactement ton polygone. Il y a une étape supplémentaire qui va arranger les triangles, faire quelques manipulations, afin d'obtenir tous les segments composant le périmètre de ton polygone. C'est ça que j'appelle "respect de la frontière".
Mais si tu utilises un algo complet, il doit te donner ton polygone triangulé au final.