3

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

これは、凸包を一度に1つずつ作成するためだけのものです。それは機能しますが、単純に加算を繰り返すだけで乗算しようとするのとよく似ています。だから私が求めているのは、ポイントのセットから凸状のレイヤーを作成するためのより効率的なアルゴリズムがあるかどうかです

4

2 に答える 2

3

単調連鎖アルゴリズムを使用する場合は、辞書式順序付けを1回だけ実行する必要があります。次に、連続する各層をO（n）時間で見つけることができます。これは、各レイヤーの並べ替えよりも高速である必要があります。

于 2012-11-09T04:08:37.263 に答える
0

scipyで試すことができますspatial.convexHull。

または、 GitHubにコードを投稿しました。

于 2013-05-25T19:05:21.490 に答える