ordonner un ensemble de points de façon circulaire
Bonjour à tous,
Voici mon problème. J'ai une matrice A (n lignes, 3 colonnes) contenant les 3 coordonnées d'un ensemble de n points. L'ensemble de ces points décrit un contour dans l'espace.
Pour l'instant, la matrice A n'est pas ordonnée (ce qui signifie que le point n°1 (ligne 1) n'est pas nécessairement le voisin du point 2 (ligne 2)).
Je souhaiterais ordonner cette matrice, ç-à-d permuter les lignes, de manière à parcourir le contour de façon "cirulaire".
Dans un premier temps, ma stratégie était la suivante:
- calculer un centre (moyenne arithmétique des cordonnées de l'ensemble des n points),
- calculer les vecteurs reliant le centre à chacun des points du contour,
- calculer (cart2pol) les coordonnées polaires de chaque point par rapport au centre -> theta (n lignes, 1 colonnes),
- ordonner ce vecteur theta (avec la fonction sort) en stockant les permutations effectuées,
- re-ordonner la matrice A de départ avec les permutations obtenues au point précédent.
Malheureusement, si pour un contour convexe, cette méthode convient parfaitement, elle n'est pas toujours valable dans le cas d'un contour concave...
Je suis donc à la recherche d'un algorithme (ou d'une bonne idée) permettant de faire cela pour des formes convexes et concaves.
Merci d’avance pour votre aide.
