18

在XKCD 漫画 195中，建议使用希尔伯特曲线设计 Internet 地址空间图，以便将来自相似 IP 地址的项目聚集在一起。

给定一个 IP 地址，我将如何在这样的地图上计算其二维坐标（范围从零到一）？

4

3 回答 3

14

这很容易，因为希尔伯特曲线是分形的，也就是说，它是递归的。它的工作原理是将每个正方形水平和垂直平分，将其分成四块。所以你一次取两位 IP 地址，从左边开始，用它们来确定象限，然后继续，使用接下来的两位，用那个象限而不是整个正方形，依此类推，直到你有用尽了地址中的所有位。

每个正方形中曲线的基本形状是马蹄形的：

0 3
 1 2

其中数字对应于前两位，因此确定了遍历顺序。在xkcd map中，这个方块是最高层的遍历顺序。可能旋转和/或反射，这种形状出现在每个 2x2 正方形上。

确定“马蹄形”在每个子方格中的方向取决于一个规则：方格的0角0在较大方格的角上。因此，上面对应的子方格0必须按顺序遍历

0 1
 3 2

并且，查看整个前一个正方形并显示四个位，我们为正方形的下一个分区得到以下形状：

00 01 32 33
 03 02 31 30
 10 13 20 23
 11 12 21 22

这就是正方形总是在下一级被划分的方式。现在，继续，只关注后两个位，根据这些位的马蹄形如何定位这个更详细的形状，并继续进行类似的划分。

为了确定实际坐标，每两位确定实数坐标中的一位二进制精度。因此，在第一级，坐标中二进制点（假设坐标在[0,1]范围内）之后的第一位x是0地址的前两位是否具有值0or 1，1否则。类似地，y坐标中0的第一位是前两位的值是否为1或2。要确定是否向坐标添加一个0或1位，您需要检查该级别的马蹄铁的方向。

编辑：我开始研究算法，结果发现它并不难，所以这里有一些伪 C。它是伪的，因为我使用b二进制常量的后缀并将整数视为位数组，但将其更改为适当的 C 应该不会太难。

在代码中，pos方向是一个 3 位整数。前两位是0正方形中的 x 和 y 坐标，第三位表示是否1与 有相同的 x 坐标0。的初始值pos是011b，意味着 的坐标0是(0, 1)和1具有相同的 x 坐标0。ad是地址，被视为n2 位整数的元素数组，从最高有效位开始。

double x = 0.0, y = 0.0;
double xinc, yinc;
pos = 011b;
for (int i = 0; i < n; i++) {
    switch (ad[i]) {
        case 0: xinc = pos[0]; yinc = pos[1]; pos[2] = ~pos[2]; break;
        case 1: xinc = pos[0] ^ ~pos[2]; yinc = pos[1] ^ pos[2]; break;
        case 2: xinc = ~pos[0]; yinc = ~pos[1]; break;
        case 3: xinc = pos[0] ^ pos[2]; yinc = pos[1] ^ ~pos[2];
            pos = ~pos; break;
    }
    x += xinc / (1 << (i+1)); y += yinc / (1 << (i+1));
}

我用几个 8 位前缀对其进行了测试，它根据 xkcd 映射正确放置了它们，所以我有点确信代码是正确的。

于 2009-12-29T21:27:11.040 回答
5

本质上，您将使用成对的位（MSB 到 LSB）分解数字。这对位告诉您该位置是否在左上 (0) 左下 (1) 右下 (2) 或右上 (3) 象限，随着数字的移动，比例会变得更精细。

此外，您需要跟踪“方向”。这是您所在比例使用的绕组；初始绕组如上（UL、LL、LR、UR），根据您最终进入的象限，下一个按比例缩小的绕组是（旋转-90、0、0、+90）当前绕组.

所以你可以累积偏移量：

假设我从 0,0 开始，第一对给我一个 2，我将偏移量转移到 0.5、0.5。右下角的绕线和我最初的一样。下一对缩小比例，所以我的调整长度将是 0.25。

这对是 3，所以我只翻译我的 x 坐标，我在 0.75，0.5。绕组现在旋转过来，我的下一个比例缩小将是（LR，LL，UL，UR）。比例现在是 0.125，依此类推，直到地址中的位用完为止。

于 2009-12-29T21:14:29.833 回答
0

我希望根据希尔伯特曲线的维基百科代码，您可以跟踪当前位置（作为 (x, y) 坐标）并在访问 n 个单元后返回该位置。然后缩放到 [0..1] 的位置将取决于希尔伯特曲线在完成时的高度和宽度。

from turtle import left, right, forward

size = 10

def hilbert(level, angle):
    if level:
        right(angle)
        hilbert(level - 1, -angle)
        forward(size)
        left(angle)
        hilbert(level - 1, angle)
        forward(size)
        hilbert(level - 1, angle)
        left(angle)
        forward(size)
        hilbert(level - 1, -angle)
        right(angle)

诚然，这将是一个蛮力解决方案，而不是一个封闭形式的解决方案。

于 2009-12-29T21:16:16.523 回答