这很容易,因为希尔伯特曲线是分形的,也就是说,它是递归的。它的工作原理是将每个正方形水平和垂直平分,将其分成四部分。因此,您一次从左开始一次获取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
1,
1否则为。同样,
y坐标中
0的第一位是前两位是否具有值
1或
2。要确定是在坐标上添加a
0还是
1位,您需要在该级别上检查马蹄铁的方向。
编辑:我开始研究算法,结果证明毕竟并不难,所以这里有一些伪C语言。这是伪的,因为我
b为二进制常数使用了后缀,并将整数视为位数组,但是将其更改为适当的C并不难。
在代码中,
pos方向的3位整数。前两位是
0正方形的x和y坐标,第三位表示是否
1具有与相同的x坐标
0。的初始值为
posis
011b,表示
0are
(0, 1)和的坐标
1与相同
0。
ad是地址,被视为
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映射正确放置了它们,因此我对代码的正确性有些信心。



