pythonconvex-hullpyhull

Pyhull python library: Output of convex hull are not subset of the input set


I installed Pyhull library to generate the convex hull for a set of points. The documentation and usage are straightforward. However, the output of the library is strange. Its documentation at pythonhosted has this snippet

from pyhull.convex_hull import ConvexHull
pts = [[-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5], [0,0]]
hull = ConvexHull(pts)
hull.vertices
hull.points

and the output, respectively, is

[[0, 2], [1, 0], [2, 3], [3, 1]]
[[-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5], [0, 0]]

The convex hull of a set of points P is the smallest convex set containing P. Therefore, the points defining the convex hull are a subset of the input set while the output of the library is not so.


Solution

  • You can use set() to find the unique indices and then extract the points:

    from pyhull.convex_hull import ConvexHull
    pts = [[-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5], [0, 0]]
    hull = ConvexHull(pts)
    I = set((i for edge in hull.vertices for i in edge))
    P = (hull.points[i] for i in I)
    
    print(I, tuple(P))
    
    
    

    Prints

    {0, 1, 2, 3} ([-0.5, -0.5], [-0.5, 0.5], [0.5, -0.5], [0.5, 0.5])
    

    The function extracts the indices of the points that form the convex hull and then retrieves the corresponding points.