Geek Answers Handbook

Convex hull and SciPy

I am trying to use scipy (0.10.1) for a quick hack to visualize a 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 is as follows:

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

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

Is there an easy way to get scipy.spatial to calculate the correct clock order?

+6
python scipy geometry computational-geometry convex-hull
source share
3 answers

So this code seems to do the trick, but it could be simpler ... Basically, I first collect the vertex numbers from the enclosure. Then I calculate the average, return the data set and sort it at an angle from the average.

 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]))]]
+10
source share

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

+8
source share

I found a good method, but it requires scipy 0.11.0 (sparse.csgraph)

Here is a complete example: the actual sort is 2 characters after the comment "sort hull ...".

 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])
+4
source share

More articles:


All Articles