Convex Hull and SciPy

Question

I'm trying to use scipy (0.10.1) for a quick hack to visualize the convex hull.

I can get the convex hull using the following code:

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

the resulting array looks like this:

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

the numbers are the vertex indices. My problem is they are not ordered. I'd need them to be in CW or CCW order in order to easily visualize them in KML.

Is there any easy way to have scipy.spatial compute the proper clockwise order?

Answer 1

So this code seems to do the trick, but could be simpler... Essentially, I first collect the vertex numbers from the hull. Then I compute the mean, recenter the dataset and sort it by the angle from the mean.

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 2

In the current dev doc (0.13.0.dev) of scipy.spatial.ConvexHull, there is a vertices property which is counterclockwise in 2D.

Answer 3

I found out a nice method but it requires scipy 0.11.0 (sparse.csgraph)

Here is a full example, the actual sorting are the 2 lignes following the "sort hull ..." comment.

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])