私はリストを狭くする方法を大規模なセットから決定しようとしています。3D数学 - 一定のヤード内の位置を保持するだけです
私は約3000のポジション（x、y、z）を持ち、基本的には互いに離れているポジションを維持したいと考えています（私は100ヤードを2ヤード互いからの半径）。
brute forceメソッドを実行し、文字通り3000^2の比較を行う以外に、どのようにしてこのリストをさらに絞り込むことができますか？
私は、これを数学の観点からどのようにアプローチするべきかについて少し混乱しています。
まあ、私はこのアルゴリズムの名前を覚えていませんが、これを扱うための楽しいテクニックを教えてあげます。私は、3D環境での点の半ランダム散乱があると仮定します。
シンプルバージョン：分割統治
のは、いくつかのメモリに
を保存しようした場合これにより、1回のパスできわめて単純化されたデータセットが得られますが、メモリが大量になる可能性があります。
あまりにも多くのメモリを使用せずにどのようにしますか？
私のキーが上記のサンプルのGrid-Cube座標（5,8,9）であるようなハッシュテーブルを使用したいと思います。
If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...)
さて、あなたは最小限のメモリ使用量の空のキューブの潜在的に多数で（無巨大な配列を持つ1パス・ソリューションを持っています。コストとは何ですか？まあ、プログラミング時間の設定には、あなたの構造/クラスあなたはハッシュテーブルの.containsアクションを実行できるように（または、あなたの言語に相当）
はねえ、私の結果は分厚いです！そうです
、我々は最初の結果を取ったので、任意の立方体に収まること。平均して、頂点間の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のポリシーなどを追加しないでください。顕著なスムージング効果を達成するには厳格すぎる必要はありません。
それでもあまりにも分厚い、私はそれがこのバリエーションで
を滑らかにしたい、私たちは、頂点が立方体に居を取ることが許可されているかどうかのために予選アクションを変更します。
注意してください。このためにネイバー検出を実行する必要はありません。各キューブの中心に向かって最適化します。
このバリエーションは、以前のバリエーションとマージできます。チートモード
は、このような状況で何人かの人々のために、あなたは単にあなたのデータセットの10％ランダムな選択を取ることができ、それは良い、十分に簡素化されます。しかし、いくつかの点が非常に密接な関係にあるので、非常にチャンクです。明るい側では、最大数分かかる。プロトタイピングしない限り、私はそれをお勧めしません。
説明を明確にするために、データセットを簡素化し、Y立方ヤードあたり約Xポイントの代表サンプルを作成します。 –
はい、それは私が書いたものよりずっと優れています！ – Geesu
これは非常に効率的でよく研究された解決策をどこかに持つ問題のようですが、オクトリー（または同様の）にすべてのポイントを入れてから、通常の3Dグリッド/メッシュを作成し、ボリュームYのセルごとにXの結果ポイントを除くすべてを破棄しますか？ – mdunsmuir