Am1rr3zA Am1rr3zA - 13 days ago 7
Python Question

get the index of point which create ConvexHull

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

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:

Plot of points and convex hull

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

convex hull example

Comments