get the index of point which create ConvexHull

Question

I amtrying to use scipy.spatial (from scipy.spatial import ConvexHull)to draw convex hull of series of points.

import pylab as pl
from scipy.spatial import ConvexHull

pl.figure()  
pl.hold(True)  

points = np.concatenate((x, y), axis=1)

hull = ConvexHull(points)

pl.plot(points[:,0], points[:,1], 'ro')

for simplex in hull.simplices:
    pl.plot(points[simplex,0], points[simplex,1], 'dk--')    

The problem is I don't correctly understand what is hull.simplices, I want to find the indices of points which are on the facet of convexhull so I can use these indices to get the point from x and y

Answer 1

In the 2-D case, the simplices attribute of the ConvexHull object holds the pairs of indices of the points that make up the line segments of the convex hull. One way to get just the indices is to get the unique elements of the flattened simplices array. But note that the points will not be in an order that follows the convex hull around the set. (In scipy 0.13.0 and later, you can use the vertices attribute to get the indices; see below.)

For example,

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt


# Generate some random points for the demo.
np.random.seed(4321)
pts = 0.1 + 0.8*np.random.rand(15, 2)

ch = ConvexHull(pts)

# hull_indices = ch.vertices   # This will work in the scipy 0.13
hull_indices = np.unique(ch.simplices.flat)
hull_pts = pts[hull_indices, :]

plt.plot(pts[:, 0], pts[:, 1], 'ko', markersize=10)
plt.plot(hull_pts[:, 0], hull_pts[:, 1], 'ro', alpha=.25, markersize=20)
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.show()

This generates:

The vertices attribute was added in scipy 0.13.0:

import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt


# Generate some random points for the demo.
np.random.seed(4321)
pts = 0.1 + 0.8*np.random.rand(15, 2)

ch = ConvexHull(pts)

# Get the indices of the hull points.
hull_indices = ch.vertices

# These are the actual points.
hull_pts = pts[hull_indices, :]

plt.plot(pts[:, 0], pts[:, 1], 'ko', markersize=10)
plt.fill(hull_pts[:,0], hull_pts[:,1], fill=False, edgecolor='b')
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.show()