Efficent algorithm for creating the convex layers from a set of points

Question

I've got a list of points that I'm trying to generate the convex layers for in python.

Currently I'm simply using the following:

def convex_layers(points):
   points = sorted(set(points))
   layers = []
   while points:
      #Create the next convex hull
      hull = convex_hull(points)

      #Create the new list of points
      for point in hull:
         points.remove(point)

      #Update the list of layers
      layers.append(hull)
   return layers 

Which is just to create the convex hulls one at a time. While it works, it seems a lot like trying to multiply simply by repeated addition. So what I'm asking is if there is a more efficient algorithm specifically for creating convex layers from a set of points

Answer 1

If you use the monotone chain algorithm, you will have to do the lexicographic sorting only once. Then each successive layer can be found in O(n) time. This ought to be faster than sorting for each layer.

Answer 2

You can try with scipy spatial.convexHull.

Or, I posted some code on GitHub.