问题标签 [z-order-curve]

我正在寻找一种快速计算 3D 莫顿数的方法。这个站点有一个基于幻数的技巧来处理 2D 莫顿数，但如何将其扩展到 3D 似乎并不明显。

所以基本上我有 3 个 10 位数字，我想用最少的操作将它们交织成一个 30 位数字。

我有一个 MySQL 记录表，每个记录都有一个 lat/lng 坐标。根据中心点和半径对这些数据进行搜索（返回半径内的任何记录）。我正在使用余弦球面定律来计算查询中的距离。我的问题是索引地理数据的效率非常低（纬度/经度值存储为浮点数）。使用 MySQL 的空间扩展不是一种选择。对于大约 100k 大小的数据集，查询需要不合理的时间来执行。

我做了一些研究，似乎使用 z-index 即莫顿数可能会有所帮助。我可以计算插入时每条记录的莫顿数，然后根据地球的半径/中心点/给定的搜索半径计算边界框的高/低莫顿值。

我对这些东西的了解只够构建我的应用程序，所以我不完全确定这是否可行，而且我也不知道如何在 PHP 中计算莫顿数。这会是按位运算吗？

从 32 位整数中解交织位的最有效方法是什么？对于这种特殊情况，我只关心奇数位，尽管我确信将任何解决方案推广到两组都很简单。

例如，我想转换0b01000101为0b1011. 最快的方法是什么？

编辑：

在这个应用程序中，我可以保证偶数位全为零。我可以利用这一事实来提高速度或减少空间吗？

在模拟粒子相互作用时，我偶然发现了莫顿顺序（Z 顺序）（维基百科链接）的网格索引，它被认为可以提供有效的最近邻单元搜索。我读过的主要原因是内存中空间接近的单元的几乎顺序排序。

在第一次实现的过程中，我无法思考如何有效地实现最近邻居的算法，尤其是与基本的统一网格相比。

1. 给定一个单元格 (x,y)，获取 8 个相邻单元格索引并计算相应的 z 索引是很简单的。尽管这提供了对元素的恒定访问时间，但必须计算或在预定义的表中查找 z-index（每个轴和 OR'ing 分开）。这怎么可能更有效率？是否真的，按 A[0] -> A 1 -> A[3] -> A[4] -> ...的顺序访问数组 A 中的元素比按 A[1023 的顺序访问更有效] -> A[12] -> A[456] -> A[56] -> ...？

2. 我期望存在一种更简单的算法来以 z 顺序查找最近的邻居。类似的东西：找到邻居的第一个单元格，迭代。但这不可能是真的，因为这只能在 2^4 大小的块内很好地工作。但是有两个问题：当单元格不在边界上时，可以很容易地确定块的第一个单元格并遍历块中的单元格，但必须检查该单元格是否是最近邻。更糟糕的是，当单元格位于边界上时，必须考虑 2^5 个单元格。我在这里想念什么？是否有一种相对简单有效的算法可以满足我的需求？

第 1 点中的问题很容易测试，但我对所描述的访问模式生成的底层指令不是很熟悉，并且真的很想了解幕后发生的事情。

在此先感谢您的任何帮助、参考等...

关于第 2 点：我应该补充一点，我了解如何为 R^d 中的点云构建莫顿有序数组，其中索引 i = f(x1, x2, ..., xd) 是从逐位隔行扫描等获得的。我试图理解的是是否有比以下天真 ansatz 更好的方法来获取最近的邻居（这里在 d=2 中，“伪代码”）：

这个问题：How to de interleave bits (UnMortonizing?)对于提取莫顿数的两半之一（只是奇数位）有一个很好的答案，但我需要一个提取两个部分（奇数位和偶数位）在尽可能少的操作中。

对于我的使用，我需要一个 32 位整数并提取两个 16 位整数，其中一个是偶数位，另一个是奇数位右移 1 位，例如

似乎有很多解决方案使用带有幻数的移位和掩码来生成莫顿数（即交错位），例如通过二进制幻数交错位，但我还没有找到任何相反的方法（即去交错） .

更新

在重新阅读 Hacker's Delight 关于完美洗牌/取消洗牌的部分后，我发现了一些有用的示例，我将其改编如下：

我认为这仍然可以在其当前的标量形式和利用 SIMD 的情况下得到改进，所以我仍然对更好的解决方案（标量或 SIMD）感兴趣。

如果我有一个数据集，其中键是 3D 点，由 3 个有符号 64 位整数表示。而且我想使用（排序的）键值存储来存储它们，其中键只是字节数组（但我可以指定一个比较器）。我想我可以通过使用位交错将所有这些点变成一个字节数组，就像如何计算 3D Morton 数中的 Z/Morton 顺序一样

除了获取单个点（可以在没有 Morton 排序的情况下更简单地完成）之外，我还想做范围搜索，在与轴对齐的框中进行搜索。我将 A 和 B 分别定义为所有坐标最低的框角，以及所有坐标最高的对角。

现在我的问题是：

1. 对于逻辑上介于 A 和 B 之间的任何点 C，C 的莫顿数是否也在 A 和 B 的莫顿数之间？（这不是莫顿命令的重点吗？）

2. 如果 1 为否，A 和 B 是否可以“四舍五入”到保证包含 C 的值？

3. 假设 1 或 2 是可能的，搜索返回是否也指向该框之外，我必须“后过滤”它？“错误集”有多大（它取决于搜索的大小或位置）？

4. 整数有符号的事实是否会导致问题？如果是这样，是否有解决方法？

回顾一下，使用 Morton Numbers 只是实际问题的一种可能解决方案：当 3D 点必须映射到一维值时，如何在 3D 整数空间中有效地进行范围搜索？我想通过在数据库中执行单个范围选择，使用最小键和最大键来获得 A 和 B 之间的所有点，理想情况下，在框外获得尽可能少的点。

我想为 32 位、64 位和 128 位生成一个 morton 密钥，并使用最佳代码！解决方案是什么？

我一直在阅读有关 morton 代码的内容，并且我发现本地性保留在生成的数字序列中。

我不明白的是如何使用这些信息来压缩数据或有效地并行构造数据。

资料来源：http ://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/

我想通过使用 morton 顺序来转置矩阵以进行改进矩阵转置。

我找到了一些关于 morton order 的文章，但我不明白如何使用它。

尤其，

和

我想反转这个矩阵 A = [1 2 3 4; 5 6 7 8；9 10 11 12；13 14 15 16]（线性地址）

至

B = [1 2 5 6; 3 4 7 8; 9 10 13 14；11 12 15 16；]。

然后转置。

但是我解决不了......

有人知道这种转变的原理吗？

真的提前谢谢了。

对于我当前的输入数据，即 3D 点，我使用Morton 代码来提高访问点列表时的缓存一致性。

我还有一些其他数据是 6D 和 7D。对于这样的维度，莫顿代码仍然是一种很好的技术吗？或者有没有其他的技术？其他空间填充曲线技术在 3D 本身中的计算比 Morton 更复杂，我想知道人们是否使用 6D/7D 或更高的替代技术。