11

3D デカルト ベクトルとして表される無秩序な点の大規模なセット (数万から数百万) が与えられた場合、すべての点を囲む規則的な正方形グリッド (ユーザー定義の間隔) を作成するための適切なアルゴリズムは何ですか? いくつかの制約:

  1. グリッドは正方形で規則的である必要があります
  2. 理想的には単一の変数を使用して、グリッド間隔 (正方形の 1 つの辺の長さ) を調整できる必要があります。
  3. 最小サイズのグリッドが必要です。つまり、グリッド内のすべての 'ブロック' には、少なくとも 1 つの無秩序な点が含まれている必要があり、すべての無秩序な点は 'ブロック' で囲まれている必要があります。
  4. アルゴリズムの戻り値は、グリッド ポイントの座標のリストである必要があります。

2D で説明すると、次の一連の点が与えられます。

ポイントのセット

あるグリッド間隔 X の場合、アルゴリズムの戻り値の 1 つとして、これらの赤い点の座標が考えられます (破線は説明目的のみ)。

グリッド間隔 x

グリッド間隔 X/2 の場合、アルゴリズムの可能な戻り値の 1 つは、これらの赤い点の座標になります (破線は説明目的のみ)。

グリッド間隔 x/2

興味のある方のために説明すると、私が取り組んでいる無秩序な点は、.pdb ファイルから取得できるような大きなタンパク質分子の原子座標です。

ソリューションには Python が好まれますが、疑似コードも適しています。

編集: 必要なものについての最初の説明は少しあいまいだったと思うので、明確にするためにいくつかの制約と画像を追加しました。

4

6 に答える 6

6

kd treeを作成することをお勧めします。高速で、シンプルで、実装が簡単です。

KDツリー

そしてウィキペディアのコード:

class Node: pass

def kdtree(point_list, depth=0):
    if not point_list:
        return

    # Select axis based on depth so that axis cycles through all valid values
    k = len(point_list[0]) # assumes all points have the same dimension
    axis = depth % k

    # Sort point list and choose median as pivot element
    point_list.sort(key=lambda point: point[axis])
    median = len(point_list) // 2 # choose median

    # Create node and construct subtrees
    node = Node()
    node.location = point_list[median]
    node.left_child = kdtree(point_list[:median], depth + 1)
    node.right_child = kdtree(point_list[median + 1:], depth + 1)
    return node

ただし、制約内に収まるように、わずかに変更する必要があります。

于 2011-09-21T23:07:57.960 に答える
2

ユーザー指定の間隔の規則的な正方形のグリッドを求めているため、かなり単純なアプローチが機能するはずです。

データを通過して、各次元の最小座標と最大座標を計算することから始めます。最大値と最小値の間の距離をカバーするために必要なユーザー指定の間隔のステップ数を計算します。

データを再度通過して、各座標の最小点と指定された間隔 (例: X_cell = Math.floor((x_i - x_min) / 間隔) を持つグリッドを使用して、各点をグリッド内のセルに割り当てます。 ）。ディクショナリまたは配列を使用して、各セルのポイント数を記録します。

ここで、セル内に少なくとも 1 つの点があるセルの座標を出力します。

私が最適化を試みていない自由があります: 最小座標と最大座標の間の距離がグリッド間隔の正確な倍数でない限り、グリッドをスライドさせてもそれを保持できる傾斜があります。すべてのポイント: 現時点では、グリッドは最低点の位置から始まりますが、おそらく最高点の前に終了するため、各次元で少し下に移動する余地があります。これを行うと、いくつかのポイントがセルからセルに移動し、占有されているセルの数が変化します。

一度に 1 次元の動きだけを考えれば、合理的に効率的に何が起こるかを理解できます。各点とそのセルのその次元の最大座標との間のその次元の距離を計算し、これらの値を並べ替えます。グリッドを下に移動すると、最大座標までの距離が最小のポイントが最初にセルを交換し、ソートされた順序で移動することにより、これらのポイントを 1 つずつ反復できます。これを行うときにセル内のポイントの数を更新すると、どのシフトが占有セルの数を最小化するかを判断できます。

もちろん、心配すべき 3 つの次元があります。細胞数が減少するまで、一度に 1 つずつ作業できます。これはローカルの最小値ですが、グローバルな最小値ではない場合があります。他の極小値を探す 1 つの方法は、ランダムに選択された開始点からやり直すことです。

于 2011-09-22T04:24:18.920 に答える
2

ボロノイ図はどうですか？Fortunes アルゴリズムO(n log n)を使用して生成できます。

それがあなたの問題に対処するかどうかはわかりませんが、ボロノイ図は非常に「自然」です。それらは自然界で非常に一般的です。

例 (ウィキペディアから):

ここに画像の説明を入力

于 2011-09-21T23:12:58.090 に答える
1

すべての点を囲む最小面積の正方形を見つけます。各正方形を繰り返し 4 つのサブ正方形に分割します (1 から 4、16、64、…)。正方形の 1 つが空になる直前に停止します。得られたグリッドが最適解の最大で 4 倍粗いことを証明することは難しくありません (重要な洞察: 空の正方形には、少なくとも 2 倍細かいグリッドから少なくとも 1 つの正方形が含まれていることが保証されています)。

おそらく、ランダムな変換を導入することで、その定数を減らすことができます。

于 2011-09-21T23:02:24.447 に答える
0

グリッドセルを正方形で規則的なものにしたい場合は、おそらく八分木が必要です。正方形と通常の制約を緩和できる場合は、kdツリーを作成できます。

于 2011-09-25T15:36:06.117 に答える