¿Ordenar los vértices de polígonos de CONCAVE en (contra) en el sentido de las agujas del reloj?

Tengo un conjunto de vértices desordenados que pueden formar un polígono cóncavo. Ahora deseo ordenarlos en sentido horario o antihorario.

Una respuesta aquí sugiere los siguientes pasos:

  • Encuentra el centro poligonal
  • Calcular angularjs
  • Ordenar puntos por ángulo

Obviamente, esto es solo para polígonos convexos y fallará cuando los puntos formen uno cóncavo.

¿Cómo puedo hacer esto a un cóncavo?

Estoy usando Python, pero doy la bienvenida a todas las respuestas genéricas.

En general, su problema parece mal definido. Por ejemplo, dado el siguiente conjunto de vértices:

Cuatro puntos en el plano en una disposición no convexa.

¿Cuál de estos polígonos no convexos consideraría la forma “correcta” de conectarlos?

Polígono ABCDPolígono ACDBPolígono ACBD

Ahora, obviamente, hay varios criterios posibles que puede utilizar para elegir entre diferentes órdenes posibles. Por ejemplo, es posible que desee elegir el orden que minimice la longitud total de los bordes , que debería producir resultados bastante “razonables” si los puntos, de hecho, se encuentran bastante cerca entre sí en el límite de un polígono simple:

Polígono simple no convexo con muchos vértices.

Desafortunadamente, para un conjunto general de puntos, encontrar el orden que minimiza la longitud total del borde resulta ser un problema conocido de NP-completo . Dicho esto, hay muchos algoritmos heurísticos que generalmente pueden encontrar una solución casi óptima rápidamente, incluso si no siempre pueden garantizar que la solución que encuentren sea la mínima.