从点集生成凸层的有效算法

Question

我有一个点的列表，我试图在python中生成凸层。在

目前我只使用以下方法：

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 

这只是一次创建一个凸面外壳。虽然它是有效的，但似乎很像是简单地通过重复加法来实现乘法。所以我要问的是，有没有一种更有效的算法，专门用于从一组点创建凸层

Answer 1

如果使用monotone chain algorithm，则只需进行一次字典排序。然后在O（n）时间内找到每个连续层。这应该比每层的排序快。在

Answer 2

您可以尝试使用scipyspatial.convexHull。在

或者，我贴了一些code on GitHub。在