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.