Что я могу получить от scipy.spatial.Delaunay.convex_hull

Question

Я думал, что scipy.spatial.Delaunay.convex_hull возвращает массив, в котором каждая точка / индекс используется дважды, потому что одна точка принадлежит двум ребрам. Но в моем случае есть несколько показателей только один раз:

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

Например, "47" используется только один раз. Что это значит (геометрически)? Как можно использовать одну точку выпуклой оболочки только для одного ребра?

Answer 1

Как уже упоминалось в комментарии выше, вы должны использовать более новую scipy.spatial.ConvexHull, Если вы посмотрите на индексы вершин, возвращаемых этим методом, в моих примерах IPython ниже, то увидите, что они обычно не являются избыточными для наборов данных 2D или 3D.

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