ℝ³ -> ℕ 有限数量值的映射

Question

我正在寻找一种能够将有限但大量的 3 维位置（大约 10^11）映射到索引（因此映射 ℝ³ -> ℕ）的算法

我知道制作 ℕ -> ℝ³ 映射是可能的，而且相当简单，这基本上就是我想做的，但是 ℕ -> ℝ³ 是确定 ℕ 的哪些索引接近的不切实际的方法某个位置，

理想情况下，我还想确保我的 ℕ 的有限子集不包含重复项。

关于如何实施的一些背景知识，以便更好地了解约束和问题以及一些天真的解决方案：

我正在想办法将星系中的恒星映射到一个唯一的 ID，然后我可以将其用作随机数生成器的 "seed"，需要 ℕ -> ℝ³ 映射我遍历所有ℕ以找到给定位置附近的ℝ³值，这显然不是一种实用的方法

我已经找到了一些关于 cantor 配对函数和吻合的信息，但是这些会导致问题，因为它们主要适用于 ℕⁿ 而不是 ℝⁿ。

不能保证我的 ℝ³ 值遵循网格，如果确实如此，我可以映射 ℝ³-> ℕ³，方法是找出 "box" 值所在的位置，然后使用 cantor 的配对函数找出which ℕ 属于那个盒子，但在我的情况下，盒子可能包含多个值，或者 none.

在此先感谢您的帮助

Answer 1

您可以使用 k-d tree 在空间上划分您的点集。要映射到自然数，将通过树到每个点的路径视为二进制数字串，其中 0 是左分支，1 是右分支。这可能无法让您准确地找到您正在寻找的东西，因为一些在空间上彼此靠近的点可能位于不同的分支上，因此在数值上彼此相距很远。但是，如果两个点在数值上彼此接近，则它们在空间上也将彼此接近。

或者，您也可以使用 octree，在这种情况下，对于下降到树中的每个级别，您一次获得三位。您可以完全划分 space，这样每个区域最多包含一个兴趣点。