Discussion :

[Earthwormjim]

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

[millie]

Le cercle creusé à gauche est-il un vrai cercle creux ?

Car si c'est le cas, ce n'est pas possible de le découper en un nombre fini de partie convexe.

[Earthwormjim]

Oui, c'est un vrai polygone circulaire composé d'une vingtaine de points ( même nombre de points pour le trou au milieu), du coup dans mon exemple, il est possible de le découper en polygones convexes en reliants les points qui se font face.

Pour le cas des cercles pleins (cf en bas à droite), je ne souhaite pas les décomposer, je veux les garder tels quels.

pour info, j'ai besoin de ceci pour améliorer un script que j'ai fais pour lightwave, ici : http://earthwormjim.free.fr/lscript/...ble/index.html

ce script permet de cloner des bouts de géométries sur les polygones d'un autre objets, en conformant les clones à chaque polygone servant de support.

Comme je vois mal comment faire une déformation régulière dans autre chose qu'un triangle ou un quadrangle, je cherche un moyen de diviser un polygone concave complexe en qq chose de plus exploitable.
Pour le cas des cercles ou autres polygones convexes proches, je vais les garder tels quels, et placer mes clones dans le cercle ou rectangle inscrit le plus grand possible, mais je verrais ça plus tard...

Bien entendu, je cherche aussi à avoir le plus possible de quadrangles (si possible proche de rectangles et non de trapèze) et le moins possible de triangles

[Earthwormjim]

Voici où j'en suis 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 ?

[j.p.mignot]

Comme l'a dit millie, si la frontière contient des éléments courbes ( cercles, ellipse, ... ) cela est impossible < que se soit des ouvertures centrales ou des limites extérieures > dans l'absolu mais demande une approximation des courbes par une série se segments.
Ceci étant dit, La solution est non unique!
Aller voir du côté des mailleurs 2D pour éléments finis. Certains algorithmes sont publiques. D'autres sont disponibles gratuitement sous forme d'application.
Il n'en reste pas moins que le nombre de triangles / rectangle sera élevé et ne découpera pas la surface comme votre dessin le laisse prévoir.

[Earthwormjim]

Comme l'a dit millie, si la frontière contient des éléments courbes ( cercles, ellipse, ... ) cela est impossible < que se soit des ouvertures centrales ou des limites extérieures > dans l'absolu mais demande une approximation des courbes par une série se segments.

Oui je le sais, et comme je l'ai précisé un peu plus haut, je travaille uniquement avec des polygones composés de segments, aucune courbe n'est utilisée nulle part.

Ceci étant dit, La solution est non unique!

ce n'est pas un problème, pour le moment, je cherche une solution valide, je chercherais plus tard un moyen d'orienter le résultat.

Il n'en reste pas moins que le nombre de triangles / rectangle sera élevé et ne découpera pas la surface comme votre dessin le laisse prévoir.

Le fait qu le nombre de polygones au final soit élevé n'est pas génant, et il est tout à fait possible d'obtenir le résultat que j'ai dessiné, j'ai déjà vu un programme le faire mais l'auteur n'a pas été assez sympa pour me filer un coup main ou pour m'aiguiller sur une quelconque piste.
Le seul doute qui me reste concerne le cercle percé.

Je me mets de ce pas à la recherche d'infos sur les mailleurs 2D

merci

[larnicebafteur]

Il faut aller chercher du côté des méthodes de maillage, qu'on utilise beaucoup dans la méthode des élements finis pour discretiser une surface ou un volume.

Attention, ces méthodes sont lourdes et longues à coder, et elles sont trés nombreuses, mais on peut en trouver des libres directement utilisables.

En cherchant un peu dans un moteur de recherche :
maillage, mailleurs, triangulation de delaunay ...

[Earthwormjim]

bon bah les mailleurs 2D ça m'aide pas du tout en fait... d'autres idées ?

[Graffito]

Bonjour,

La méthode indiquée (en 6 étapes) peut être simplifiée si les polygones sont tous orientés dans le même sens (exemple : sens des aiguilles d'une montre).

Si c'est le cas, il est facile de déterminer si l'angle entre un segment sommetX-1:sommetX et le segment suivant sommetX:sommetX+1 est entrant ou sortant.
Si l'angle est entrant, on recherchera pour continuer le traitement du polygone en cours le prochain point X+N tel que l'angle entre sommetX-1->sommetX et sommetX->sommetX+N soit sortant. Doù, la création d'un nouveau polygone composé de la suite des points X,X+1,...X+N à traiter ultérieurement (ou directement avec un appel récursif).

Déterminer le sens de rotation est un problème qui m'a longtemps gonflé. Je viens récement de trouver une solution qui fonctionne plutôt bien (mais on peut trouver des contre-exemple théoriques) : on définit ainsi des points PX et P'X (si on regarde les polygones composés de la suite des points PX et P'X, on obtient des "envellopes" interne et externe du polygone) :
- vecteur(SommetX->PX )=VecteurNormé(rotation(vecteur(sommetX-1->sommetX),+90°)),
- vecteur(SommetX->PX')=VecteurNormé(rotation(vecteur(sommetX-1->sommetX),-90°)).
On fait la somme S et S' des distances D et D' de Px et P'X à la surface du polygone (*).
(Si S-S'>0, les points Px sont vers l'extérieur et les points P'X vers l'intérieur).
Suivant le sens de rotation choisi et le signe de S-S', on inversera ou non les points du polygone pour que tous les polygones soient dans le bon sens.

(*) pour un meilleur résultat, pondérer les distances D et D' par la somme des distances de sommetX-1:sommetX et sommetX:sommetX+1.

Noter que la longueur du "vecteur normé" (1 en théorie) est à ajuster à une longueur constante dont l'ordre de grandeur correspond à la taille d'une fraction de coté moyen.

[Earthwormjim]

ok, merci beaucoup pour cette piste, je vais tester ça aussi