Bonjour

J'ai un problème chiant là

En fait je génère des points aléatoirement. Et à partir de ces points générés, je veux obtenir un polygone.

Le truc c'est que comme les points sont générés aléatoirement, des fois j'obtiens des polygones complexes : http://puu.sh/MZAK

mais moi, je veux que des polygones simple comme ça http://puu.sh/MZB9

je veux donc pouvoir convertir mon polygone complexe en polygone simple mais je suis trop mauvais en maths pour y arriver tout seul

Si je refais un polygone en triant les points par X ou par Y ça marche pas.

J'me suis dit qu'il faut les ordonner de manière à ce qu'ils soient genre dans le sens des aiguilles d'une montre mais ça a l'air chiant à faire alors avant de m'y mettre je vous demande si y'a pas plus simple

Y'a pas un théorème magique qui fait ça vite et bien ?

déja, tu considères le point le plus haut.

tu trace une ligne entre lui et le point à sa gauche qui forme l'angle le plus petit avec une ligne horizontale ; ce point devient le point courant.

et tu répètes le processus.

http://sournoishack.com/uploads/1679892543Sans_titre.PNG

et tu noteras que certains points seront exclus... ça arrive souvent, quand on change des nuages de points en formes convexes.

pas sûr que cet algorithme-là soit inscrit dans les bouquins, mais il pourrait fonctionner. doute:

Ah ouais, pas bête, j'avais pas pensé à utiliser l'angle

Merci pour ta réponse bien détaillée et super rapide, je m'y met

amuse-toi bien avec les produits vectoriels

Cherche Graham scan sur Google c'est ce que tu veux.

PS : Ca veut rien dire "polygone complexe", en l'occurrence on parle plutot de "polygone concave" si j'ai bien compris ton probleme.

Plutôt de polygones croisés. ;)

Merci, grâce au nom graham scan j'ai pu reprendre du code déjà existant et l'adapter super rapidement et ça marche nickel

J'ai dit polygone complexe à cause de ça http://www.mathsisfun.com/geometry/polygons.html

Ah je vois, au temps pour moi !

Et de facon generale ce que tu cherches est un algorithme de detection d'envelope convexe. Il ya plein d'algo pour faire ca en fonction des cas d'utilisation.

Il me semble que l'algo de caelacanthe est ultra-classique et archi-connu

bin moi je connaissais pas

oui, c'est un des algos classiques. Il y a tellement d'algo du genre que c'est difficile de se rappeller de leur noms.

en même temps, c'est limite la première manière de faire qui vient à l'esprit pour résoudre ce problème.

ouais bon je suis un gros con on a compris

Nan mais justement, on essaye de t'expliquer que t'es pire que ça.

Heu, noraj

Je voulais juste dire que cet algo va se retrouver dans pas mal de bouquins, notamment d'infographie. Pour répondre à caelacanthe qui se demandait si cet algo pouvait se trouver dans un bouquin ou non.

Je n'ai nullement sous-entendu que qui que ce soit était un gros c*n.

Non mais c'était pas sérieux hein, y'a pas de soucis