Decomposé un polygone 2D troué en plusieurs polygones pleins

**jcloupgarou** · 06/06/2006, 17h05

Bonjour,

Je dois effecter un calcul sur des polygone 2D pleins (non troué). Hors j'ai a ma disposition des polygones évidés par d'autres polygones.
Comment décomposer le polygone troué initial en N polygones pleins, svp ? (pas de contraintes : decomposition non unique, N indefini)

Par exemple avec le polygone P0P1P2P3P4P5P6P7 troué par T0T1T3T4 T5T6T7 (polygonTroue.jpg), je peux le decomposer en trois polygones pleins
P0P1P2T4T3T1T0, P0T0T4P2P3T6T5P7 et P7T5T7T6P3P4P5P6 (polygonSubdivise.jpg) (voir image attachée)

Merci, bonne journée
Jc

**Laurent Gomila** · 06/06/2006, 17h43

Je ne connais pas vraiment les algorithmes existant pour ça, mais intuitivement je pense qu'un point de départ serait de découper récursivement ton polygone par une droite définie par l'un des côtés de l'un des trous. Tu obtiens ainsi N polygones, auquels tu peux à leur tour appliquer l'algorithme s'ils possèdent encore des trous.

**jcloupgarou** · 21/06/2006, 11h26

Je m'en sors pas avec cet algo, et j'ai trouvé aucune autre indication sur le web... Personne n'a jamais eu besoin de faire cela ?

**bafman** · 21/06/2006, 13h55

malheureusement, c'est un sujet nettement plus compliqué qu'il n'y parait

Je m'y etait interessé à une époque et on m'avait dit de regarder du coté de voronoï, mais je n'y avais rien compris (et surtout pas trop vu le rapport a part de decouper le tout en sous polygones convexes)

**Laurent Gomila** · 21/06/2006, 16h36

Qu'est-ce qui te pose problème avec cet "algo" exactement ?

mat.M · 21/06/2006, 18h27

Si tu veux pas te casser la tête sous Windows tu peux créer des régions avec CreatePolygonRgn , les points des polygones et CombineRgn qui donne une région résultante.
Mais ce n'est pas portable

**dazz_x** · 22/06/2006, 09h23

[Mode HS ON]

Je m'y etait interessé à une époque et on m'avait dit de regarder du coté de voronoï

effectivement, je ne vois pas le rapport, sinon comme dual d'une triangulation (de Delaunay)...

[Mode HS OFF]

L'algo de Laurent est très bien, et plutôt facile à mettre en place, je ne pense pas que tu puisses trouver quelque chose de plus simple --> il va falloir passer par une triangulation de ton polygone troué. L'idéal, ce serait une décomposition y-monotone de ton polygone troué (je sais qu'un algo existe dans un Graphics Gems ou un Game Programming Gems (cherche Manesha) et qu'il permet de faire ce que tu veux... reste à le trouver

)
Pour la triangulation, je te renvoie à http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html, mais tout dépend de l'utilisation que tu en feras. Dans certains cas, c'est un peu utiliser une bombe atomique pour ouvrir une huître

Voilà, voilà