python - Convex Hull and SciPy

geometry computational-geometry

Question

Estoy tratando de usar scipy (0.10.1) para un truco rápido para visualizar el casco convexo.

Puedo obtener el casco convexo usando el siguiente código:

vecs = [[-0.094218, 51.478927], [-0.09348,  51.479364], [-0.094218, 51.478927],
        ...
        [-0.094218, 51.478927], [-0.094321, 51.479918], [-0.094218, 51.478927],
        [-0.094222, 51.478837], [-0.094241, 51.478388], [-0.094108, 51.478116],
        [-0.09445,  51.480279], [-0.094256, 51.478028], [-0.094326, 51.500511]]
hull = scipy.spatial.Delaunay(vecs).convex_hull

la matriz resultante se ve así:

[[56,  9], [16,  1], [56,  1], [55,  9], [53, 55], [53, 16]]

los números son los índices de los vértices. Mi problema es que no están ordenados . Necesito que estén en orden de CW o CCW para poder visualizarlos fácilmente en KML.

¿Hay alguna manera fácil de hacer que scipy.spatial calcule el orden correcto en el sentido de las agujas del reloj?

Answer 1

Encontré un buen método pero requiere scipy 0.11.0 (sparse.csgraph)

Aquí hay un ejemplo completo, la clasificación real son las 2 líneas siguiendo el comentario de "ordenar el casco ...".

import numpy as np
import scipy as sp

# random point cloud and hull
X = np.random.randint(0,200,(30,2))
hull = sp.spatial.qhull.Delaunay(X).convex_hull

# sort hull indices using (sparse) adjacency matrix graph stuff
g = sp.sparse.csr_matrix((np.ones(hull.shape[0]),hull.T), shape=(hull.max()+1,)*2)
sorted_hull = sp.sparse.csgraph.depth_first_order(g,hull[0,0],directed=False)[0]

# display with matplotlib
from matplotlib import pyplot as plt
plt.plot(X[:,0],X[:,1],''.'')
plt.plot(X[sorted_hull,0],X[sorted_hull,1])

Answer 2

Entonces este código parece ser el truco, pero podría ser más simple ... Básicamente, primero colecciono los números de vértice del casco. Luego calculo la media, recentro el conjunto de datos y lo ordena por el ángulo de la media.

ps = set()
for x, y in hull:
    ps.add(x)
    ps.add(y)
ps = numpy.array(list(ps))
center = vecs[ps].mean(axis=0)
A = vecs[ps] - center
h = vecs[ps[numpy.argsort(numpy.arctan2(A[:,1], A[:,0]))]]

Answer 3

En el documento dev actual (0.13.0.dev) de scipy.spatial.ConvexHull , hay una propiedad de vertices que está en sentido antihorario en 2D.