Cómo dibujar el polígono más grande de un conjunto de puntos

Entonces, tengo un conjunto de puntos (x, y) y quiero poder dibujar el polígono más grande con estos puntos como vértices. Puedo usar patches.Polygon () en matplotlib, pero esto simplemente dibuja líneas entre los puntos en el orden que les doy. Esto no hace automáticamente lo que quiero. Como ejemplo, si quiero dibujar un cuadrado y ordenar los puntos aumentando x, y luego aumentando y, no obtendré un cuadrado, sino dos triangularjs de conexión. (la línea “cruza sobre”)

Entonces, el problema ahora es encontrar una manera de ordenar la lista de puntos de tal manera que “vaya alrededor del exterior” del polígono cuando se repite esta lista.

¿O hay quizás alguna otra funcionalidad en Matplotlib que pueda hacer esto por mí?

Como se sugiere, una solución simple es calcular los angularjs desde algún punto interior a todos los puntos y ordenarlos.

Así que aquí hay una función numpy para calcular ccworder :

 In []: def ccworder(A): ..: A= A- mean(A, 1)[:, None] ..: return argsort(arctan2(A[1, :], A[0, :])) ..: 

Y simple demostración:

 In []: A Out[]: array([[0, 0, 1, 1], [0, 1, 1, 0]]) In []: ccworder(A) Out[]: array([0, 3, 2, 1]) 

Actualizar:
Puede parecer que este tipo de ordenación puede ser algo tedioso de calcular, pero la numpy puede proporcionar una buena abstracción para hacerlos bastante sencillos.

Advertencia: como Joe y otros han señalado, este ccworder formará el orden correcto en el casco convexo solo si todos los puntos están todos listos en el casco convexo. Es decir, de alguna manera falta el pedido, ya que parece ser el caso del OP, se puede recuperar. Por supuesto, hay otras situaciones en las que ccworder se usa por completo.

No sé Matplotlib, pero lo que necesita / desea es dibujar el casco convexo del conjunto de puntos. Piense en el casco convexo como una cuerda elástica que coloca alrededor del conjunto de puntos. La forma que adquiere la cuerda elástica es el casco convexo. Existen diferentes algoritmos para calcular un casco convexo, así que verifique si Matplotlib admite alguno. Si no, revise estos enlaces para ver un punto de partida sobre cómo implementar uno.

http://en.wikipedia.org/wiki/Convex_hull

http://en.wikipedia.org/wiki/Convex_hull_algorithms

Si ya conoce los puntos del casco , dibujar el polígono conectando esos puntos es bastante fácil de hacer en Matplotlib porque los polígonos se implementan en Matplotlib como rutas . Comenzaría con la clase matplotlib.path .

Si no conoce los puntos del casco, entonces estoy de acuerdo con Elmar: el casco convexo es el algoritmo que desea. He codificado este algoritmo en NumPy y lo he trazado en Matplotlib. Mi código fue tomado de una excelente receta en el Libro de cocina SciPy, aquí . Esta receta incluye una implementación NumPy más el código completo requerido para trazar en Matplotlib el casco convexo alrededor de un conjunto dado de puntos.

Además, Matplotlib incluye un paquete llamado delauney , que, como habrá adivinado, es para tesselating una superficie utilizando triangulación de delaunay. Y como usted sabe, esto se relaciona con el casco convexo a través de la teselación de voronoi, es decir, los límites de cada celda de voronoi se crean a partir de un cálculo de casco convexo.

Desde sus comentarios a otras respuestas, parece que ya obtiene el conjunto de puntos que definen el casco convexo, pero no están ordenados. La forma más fácil de ordenarlos sería tomar un punto dentro del casco convexo como el origen de un nuevo marco de coordenadas. Luego, transforma (probablemente) las coordenadas cartesianas de sus puntos en coordenadas polares, con respecto a este nuevo marco. Si ordena sus puntos con respecto a su coordenada de ángulo polar, puede dibujar su casco convexo. Esto solo es válido si el conjunto de sus puntos define un casco convexo (no cóncavo).

Entonces, ¿qué tal la clasificación a ti mismo?

Supongamos que el conjunto de puntos de casco convexo se almacena como puntos de lista en python, y C es el tipo de punto interno en su conjunto de puntos de casco convexo, puede preparar un comparador como el siguiente pseudocódigo:

 def cmpAngle(p1, p2): vector1 = p1 - C vector2 = p2 - C return dotProduct(vector1, vector2) points.sort(cmp=cmpAngle) 

La idea es hacer uso del producto punto para averiguar el orden por su rotación relativa.

Aquí tiene una implementación en python del casco convexo (esto es lo que está buscando):

http://www.scipy.org/Cookbook/Finding_Convex_Hull

He usado scipy.spatial para este tipo de problema. Tiene funciones específicas para trazar cascos convexos. Ver aqui Tal vez eso es más poder de fuego de lo que querías.