what do I get from scipy.spatial.Delaunay.convex_hull

Question

I thought scipy.spatial.Delaunay.convex_hull is returning an array where every point/index is used twice, because one point belongs to two edges. But in my case there are several indices only one time:

hull = [[5053 6943]
        [6219 5797]
        [3441 5797]
        [7547 1405]
        [3441 6547]
        [8144 9215]
        [  47  444]
        [ 444 6219]
        [6547 5053]
        [9945 6943]
        [2695 1405]]

For example the "47" is only used once. What does this mean (geometrically) ? How can one point of a convex hull only be used for one edge?

Answer 1

As mentioned in the comment above, you should use the newer scipy.spatial.ConvexHull. If you look at the indices of the vertices returned from this method in my IPython examples below, you will see that they are not normally redundant for 2D or 3D data sets.

%pylab inline
import numpy
#use a simple trianglular data set:
triangle_points = numpy.array([[0,0],[-1,1],[1,1]])

#plot the triangle:
fig = plt.figure()
ax = fig.add_subplot(111,aspect='equal')
ax.scatter(triangle_points[...,0],triangle_points[...,1])

#now calculate the convex hull of the triangular point set:
import scipy, scipy.spatial
convex_hull_2D = scipy.spatial.ConvexHull(triangle_points)
#determine the indices of the vertices forming the convex hull (i.e., the output you get with the older scipy version):
convex_hull_vertex_indices = convex_hull_2D.vertices
#print the array of convex hull vertex indices:
convex_hull_vertex_indices
array([2, 1, 0], dtype=int32) #output

#For this simple 2D data set it is clear that scipy can define a convex hull using the index of each input point only once, so it is not doing AB, BC, CA as you might initially guess

#Let's see what happens if we add a point outside the plane of the triangle and make the data set 3D:
tetrahedral_points = numpy.array([[0,0,0],[-1,1,0],[1,1,0],[0,0.5,3]]) #the last element is the 'out of plane' new point
convex_hull = scipy.spatial.ConvexHull(tetrahedral_points)
convex_hull_vertex_indices = convex_hull.vertices
convex_hull_vertex_indices
array([0, 1, 2, 3], dtype=int32) #output  

#again, for a simple shape, even in 3D, scipy specifies the indices of the vertices of the convex hull in a non-redundant manner

#take a look at the simplices of the 2D ConvexHull object:
convex_hull_simplices = convex_hull_2D.simplices
convex_hull_simplices
array([[2, 1],
       [0, 1],
       [0, 2]], dtype=int32) #output

#so the simplices do contain duplicate indices to connect points to form edges/1-simplices
fig = plt.figure()
ax = fig.add_subplot(111,aspect='equal')
ax.set_ylim(0,1.2)
edge_colors = ['blue','red','green'] #color each 1-simplex differently for clarity
for simplex, edge_color in zip(convex_hull_simplices,edge_colors):
    plt.plot(triangle_points[simplex,0], triangle_points[simplex,1], c=edge_color)