在XKCD漫画195中,建议使用Hilbert曲线设计Internet地址空间的地图,以便将来自类似IP地址的项目聚集在一起。
给定一个IP地址,我将如何在这样的地图上计算其2D坐标(范围为0到1)?
这很容易,因为希尔伯特曲线是分形的,也就是说,它是递归的。它的工作原理是将每个正方形水平和垂直平分,将其分成四部分。因此,您一次从左开始一次获取IP地址的两位,并用它们确定象限,然后继续使用接下来的两位,用该象限而不是整个正方形,依此类推,直到得到用尽地址中的所有位。
每个正方形中曲线的基本形状类似于马蹄形:
0 3 1 2
其中的数字对应于高两位,因此确定遍历顺序。在xkcd映射中,此正方形是最高级别的遍历顺序。可能旋转和/或反射后,此形状出现在每个2x2正方形处。
如何在“马蹄”在每个子方格的取向确定是通过一个规则决定的:0在角落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。要确定是在坐标上添加a 0还是1位,您需要在该级别上检查马蹄铁的方向。
[0,1]
x
1
y
2
编辑:我开始研究算法,结果证明毕竟并不难,所以这里有一些伪C语言。这是伪的,因为我b为二进制常数使用了后缀,并将整数视为位数组,但是将其更改为适当的C并不难。
b
在代码中,pos方向的3位整数。前两位是0正方形的x和y坐标,第三位表示是否1具有与相同的x坐标0。的初始值为posis 011b,表示0are (0, 1)和的坐标1与相同0。ad是地址,被视为n2位整数的- element数组,并且从最高有效位开始。
pos
011b
(0, 1)
ad
n
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映射正确放置了它们,因此我对代码的正确性有些信心。