Tri des points du polygone

Question

J'ai un polygone convexe ABCDE ... (il peut avoir n'importe quel nombre de points). J'ai besoin de trier tous ses vertex pour qu'aucun des bords ne se croisent.
exemple:

A _____ B 
    \ /
    \/
    X 
/\ 
    /___\ 
C  D 

Ce polygone pour ABCD a des bords entrecroisés. cependant dans l'ordre ABDC:

A _____ B 
    | | 
    | | 
    | | 
    | | 
    |___| 
C  D 

Aucun des bords ne se croisent donc ABDC est la sortie attendue.

Comment est-ce que je peux faire ceci?

Answer 1

En supposant que vos points sont sur la coque convexe de polygone, vous pouvez utiliser les éléments suivants:

1. Choisissez les deux points extrêmes avec la valeur min et max X, (appelez-X _min et X _max) et tracer la ligne entre eux. Dans le cas où vous avez plusieurs points avec la même valeur X aux extrêmes, sélectionnez X _min avec la valeur Y minimale et X _max avec la valeur Y maximale. Diviser la liste de points en deux sous-listes où tous les points sous la ligne X _min et X _max sont dans une liste et tous ceux au-dessus de cette ligne sont dans un autre. Inclure X _min dans la première liste et X _max dans la seconde.
2. Trier la première liste dans l'ordre croissant de la valeur X. Si vous avez plusieurs points avec la même valeur X, triez-les en Y croissant. Cela ne devrait arriver que pour les points ayant le même composant X que X _max puisque le polygone est convexe.
3. Trier la deuxième liste dans l'ordre décroissant de la valeur X. Encore une fois, trier en Y décroissant en cas de points multiples avec la même valeur X (ce qui ne devrait arriver que pour les points X) _min
4. Ajouter les deux listes ensemble (peu importe quelle est la première .)

Answer 2

Sélectionnez deux points sur le polygone. le point médian de la ligne sera contenu dans ce polygone. Que ce point soit M.

Ensuite, triez les points en fonction de l'angle basé sur M (le long de l'axe X), en dégageant la dégénérescence en fonction de la distance de M. Itérer dans cet ordre assure que deux arêtes ne se croisent pas.