Algorithmes pour la triangulation des polygones

9

J'ai eu du mal à trouver un algorithme ou à publier des articles sur la triangulation des polygones auto-entrecroisés (également des polygones avec structure de trous).

Quelqu'un peut-il me guider pour trouver le papier / algorithme publié, s'il vous plaît?

PS: quelqu'un marque correctement cette question, je n'ai pas assez de points de réputation pour le faire.

ds.algorithms reference-request cg.comp-geom Prashant Cholachagudda
la source
5
Peut-être que votre accent est mis sur l'aspect auto-intersecté de vos polygones? La plupart des algorithmes (comme celui suggéré par Suresh) supposent un polygone simple. Vous devrez d'abord calculer les points d'intersection aux auto-croisements, via, par exemple, un balayage plan. Ensuite, vous pouvez appliquer l'algorithme de Seidel.
Joseph O'Rourke

Réponses:

7

Avez-vous considéré l'algorithme de Seidel ?

Suresh Venkat
la source
L'algorithme de Seidel, bien que très rapide, doit être modifié pour gérer les auto-intersections. Ce n'est pas impossible, mais pas immédiatement évident.
Simon F