这种将坐标映射到数字的算法叫什么？

Question

我正在编写可视化晶体的程序。作为程序的一部分，我必须在格子结构中生成所有不同的基点。对于那些不熟悉晶体学的人，您可以在此处找到这些结构的最一般情况：https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types

问题是我想跟踪所有这些点。所以我给了他们一个号码。我试着用笔和纸做了一些尝试，发现了一个很好的算法，可以通过以二进制形式将坐标（2D 或 3D）与数字（反之亦然）连接起来。

所以如果你想要，例如，一个简单的二维立方晶格，你想知道点号 14 的坐标。你可以把这个二进制写成 001110。你把这个数字分成 00|11|10 ，其中最右边的部分代表(x,y)*1，中间的部分代表(x,y)*2，左边的部分代表(x,y)*4（对数字14没用），只是为了让一切都清楚）等等。所以数字 14 映射到点 (3, 2)。

为前 50 个整数生成坐标的简单 C++ 程序：

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 属性，每种 Lattice 类型都不同。

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

这是我在 stackexchange 上的第一个问题，怀疑我是否必须在这里或在物理论坛上 post 这个问题。或者也许在数学论坛上，因为这是一种 R^2->R 双射。所以如果这个问题不在正确的地方，请指正我。

Answer 1

我可能误解了你的代码，但你所做的似乎是取二进制数的偶数位，将它们连接在一起形成一个新数字，并将该数字用作你的 x 坐标.您似乎对 y 坐标做了同样的事情。

我认为该算法没有名称，但它似乎是一种非常标准的技术。对于它的价值，我认为有一种更简单的方法可以通过使用按位运算符而不是 bitset 和 pow:

来完成您在这里所做的事情

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

    for (int i = 0; i < 8; i++) {
        if (n & (1 << (2*i)) != 0) {
           x += 1 << i;
        }
        if (n & (1 << (2*i + 1)) != 0) {
           y += 1 << i;
        }
    }
    cout << n << " " << x << " " << y << endl;
}

值1 << k是第k位为1，否则为0的数字。如果 n 的第 k 位为 0，则使用按位 AND 运算符将此数字与 n 进行 AND 操作将返回 0，否则返回非零数字。因此，测试 if (n & (1 << k) != 0) 检查 n 的第 k 位是否被设置。然后，我们不使用 pow 来计算 2ⁿ，而是使用 1 << k 具有数值 2^{k[=30= 的事实].}

希望对您有所帮助！

Answer 2

不幸的是，这可能对您没有帮助，但作为一个奇怪的琐事，这对应于 joke language INTERCAL.

中的 INTERLEAVE（或 MINGLE）运算符

我不知道这种编码的另一个名称。但它通常用得不多，因为大多数计算机上都有可用的指令，将两个（或许多）整数的二进制表示简单地连接在一起会更简单、更快，这只需要 O(d) 时间（也许只有作为 d-1 机器指令）对于 d 维。关于你的编码我能想到的一个优点是它不需要你为每个维度承诺一个固定的位大小，所以你需要编码一个格点的最大位数与最大坐标值——这是你实际使用的东西吗？

Answer 3

So here's my question: does this algorithm exists already? Has it a name?

此映射称为 Z 顺序曲线或 Morton code:

In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a function which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree.

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

可以找到一些用于使用位操作操作对这些数字进行快速交织以对这些数字进行编码的算法 here。

这种将坐标映射到数字的算法叫什么？

What is this algorithm mapping coordinates to numbers called?

algorithm

coordinates

coordinate-systems

coordinate