python - 从一组点创建凸层的有效算法

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

如果你使用单调链算法，你只需要进行一次字典排序。然后可以在 O(n) 时间内找到每个连续的层。这应该比对每一层进行排序要快。

Answer 2

您可以尝试使用 scipy spatial.convexHull。

或者，我在 GitHub 上发布了一些代码。