Ordenando los puntos del polígono

Question

Tengo un polígono convexo ABCDE ... (puede tener cualquier cantidad de puntos). Necesito ordenar todos sus vértices para que ninguno de los bordes se crucen.
ejemplo: bordes

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

ese polígono con el fin ABCD ha de intersección. sin embargo, en orden ABDC:

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

Ninguno de los bordes se cruza, por lo que ABDC es la salida esperada.

¿Cómo puedo hacer esto?

Answer 1

Suponiendo que sus puntos están todos en la envolvente convexa de su polígono, se puede usar la siguiente:

1. escoger los dos puntos extremos con el mínimo y el valor máximo de X, (llamarlos X _min y X _max) y trazar la línea entre ellos. En el caso de que tenga puntos múltiples con el mismo valor de X en los extremos, elija X _min con el valor Y mínimo y X _max con el valor Y máximo.
2. Dividir la lista de puntos en dos listas sub donde todos los puntos por debajo de la línea que conecta X _min y X _max están en una lista y todos aquellos por encima de la línea son en otro. Incluya X _min en la primera lista y X _max en la segunda.
3. Ordene la primera lista en orden ascendente del valor X. Si tiene varios puntos con el mismo valor de X, ordénelos en valor Y ascendente. Esto solo debería ocurrir para puntos con el mismo componente X que X _max ya que el polígono es convexo.
4. Ordene la segunda lista en orden descendente de valor X. Nuevamente, clasifique el valor Y descendiente en el caso de puntos múltiples con el mismo valor X (que solo debería ocurrir para los puntos con el componente X X _min.
5. Adjunte las dos listas (no importa cuál sea el primero .)

Answer 2

elija dos puntos en el polígono. el punto medio de la línea estará contenido dentro de ese polígono. Permita que ese punto sea M.

Luego, ordene los puntos según el ángulo basado en M (a lo largo del eje X), rompiendo la degeneración en función de la distancia desde M. Iterar en ese orden asegura que no se crucen dos bordes.