Discussion :

[Djakisback]

Salut,
je suis confronté à un problème de tri pour tracer un polygone. J'ai tenté quelques trucs mais sans succès.
J'ai une liste de points 2d (x,y), constamment en mouvement car liés à une simulation physique.
A chaque cycle je récupère les coordonnées des points et je voudrais tracer un polygone n'ayant aucun segment qui se croisent.
Si je réduis l'exemple au minimum avec 4 points ça donne ça :



et voici ce que j'essaie d'avoir :



J'essaie de trier les points en fonctions de leurs coordonnées pour pouvoir tracer un polygone dans le sens anti-horaire (et donc sans aucune intersection de segments).
Sur 4 points c'est simple mais j'essaie de trouver un algo de tri généralisable à n points :



L'idée c'est d'ailleurs de tracer le contour, donc en fait les coordonnées des points intérieurs ne me sont pas vraiment utiles. (En fait, je m'aperçois en rédigeant que ce que je cherche c'est un algo de bounding box ou plutôt de "forme englobante", "bounding shape ?")

Il faudrait que je récupère les min x, max x, min y, max y mais je ne vois pas comment faire le croisement pour la sélection des points pertinents. Toute idée est la bienvenue ^_^

Voilà, un grand merci à ceux qui me liront et pour l'aide future

[pseudocode]

L'idée c'est d'ailleurs de tracer le contour, donc en fait les coordonnées des points intérieurs ne me sont pas vraiment utiles. (En fait, je m'aperçois en rédigeant que ce que je cherche c'est un algo de bounding box ou plutôt de "forme englobante", "bounding shape ?")

Le problème avec les polygones concaves, c'est que connaitre la liste des sommets ne suffit pas a définir un seul polygone (meme non croisé).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
exemple avec 5 points:
 
*     *      *-----*     *     *
             |    /      | \ / |
   *         |  *        |  *  |   ...
             |    \      |     |
*     *      *-----*     *-----*

[Djakisback]

Ah oui merci beaucoup je n'avais pas vu cela. Je continue mes recherches (enfin, en fait, faut déjà que j'essaie de définir ce que je veux faire ).

[Djakisback]

En fait pour être plus précis, mon but était de simuler un fluide via des sphères Bullet (moteur physique). L'idée est donc d'obtenir le contour d'un groupe de sphères, puis de tracer un polygone rempli. Mais c'est vrai qu'avec cette remarque sur les polygones, je ne vois plus trop comment choisir mes points.

[Jean Dumoncel]

Bonjour,

si tu cherches la forme convexe qui englobe l'ensemble de tes points, regarde du cote des algorithmes d'enveloppe convex (convex Hull).

[Djakisback]

Merci beaucoup, oui c'est effectivement cela que je recherche, je vais voir ça de ce pas (ça va mieux quand on pose les mots ^^)