Discussion :

[BioKore]

Bonjour à tous,

Dans le cadre d'un petit algorithme de mon cru, il m'est nécessaire de trier des points 2D (comprendre vertices, représentés par des vecteurs de dim 2), de sorte à pouvoir tracer, dans l'ordre trigonométrique, un polygone non croisé, convexe ou concave.
En gros, je balance un tas de points non triés et l'algo me sort la solution (ou l'une des possibles solutions) permettant de tracer une forme (2D), soit un std::vector trié des points donnés.

Techniquement, je devrais être en mesure de réaliser un tel algo, mais après avoir passé un après-midi sur le sujet, je flanche. Une petite idée ou un indice de quelque-chose qui pourrait m'aider dans ma démarche ?


Merci d'avance

[jo_link_noir]

Je n'ai pas testé, mais je dirais qu'on peut définir le centre du nuage de point et avec faire un trie sur le fait qu'un point à gauche d'un autre (en se positionnant vers le centre) est toujours plus grand.

[BioKore]

Bonjour, et merci pour ce retour.

J'ai effectivement pensé à cette idée ; néanmoins, cette méthode à le défaut de devoir tester chaque point par rapport à tous les autres et non pas uniquement aux plus proches. La technique faisant intervenir le produit vectoriel, j'imagine qu'il existe une solution moins gourmande (même si ce n'est pas le premier objet de la question). Il me faudrait réaliser un dessin pour imager la chose mais techniquement, l'algo proposé ne garanti pas non plus que le polygone ainsi créé ne présente pas de croisements.

Autant le préciser, j’admets, bien entendu, que le nuage de points donné autorise au moins une solution à la réalisation d'un polygone non croisé faisant intervenir l'ensemble des sommets.

[foetus]

À vue de nez , il faut reprendre "je-ne-sais-plus-quel-algo" glouton pour construire l'enveloppe convexe (peut-être concave ) d'un nuage de points.

En gros, tu sélectionnes un point initial. Et ensuite l'algo prend un autre point, teste certains critères (1) et si c'est bon trace une arête entre ce point choisi et le point précédent.
Sinon, par exemple dans l'algo de triangulation de Delaunay (<- lien wiki en français) on sait comment refaire le maillage local.

Pour toi, les critères (1) que je vois

• Est-ce que cette nouvelle arête en coupe 1 autre ? (test d'intersection) - si oui, tu vas avoir un truc style A-B-C-D et c'est A-B et C-D qui se coupent. Tu refais A-D-B-C ou A-D-C-B ou ... en fonction de la position des points
• Est-ce que cette nouvelle arête entre A et B a une distance similaire (à un delta près) à 2 arêtes qui relient A et B via un 3ième point C ? Si c'est la cas, il faut déterminer si cette nouvelle arête est à l'intérieur (on supprime cette arête et on retire/ réserve/ ... peut-être ce nouveau point) ou à l'extérieur de la forme (on supprime ces 2 arêtes et on retire/ réserve/ ... peut-être le point C)

[tbc92]

Tu ajoutes un point A, proche du centre de tous les points.
Pour chacun de tes points M(i), tu calcules l'angle entre l'horizontale et l'axe AM(i) : un angle entre 0 et 360° donc.
Et tu tries tous tes points selon cet angle.
Et c'est fini, les points dans cet ordre forment un contour conforme à ta demande.

[Flodelarab]

Bonjour

J'aime beaucoup ce dernier algorithme .
D'autant plus que l'argument d'un nombre complexe est donnée par la formule : arg z = 2 * arctan( (Re(x) + |z| ) / Im(z) ) si z n'est pas un réel négatif ou nul (arg z = π, sinon). Le résultat est entre -π et π.
Donc ici, l'angle du point est :


ou π si y=0 et x ≤ 0

NB1 : L'origine ne doit pas être présente deux fois dans ta liste, sinon, c'est un polygone croisé.
NB2 : Si des points ont le même angle, il faut les mettre dans l'ordre du module (distance de l'origine aux points), croissant ou décroissant..

[BioKore]

Bonjour, et merci pour les retours.

Effectivement, j'ai déjà implémenté quelque-chose de basé sur l'angle ET la longueur des vecteurs. Cependant, ce qui me chagrine, c'est comment refermer le polygone ? Cependant, je viens d'y penser, je n'étais pas vraiment placé au centre du nuage de points... Maintenant que je trace un dessin rapidement sur le papier avec une forme quelconque, je me dis que ça devrais marcher....

Merci pour le tuyau qui me manquait ! Je teste ça cette fin de semaine et je vous dit ce qu'il en est.
Si d'autres ont d'autres idées, je suis preneur. C'est toujours bien d'avoir plusieurs cordes à son arc.

Merci encore !

[BioKore]

Bon, j'ai lancé un ou deux tests concluants sur des formes simples.
Demain, je tenterais de faire ça sur un plus grands nombre de formes, mais je pense que le résultat sera positif.

Pour info, j'ai réalisé ce bout de code de manière à essayer un "test de collision". En gros, savoir si un point est situé à l'intérieur ou à l'extérieur d'une surface donnée. Bien entendu, je sais qu'il existe d'autres algos pour ça mais je voulais valider la chose. On calcule l'aire de la surface initiale, puis l'aire de la surface initiale à laquelle on a ajouté le sommet à tester. Si l'aire est supérieure, alors le point est à l'extérieur de la forme, si l'aire est inférieure, alors le points est situé dans la forme.

L'avantage que je vois à cette méthode par rapport à d'autres c'est que ce dernier peut traiter de formes concaves comme convexes.
Inconvénient : cet algo est sûrement plus "lourd" en terme de ressources nécessaires ; en tout cas, c'est l'idée que je m'en fait là.
Évolution potentielle pour traiter des formes 3D par calcul des volumes.

Qu'en pensez-vous ?

---

Edit : Non, en fait, cela ne peut fonctionner tel quel pour déterminer si un point est ou non à l'intérieur d'une forme. Ceci est limité aux formes convexes.
Néanmoins, l'algorithme de tri / génération fonctionne tout de même et réponds à la question initiale... Ce dont j'ai besoin maintenant c'est de savoir comment intégrer un sommet à un polygone existant sans que le nouveau polygone soit croisé. Je vais réfléchir à nouveau au sujet...