Decomposition Geometrique de polygonRésolu

Question

Voila, c'est dit dans le titre, je cherche a decomposer un polygon, abolument pas regulier, en differentes parties geometriques que je pourrait elles meme divisé, jusqu'a ne trouver que des triangles en fin de compte. Le but etant d'en trouver le moins possible. En faite, je cherche un moyen de creer des triangles dont tous les points sont coplanaire, et de pouvoir les dessiner avec DirectX. 
Bon j'y ai pas mal reflechis et j'ai pensé utiliser la propriete des Regions mais a partir de la, a par creer un cadrillage, c'est pas terrible, et ca fait beaucoup de triangle.
Aussi le principal probleme que j'ai c'est que le polygon peut avoir toutes les forme possible et inimaginable, bien que si ca pose encore un probleme le faite que plusieurs partie du polygon se coupent puisse etre supprimé.
A partir de la ce serai bien si quelqu'un connaissait quelque chose qui puisse me permetre de creer mes triangles, si y'a deja quelquechose qui existe ou si quelqu'un connait une autre methode.
Merci.

cs_bibi_vb · Accepted Answer

Bonsoir,
            Je pense que la réponse a la question posée se trouve dans les mots systeme de Veronoî et triangulation de Delaunay.
Je sais que le message a deux ans d'age.... mais si cela peut etre utile a qq un qui en cherchant passe par là .

Bonne prog.

jmfmarques · Answer

Je ne comprends pas.
Tu dis, par exemple : "le but étant d'en trouver le moins possible" et je suppose que tu parles du nombre de triangles nécessaires pour couvrir toute la surgace de ton polygone. Or, pour moi, ce nombre ne saurait dépendre d'un découpage plus adroit que l'autre en triangles, le nombre de triangles étant strictement égal à celui du nombre des côtés - 2.
A moins que tu ne nous dises pas tout et que tu fasses un découpage "mixte" (pas seulement des triangles)....

S'il s'agit véritablement d'un découpage en seuls triangles, il te suffit de tracer des segments joignant toujours la même arête à chacune de toutes les autres, hormises les 2 arêtes adjacentes.S'il existe des arêtes "rentrantes", tu dois en choiisir une comme point de départ. Si toutes les arêtes sont sortantes, par contre, aucun problème.


Reste maintenant un point essentiel dont tu ne nous as pas parlé.


Où enmagasines-tu les coordonnées de tes arêtes et comment les récupères-tu ?

Neron2005 · Answer

Oui je me suis peut etre mal fais comprendre, en faite, j'envisage de pouvoir creer des polygones ou, si l'on opere de la sorte, certaines liaisons sortiraient de la figure et je veut une methode qui marche dans tous les cas,
et les coordonné sont enregistre dans un tableau tout simplement.

jmfmarques · Answer

Il est vrai que si, à la fois :
-tu as plus d'une arrête "rentrante"
- que les coordonnées des autres arrêtes "rentrantes" sont "en débordement" par rapport à l'arrête choisie comme départ, tu vas te trouver confronté inévitablement à des croisements.
Il est malheureusemnt également vrai que, dans un tel cas, tu ne pourrais t'en sortir que par application de l'analytique pour décomposer dans un premier temps ton polygone en plusieurs sous-polygones tels qu'aucun d'entre eux ne répêtrait le problème.
Ce serait une entreprise quasi démentielle si le nombre des "débordements" était élevé.

Je me vois mal aller dans ce sens et ne puis alors que te souhaiter courage et opiniatreté ...

jmfmarques · Answer

Question malgré tout : dans quel but, exactement ? (un calcul de surface ?)

jmfmarques · Answer

Si tu choisis malgré tout la voir analytique :
voilà ce qu'il convient de mettre en oeuvre :
- partir de l'une quelconque des arêtes et la relier à l'arête la plus proche qui ne serait pas celle atteinte par un chemin coincidant avec l'un des côtés du polygone
- de cette nouvelle arêté, recommencer le même mécanisme


et ainsi de suite jisqu'à ce que tous les segments ainsi tracés l'aient été deux fois chacun


J'unsiste : aucun segment ainsi tracés ne devra correspondre à un côté éxustan du polygone

Si tu fais celà : ton polygine sera nécessairement découpés en un nombre minimum de rectangle.

La chose (le découpage) est aisé (application du théorème de pythagore pour calculer les distances entre l'arête où l'on est et toutes les autres arêtes pour trouver la plus proche, mais refus d''un chemin qui serait déjà un côté du polygine)

Une autre affaire sera de mémoriser ainsi tous les segments ainsi rajoutés et d'en déduire les triangles qu'ils composent...La chose est parfaitement réalisable mais j'en ai mal au crâne rien que d'y penser...(ce sera pire qu'un jeu de patience traditionnel...).

jmfmarques · Answer

Ouf...
Plein de fautes de frappe !
Je corrige la proncipale 

Si tu fais celà : ton polygine sera nécessairement découpé en un nombre minimum de triangles

je te laisse corriger les autres (facile)

Neron2005 · Answer

je suis pas sur de bien comprendre ce que tu dit : 
- donc je doit choisir n'importe quelle arrete de mon polygone (dison la premiere)
- ensuite la relier a l'arrete la plus proche (jusque la ca a l'aire d'aller)
- mais ensuite, de quel arrete tu me parle, de celle d'arriver ou des deux que je vien de creer a travers le polygone,
c'est pas tres clair pour moi pour la suite aussi si tu pouvais reexpliquer ce serai simpa

jmfmarques · Answer

C'est pourtant simple : il te faut :
1) partir d'une arête
2) aller vers la plus prôche hors celle reliant cette dernière à la précédente par un côté existant du polygone
3) de cette dernière arête : aller vers la plus proche (toujours selon le même princope)
etc...
jusqu'à avoir dessiné 2 fois tous ces segments intermédiaires (seul moyen de s'assurer qu'il ne reste pas de sous-polygones de plus de 3 côtés)
Le mieux est sans aucun doute que tu prennes une feuille de papier et 2 feutres de couleur (une couleur pour le polygone et l'autre pour tes segments "internes"), que tu suives la méthode... et que tu constates le résultat ...

Decomposition Geometrique de polygon

9 réponses

Votre réponse

Discussions similaires