Bonjour à tous !
Je suis à la recherche d'une solution sur un problème épineux : je souhaite décomposer un polygone concave à N cotés en une série de polygones convexes "simple" comme des quadrangles (rectangles ou trapèzes) des triangles ou des cercles...
Voici un exemple de ce que souhaiterais obtenir :
Merci d'avance pour votre aide
hi hi, je ne pourrais malheureusement pas t'aider mais j'aimerai vraiment satisfaire ma curiosité : à quoi cela sert-il concrètement ?
Merci,
Sami
Je suis en train d'améliorer un script que j'ai fais pour un logiciel 3D.
Ce script permet de dupliquer des objets 3D sur chaque polygones d'un autre objet, en conformant chaque copie à la forme du polygone servant de support.
Pour le moment mon script ne gère que les quadrangles et les triangles, car il est beaucoup plus difficile de faire des interpolations sur d'autres polygones...
C'est pourquoi je cherche un moyen de convertir automatiquement n'importe quel type de polygone en quadrangles ou en triangles, le cas des cercles pouvant être géré à part je pense.
pour info, mon script se trouve ici : http://earthwormjim.free.fr/lscript/...ble/index.html
Je cherche aussi une méthode pour placer aléatoirement un polygone de forme quelconque, à l'intérieur d'un autre polygone de forme quelconque et pouvant aussi avoir des trous.
Mais bon, ça sera pour plus tard
Je précise que pour tout ça je bosse presque entièrement en 2D pour simplifier les calculs.
Je n'ai pas forcément besoin d'avoir tout un exposé mathématique, je suis plutot à la recherche d'une marche à suivre, ce découpage se faisant necéssairement en plusieurs étapes pour couvrir tous les cas.
tu peux peut-être traiter ce problème récursivement. Cela revient alors à trouver une diagonale incluse dans l'intérieur de ton polygone. J'ai l'impression qu'il en existe toujours une ayant comme sommet un sommet arbitraire du polygone (mais je ne sais pas le montrer). On doit pouvoir la trouver en triant les sommets restants selon l'angle que forme la diagonale avec une direction fixée. Il faut identifer un segment de la suite des sommets du polygone... (à compléter)
J'aurais peut etre du envoyer une autre image, sur celle-ci effectivement, pas mal de sommets se trouvent alignés, mais ça ne sera pas forcément toujours le cas
Je bosse déjà sur deux fonctions récursives pour dépioter tout ça : un pour relier directement tous les sommets qui peuvent l'être et une autre pour ajouter des coupure entre un sommet et un milieu segment, ça marche pas pour tous les cas, mais c'est un bon début je pense.
Je posterais bientôt une description de tout ça, c'est pas encore tout à fait au point...
Tu pourrais découper ton terrain en triangle. Cette méthode est simple et un algorithme de triangulation (Delaunay) est facilement implementable. Pour autant que je sache c'est comme ça que c'est réalisé dans certain jeu video pour seletionner uniquement les parties de terrain visible à partir d'un point, ce qui empeche l'affichage des parties cachés..
Ouep, mais non...
Je veux avoir le plus possible de quadrangles qui soient le plus proche possible de rectangles ou de carrés, donc exit les triangles... moins il seront nombreux et mieux ce sera.
Merci quand même pour l'idée
Peut être que tu peux reflechir à une strategie pour fusionner les triangles de maniere à obtenir des polygones.
Une autre approche serait une partition de Voronoi qui a la bonne propriété de fournir des polygones convexes. Mais la il faut trouver une maniere de définir les points à partir desquelles on calcule cette partition.
J'ai déjà testé la triangulation, le problème c'est que c'est totalement imprévisible et les triangles résultants ne permettent pas toujours de les refusionner deux par deux pour retrouver des quadrangles corrects, du moins, pour l'utilisation que je veux en faire apres...
Moi je partirai sur une solution consistant à :
- déterminer les équations de toutes les droites
- calculer les points d'intersection pour toutes les droites deux à deux
- (incomplet) à "remplir" les segments entre les deux points à condition que ce segment n'est pas coupé par un autre éventuel prolongement
La condition 3 n'est pas complète, il faut trouver une condition qui permette de déterminer dans quel cas exactement "remplir" entre les points d'intersection.
hum ouep, je fais déjà à peu près un truc dans ce style
pour le moment, je commence par relier tous les points qui peuvent l'être :
1) je fais une boucle sur tous les segments
2) dans cette boucle je fais une autre boucle sur tous les points (sauf ceux du segment en cours)
3) je vérifie si le point est dans le prolongement du segement en cours
4) si oui, je vérifie que la liaision entre ce point et l'extrémité du segement ne coupe pas un autre bord et si cette coupure se trouve bien à l'intérieur du polygone
5) si tous les tests sont ok, alors je valide la coupure, j'obtiens donc deux polygones et je lance récursivement la même fonction sur ces deux polygones
Sinon, je passe au point suivant
6) Une fois que je suis passé par tous les points, je continue la boucle sur les bords, etc...
après ça, il me reste déjà beaucoup moins de polygones tordus
ensuite, j'ai un début de fonction qui fait aussi une boucle sur tous les bords en les considérant comme des droites infinies, là je teste la coupure avec tous les autres bords, si j'en trouve une je m'assure que c'est bien le bords plus proche qui est coupé et que la coupure reste bien dans le polygone
si c'est le cas, je coupe, et je continue récursivement sur les deux polygones obtenus...
l'idée est là, mais j'ai encore des erreurs par moment sur cette fonction.
vous en pensez quoi ?
Déjà à bien y mieux regarder je trouve qu'il y a plusieurs facons de découper la fiirre déjà faudrait trouver une expression de la loi de découpage qui te donne qu'un seu découpage sinon informatiquement tu rsique de ne pas pouvoir y arriver.
je ne pense pas que ceci soit un réel problème :
Il y a bien sur grand nombre de possibilités pour découper le polygone, mais j'essaye d'aller au plus simple et/ou au plus rapide
pour le moment, je garde le premier résultat valide pour chaque opération, même si visuellement, ce n'est pas forcément le plus avantageux, je ferais cette optimisation par la suite.
par exemple, lorsque je fais mes découpes au lieu de m'arreter à la première coupure valide, je pourrais stocker le résultat et continuer la boucle jusqu'à la fin, et seulement là, conserver le résultat donnant la coupure la plus courte, (ou s'il y en a plusieurs de longueurs égales, en choisir une aléatoirement parmi celles-ci)
Ainsi, j'orienterais le résultat afin de limiter le nombre de polygones rectangulaires de formes allongées, au détriment de la vitesse bien sur...
enfin, je pense...
