实现互联网的Hilbert映射

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (14)

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

提问于
用户回答回答于

Hilbert曲线是分形的,也就是说,它是递归的。它的工作原理是将每个正方形水平和垂直平分,分成四块。所以你一次取两位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如果地址的前两位具有以下值01,和1否则。类似地,y坐标是0如果前两位具有以下值12...。若要确定是否添加01位到坐标,你需要检查马蹄铁在那个水平的方向。

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

在密码里,pos是指向方向的3位整数。前两位是0在正方形和第三个位中表示是否1具有与0...。初值pos011b的坐标0(0, 1)1具有与0...ad地址是否被视为n元素数组由2位整数组成,从最重要的位开始.

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));
}
用户回答回答于

本质上,你会分解这个数字,使用对位,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坐标,我在.75,5。卷绕现在是旋转的,我的下一个规模将是(LR,LL,UL,UR)。现在的比例尺是.125,以此类推,直到我的地址里的位数用完为止。

扫码关注云+社区