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 ^^)

[Djakisback]

J'ai testé une implémentation du Quick Hull algorithm. Le résultat est très sympa :





mais en fait je m'aperçois que ce qu'il me faudrait c'est la forme concave englobante et non convexe. On en revient au problème du choix des points pour le tracé du polygone concave. Sur les images, les sphères représentent les points et le bleu la zone censée représentée le liquide. L'idéal serait que le bleu matche la crête du groupe de points.

Je continue mes recherches avec "Concave Hull"

[souviron34]

je suis en train de pondre (si j'ai du temps, en ce moment assez pris) un article sur ce sujet..

Si tu cherches sur ce forum "polygones concaves" ou "non convexe" tu trouveras l'explication de la méthode..

[Djakisback]

Merci bien je vais chercher cela

[pseudocode]

L'idéal serait que le bleu matche la crête du groupe de points.

Dans ce cas, pas trop de problème. Il suffit de balayer les colonnes (axe x) et de prendre dans chacune le point le plus haut (axe y).

Un petit lissage de la courbe obtenue et ca devrait etre pas mal.

[Graffito]

Dans ce cas, pas trop de problème. Il suffit de balayer les colonnes (axe x) et de prendre dans chacune le point le plus haut (axe y).Un petit lissage de la courbe obtenue et ca devrait etre pas mal.

C'était aussi ma première impression, mais ca ne permet pas de traiter une vague, qui est en train de casser (juste avant de former un "tube" de surf).

Code :

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

1
2
3
4
5
6
7
8
9

                 **
             **     **
          *           *
       *          * * *
     *          *      *
   *            *              ***
*                 *       **       **
                    *****                ******

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é).

Il me semble qu'on peut réduire le nombre de candidats en introduisanr des contraintes supplémentaire du type:
- surface minimum,
- périmètre minimum.

[Djakisback]

Merci, effectivement c'était aussi ma première impression mais c'est un peu plus compliqué que cela.

[nonifier]

Et réaliser une triangulation de l'ensemble des centres de tes sphères ? Genre triangulation de delaunay ?
Tu obtiendrais un polygon concave assez rapidement.
Le problème c'est que tes sphères ne forment pas d'ensemble connexe. Il faudrait recalculer la triangulation à chaque fois.

C'est juste une idée comme ça....

[Jean Dumoncel]

Et réaliser une triangulation de l'ensemble des centres de tes sphères ? Genre triangulation de delaunay ?
Tu obtiendrais un polygon concave assez rapidement.

Si tu calcules ta triangulation juste sur un set de points, tu obtiendras l'enveloppe convexe et non un polygone concave.

[souviron34]

non, ça peut marcher, sauf que tu te tapes tout un tas de calculs pour lesquels tu as des cas particuliers (donnat lieu à bugs) de la triangulation : points alignés en particulier..

Et pour l'avoir tenté, je peux t'affirmer que les bugs (celui-là plus le calcul du cercle circonscrit dans ce genre de cas) donne lieu à de jolis ratés...


On en revient donc au problème de 'l'élimination"...

Sauf si l'on peut affirmer avoir une certaine "résolution", auquel cas les algos de contouring peuvent marcher...

[Djakisback]

Je me repenche un peu sur ce problème après une petite pause. Merci pour les idées et remarques.

Finalement je m'aperçois que mon souci de base c'est pas encore l'algo pour la forme concave (bien que ça doit être bien chaud ^^) mais c'est que je n'arrive pas à définir sur quels critères tracer la forme englobante, donc par où commencer.

Etant donné que j'utilise des cercles et non des points j'ai le sentiment qu'il faudrait que je prenne en compte les diamètres des cercles (et/ou tangentes mais là je crois ça devient un bouffe-ressources).

Pour les contraintes, je me demande s'il ne faudrait pas déjà que je parte sur une forme englobant toutes les sphères en contact (en ajoutant un "facteur d'imprécision" pour pallier à l'approximation des coordonnées)

Si je prends la dernière image que j'ai postée, je pourrais calculer le polygone englobant de toutes les sphères en contact, avec un coefficient à ajouter au diamètre. Ensuite, je pourrais rallier les sphères "virevoltantes" à la sphère la plus proche pour étendre le polygone.

Pas sûr qu'il y ait besoin d'une image mais bon



Est-ce que vous pensez que c'est faisable/viable ? Tout avis sur la question est le bienvenu

(au passage je ne suis pas sûr que ça simplifie l'algo de détection de forme concave, mais je crois que ça fixe la contrainte pour le choix des points)

[Graffito]

Je pense qu'il est plus simple de pratiquer ainsi :
1) ramener les billes à leur centre,
2) trouver une envellope non convexe contenant tous les points
3) "élargir" cette envellope du diamètre des billes.

Pour le 2), voir du coté des algo "MergeHull", "Grayham's scan" ou "Stan Hull".

Pour le 3), on crée l'envellope "élargie brute" composée de segments et d'arcs de cercles, mais qui comportera malheuresement des croisements. Pour obtenir l'envellope "élargie nette", sans croisements, on peut découper les arcs et segments en "mini-segments dont la longueur dépend de la précision souhaitée et ensuite éliminer les mini-segments tels que l'une de leurs extrémités soit à une distance du polygone initial inférieure au rayon des billes.

[Djakisback]

Merci bien, je vais aller voir du côté des algos que tu proposes

Mais si j'ai bien compris, tu proposes de trouver directement une enveloppe non convexe de points (sur l'ensemble des points), mais sur quels critères ? (en fait j'ai l'impression que ça résout pas le problème de base mais j'en saurai plus après recherche)

Plus j'y réfléchis et plus je me dis que la notion de contact/collision de cercles peut être intéressante dans le calcul d'un polygone englobant concave. J'ai l'impression que ça peut être une très bonne contrainte même dans d'autres cas que celui-ci. Et les calculs d'intersections cercle/cercle sont pas très coûteux. (Une fois que t'as ton/tes groupes de points, il y a peut-être moyen de trouver les extrêmes par lignes/colonnes, ca devient de la donnée "tabulaire")

[Graffito]

Pour le 2) - trouver une envellope non convexe - voir du coté des algo "MergeHull", "Grayham's scan" ou "Stan Hull".

Oups, je viens de réaliser que ce sont des algo pour enveloppes convexes

[souviron34]

Oups, je viens de réaliser que ce sont des algo pour enveloppes convexes

Ben vi...

Le problème des polygones concaves est extrêmement complexe..

Certaines techniques existent... Pour l'instant elles sont du domaine de la recherche, et aucune ne fournit un "algo" simple..

C'est pourquoi ce que j'avais suggéré dans les posts référés à ce problème, a au moins l'avantage d'avoir un pricnipe simple..

La plupart des techniques existantes pré-supposent tout un tas de trucs par rapport à la disposition des points, que ce soit discrétisation, matrices, etc..


@Djakisback :

Disons que comme ce sont des billes, oui il peut y avoir une idée à poursuivre , au moins en ce qui concerne le "bas" .. :

chaque couche est décalée de la précédente par une 1/2 sphère.. En prenant donc une résolution en X comme étant le rayon, tu peux explorer comme l'avait dit pseudocode en X, et trouver pour chaque X les sommets en Y du "bloc" de billes..

Cela te donnera la forme du bloc (soit assimilée au point supérieur de la sphère, soit en la raffinant par l'adjonction de 1/2 ou 1/4 sphère (d'ailleurs, dans ton schéma, j'ai un peu de mal à comprendre pourquoi il y a des trous DANS le tas).

Une fois ceci déterminé, tu pourrais ajouter les "extérieurs" (point n'appartenant pas au polygone) au coup par coup...



PS/ cependant, je pense que c'est moins simple que la technique que j'avais exposé dans les posts référencés, même si j'ai amélioré (optimisé) cette technique sur un point ou 2 (qui seront explicités dans l'article)..