这个算法将坐标映射到称为的数字是什么？

Question

我正在编写一个用于可视化晶体的程序.作为程序的一部分,我必须在晶格结构中生成所有不同的基本点.对于那些不熟悉晶体学的人,你可以在这里找到这些结构最常见的例子:https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types

问题是我想跟踪所有这些要点.所以我给了他们一个号码.我正在尝试使用笔和纸,并找到了一个很好的算法,通过以二进制形式写出来将坐标(2D或3D)与数字(以及相反的方式)连接起来.

因此,如果您想要,例如,2D中的简单立方晶格,并且您想知道第14点的坐标,您可以将此二进制数写为001110.您将数字分为00 | 11 | 10,其中最多右边的部分代表(x,y)*1,中间部分代表(x,y)*2,左边的部分代表(x,y)*4(对于数字14来说没用,只是为了制作一切清除)等等.所以数字14映射到点(3,2).

一个简单的C++程序,用于生成前50个int的坐标:

int x, y;

for (int n = 0; n < 50; n++)
{
    x = 0;
    y = 0;

    bitset<16>  nset(n);

    for (int i = 0; i < 16/2; i++)
    {
        x+=(nset[2*i]*pow(2.,i));
        y+=(nset[2*i+1]*pow(2.,i));
    }

    cout  << n << "\t" << x << "\t" << y << endl;
}

我通过为z值保留一个额外的列将此算法扩展为3D,并通过保留第一个或两个列的类型为x + 1/2,y + 1/2,z + 1 /来扩展其他格子类型2个属性,每种格子类型不同.

所以这是我的问题:这个算法是否已存在？它有名字吗？或者这只是二进制数学的一个明显应用？我读了一些关于hashmaps的东西,但这对我来说似乎更有效,至少如果你处理的是整数.

这是我在stackexchange的第一个问题,怀疑我必须在这里或在物理论坛上发布这个问题.或者也许在数学论坛上,因为这是一种R ^ 2-> R双射.如果这个问题不在正确的地方,请纠正我.

Answer 1

所以这是我的问题：这个算法已经存在吗？它有名字吗？

这种映射称为 Z 阶曲线或莫顿码：

在数学分析和计算机科学中，Z 阶、莫顿阶或莫顿码是一种将多维数据映射到一维同时保留数据点局部性的函数。它由 GM Morton 于 1966 年推出。多维中点的 z 值可以通过交错其坐标值的二进制表示来简单地计算。一旦数据按此顺序排序，就可以使用任何一维数据结构，例如二叉搜索树、B 树、跳跃列表或（截断低有效位）哈希表。结果排序可以等效地描述为从四叉树的深度优先遍历中获得的顺序。

如示例 C++ 代码所示，x 坐标存储在偶数位中，y 坐标存储在奇数位中。该映射可以轻松扩展到更高的维度。

可以在此处找到一些使用位操作操作对这些数字进行快速交织的算法。