有限個の値のマッピング＃

Question

私は、有限であるが多数の3次元位置（約10^11）をインデックスにマッピングできるアルゴリズムを探しています（マッピング³³ - >ℕ ）

私は、ℕ - >ℝ3マッピングを作ることは可能であり、それはかなり簡単であり、それは基本的に私がしたいことですが、ℕ - >ℝ³はℕのどのインデックスが近くにあるのか

理想的には、ofの私の有限サブセットに重複が含まれないようにしたいと考えています。

これは、この問題にはいくつかの単純なソリューションを制約し、問題のより良いアイデアを与えるために実装される方法のいくつかの背景：

私はへの銀河の星をマッピングする方法を考えるしようとしています私が乱数ジェネレータの "シード"として使うことができるユニークなIDであれば、ℕ - >ℝ3マッピングは、与えられた場所の近くにあるℝ³の値を見つけるためにallのすべてを繰り返し処理する必要があります。

私はすでにcantorペアリング機能とダブテールについていくつかの情報を見つけましたが、それらは主にℕⁿではなくℝⁿに適用されるため、問題を引き起こします。

私のℝ3値がグリッドに沿っていることを保証するものではありませんが、もし私がℝ3-ℕ³をマップすることができれば、その値がどの "ボックス"であるのかを知ることができます。私の状況では、ボックスには複数の値が含まれている場合もあれば、存在しない場合もあります。任意のヘルプ

Answer 1

を事前に

おかげであなたはk-d treeは、空間的にポイントのあなたのセットを分割するために使用することができます。自然数にマップするには、ツリー内の各点までのパスを2進数の文字列として扱います。0は左分岐で、1は右分岐です。お互いに空間的に近いいくつかのポイントが異なるブランチ上にある可能性があり、したがって数値的に離れているので、これはあなたが探しているものを正確に得られない可能性があります。しかし、2つの点が数値的に近い場合、それらは空間的に互いに近くなります。

また、octreeを使用することもできます。その場合、ツリーに降下する各レベルごとに3ビットずつ取得します。各領域に最大で1つの関心領域が含まれるように、空間を完全に分割することができます。