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

Question

在XKCD漫画195中,建议使用希尔伯特曲线设计互联网地址空间的地图,以便来自类似IP地址的项目将聚集在一起.

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

Answer 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如果地址的前两个比特具有值0或1,和1以其他方式.类似地,y坐标中0的第一位是前两位是否具有值1或2.要确定是否在坐标上添加0或1位,您需要检查该级别的马蹄形方向.

编辑:我开始计算算法,事实证明它毕竟不是那么难,所以这里有一些伪C.它是伪的,因为我使用b二进制常量的后缀并将整数视为位数组,但将其更改为正确的C应该不会太难.

在代码中,pos是一个3位整数的方向.前两位是0方形中的x和y坐标,第三位指示是否1具有相同的x坐标0.初始值为posis 011b,表示坐标为0are (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映射正确放置它们,所以我有点相信代码是正确的.

Answer 2

基本上你会使用位对,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,依此类推,直到我的地址中的位数不足为止.