5

多数のポジションから、リストを大幅に絞り込む方法を決定しようとしています。

現在、約3000の位置（x、y、z）があり、基本的に互いに最も離れた位置を維持したいと考えています（半径2ヤード以内にある100の位置を維持する必要はありません）。 ）。

強引な方法を実行し、文字通り3000 ^ 2の比較を実行する以外に、このリストをさらに絞り込む方法について誰かが何か考えを持っていますか？

数学の観点からこれにどのように取り組むべきかについて少し混乱しています。

4

1 に答える 1

7

さて、このアルゴリズムの名前は思い出せませんが、これを処理するための楽しいテクニックを紹介します。3D環境には点の半ランダム散乱があると仮定します。

シンプルバージョン：分割統治

  1. スペースを立方体の3Dグリッドに分割します。各立方体は、各側でXヤードになります。
  2. グリッド内の各立方体の要素を持つように、多次元配列[x、y、z]を宣言します。
  3. 配列のすべての要素は、頂点または頂点（x、y、z）構造への参照のいずれかである必要があり、それぞれのデフォルトはNULLである必要があります。
  4. データセット内の各頂点を反復処理し、頂点がどのキューブに該当するかを判別します。
    • どのように？X（立方体の辺の長さ）のサイズが1であると仮定すると、（5.5、8.2、9.1）頂点はMyCubes [5,8,9]に属していると考えるかもしれません。注：小数/浮動小数点数を次のように切り捨てました。どのキューブを決定します。
  5. その関連するキューブがすでに頂点によって取得されているかどうかを確認してください。チェック：MyCubes [5,8,9] == NULLの場合、（頂点を挿入）else（何もせず、投げ出します！スポットを取得しました、バディ）

メモリを節約しましょう

これにより、1回のパスで非常に単純化されたデータセットが得られますが、大量のメモリが必要になる可能性があります。

では、メモリを使いすぎずにどうやってそれを行うのでしょうか？

上記のサンプルでは、​​キーがグリッドキューブ座標（5、8、9）になるようにハッシュテーブルを使用します。

 If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...)

これで、メモリ使用量を最小限に抑えたワンパスソリューションが得られます（空のキューブが多数存在する可能性のある巨大な配列はありません。コストはいくらですか？）を実行できるように構造/クラスをセットアップするためのプログラミング時間です。 HashTable（または同等の言語）のアクションが含まれています

ねえ、私の結果は分厚いです！

そうです、どのキューブにも当てはまる最初の結果を取得したからです。平均して、頂点間のX分離を達成しますが、これまでに理解できるように、一部の頂点は（立方体のエッジで）互いに近接しています。

では、どのように処理するのでしょうか。さて、一番上にある配列メソッドに戻りましょう（メモリを大量に消費します！）。

頂点がすでに問題のキューブにあるかどうかを確認するだけでなく、次の別の確認も実行します。

 If Not ThisCubeIsTaken()
    For each SurroundingCube
      If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me()
         exit_loop_and_outer_if_statement()
      end if
    Next
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me
 End If

3D配列を使用している場合、隣接する立方体を取得するのは非常に簡単なので、おそらくこれの美しさを理解できると思います。

このような平滑化を行う場合は、おそらく「0.25Xの場合は追加しない」ポリシーなどを適用できます。目立つスムージング効果を実現するために、厳しすぎる必要はありません。

まだ分​​厚い、スムーズにしたい

このバリエーションでは、頂点が立方体に存在することを許可するかどうかの限定アクションを変更します。

 If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube's current vertex
    InsertVertex (overwrite any existing vertex in the cube
 End If

これについては、ネイバー検出を実行する必要がないことに注意してください。各立方体の中心に向かって最適化するだけです。

必要に応じて、このバリエーションを前のバリエーションとマージできます。

チートモード

このような状況にある一部の人々にとっては、データセットを10％ランダムに選択するだけで、十分に単純化できます。ただし、いくつかのポイントが非常に接近しているため、非常に分厚いものになります。明るい面では、最大で数分かかります。プロトタイピングをしているのでない限り、お勧めしません。

于 2013-02-12T00:51:41.727 に答える