一尘不染

实施互联网的希尔伯特地图

algorithm

XKCD漫画195中,建议使用Hilbert曲线设计Internet地址空间的地图,以便将来自类似IP地址的项目聚集在一起。

给定一个IP地址,我将如何在这样的地图上计算其2D坐标(范围为0到1)?


阅读 283

收藏
2020-07-28

共1个答案

一尘不染

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

每个正方形中曲线的基本形状类似于马蹄形:

 0 3
 1 2

其中的数字对应于高两位,因此确定遍历顺序。在xkcd映射中,此正方形是最高级别的遍历顺序。可能旋转和/或反射后,此形状出现在每个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
11否则为。同样,y坐标中0的第一位是前两位是否具有值12。要确定是在坐标上添加a
0还是1位,您需要在该级别上检查马蹄铁的方向。

编辑:我开始研究算法,结果证明毕竟并不难,所以这里有一些伪C语言。这是伪的,因为我b为二进制常数使用了后缀,并将整数视为位数组,但是将其更改为适当的C并不难。

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

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映射正确放置了它们,因此我对代码的正确性有些信心。

2020-07-28