Salut, en 2D, j'ai un polygone de n points, toujours convexe, dont les segments sont définis d'un point au suivant (le dernier point avec le premier, donc l'ordre est important). Si je duplique le polygone et le déplace, j'aimerai retrouver la forme englobante convexe des deux polygones, et donc redéfinir les points nécessaires dans l'ordre. Voici un schéma c'est plus simple : http://i.imgbox.com/b2XauzWa.png

En noir le polygone de départ, en rouge le polygone dupliqué et déplace, en vert le résultat final que je souhaite. A ma disposition j'ai une fonction pour vérifier si deux segments se croisent, et si un point arbitraire est dans un polygone, mais je ne m'en sors pas pour autant.

Quel méthodologie utiliseriez-vous ?

Je commencerais par regarder du cote du probleme convex hull pour une solution generique (quickscan, graham scan). Apres, il y a peut etre une solution plus efficace compte tenu de la forme du probleme.

https://en.wikipedia.org/rg/wiki/Convex_hull_algorithms

Merci pour les réponses. Le Graham scan semble idéal dans mon cas (peu de points), et à la fin les points sont automatiquement dans l'ordre qui m'intéresse.

whiteapplex je suis parti sur un truc du genre sans arriver au bout à cause de cas spéciaux, mais je regarderai ta solution en détail.

J'ai fait un projet étudiant en Java il y a plusieurs années de cela sur les enveloppes convexes. Si je me souviens bien, il y avait deux implémentations différentes, une qui se basait sur du Divide And Conquer et l'autre qui se basait sur les méthodes de Monte-Carlo (algorithme qui choisit des points aléatoirement pour construire l'enveloppe). Dans les faits, c'était ce dernier algorithme qui était plus rapide. Voici le code source si ça peut t'aider :

https://www.dropbox.com/ss/zt65rrzinmzqpqv/src.zip?dl=0

tu peux tester l'algo en live via une IHM en Swing.

Juste une précision, au final tu t'en fous d'avoir deux ou n polygones. Faut juste stocker tes nuages de points dans une liste et appliquer l'algo d'enveloppe convexe dessus.

Le Graham scan a bien fonctionné, et il est très simple

RayonSpectral ça aurait pu être intéressant de comparer les différentes méthodes effectivement. Là dans mon cas j'ai rarement plus de 20 points donc pas forcément besoin d'une optimisation. Pour un ordre d'idée, avec 1.000 points ça tourne entre 3 et 9 millisecondes, 10.000 points ça monte entre 350ms et 900ms, je crois que ça correspond à ce qui est indiqué dans le lien de godrik concernant cet algorithme, Time complexity = n log n, donc pas optimal mais ça suffit largement pour 20 points.