Discussion :

[Chatanga]

Bonjour,

Je recherche un algorithme pour diviser (sans rajouter de points) un polygone concave en polygones convexes. Ca a l'air simple, mais impossible de mettre la main sur quoique ce soit. J'ai bien trouvé un lien sur cette page de Wikipedia, mais rien de bien concluant. J'imagine que je ne dois pas utiliser les bons mots clefs...

[Graffito]

Hertel-Mehlhorn Algorithm
voir : http://www.bringyou.to/compgeom/

Mots clés : Minimum/optimal decomposition convex polygon [Greene]

[Chatanga]

Merci,

Si j'ai bien compris, ma "convexification" de polygone se réalise en fait en deux étapes : triangularisation (ce qui suffit en soi) puis optimisation en retirant des diagonales (c. à d. segments internes) inutiles.

J'ajoute le lien suivant pour ceux que ça intéresserait : http://www.cgafaq.info/wiki/Simple_P..._Triangulation.