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

Question

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

algorithmmathhilbert-curve

18

在XKCD漫画195中，提出了一种使用希尔伯特曲线设计互联网地址空间地图的建议，以便来自相似IP地址的项目能够聚集在一起。

给定一个IP地址，我该如何计算它在这样一张地图上的二维坐标（范围为零到一）？

- Martin

5

整洁的实现现场：http://icicle.dylex.net/~ipmap/ - Mikeb

呵呵，很酷，我喜欢它标记“你在这里”的方式。 - Martin

JavaScript 实现：前往该页面并在开发控制台中输入 bfmap 或 bfrev。 - mgold

3个回答

5

基本上，您需要使用一对对的位数将数字分解，从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坐标，我现在在0.75，0.5。缠绕方式现在已经旋转，我的下一个比例尺将是（LR、LL、UL、UR）。比例尺现在是0.125，依此类推，直到我的地址中的位数用完为止。

- Mikeb

我认为这不是完全正确的。只要你获得1和2，它就可以工作。如果您获得0或3，则需要旋转以及缩小比例；否则，所有未来的位对都会使您误入歧途。 - Jason Orendorff

是的，我正在努力修复它。一开始看起来比较简单，但实际上更加复杂！ - Mikeb

是的，但我认为我喜欢jk的解释比我的好。 - Mikeb

你的更简单，我更直观地理解它 - 这得到了我的认可 :) - Martin

0

我期望基于希尔伯特曲线的维基百科代码，你可以跟踪你当前的位置（作为一个（x，y）坐标），并在访问n个单元格后返回该位置。然后，在完成时，缩放到[0..1]上的位置将取决于希尔伯特曲线的高度和宽度。

from turtle import left, right, forward

size = 10

def hilbert(level, angle):
    if level:
        right(angle)
        hilbert(level - 1, -angle)
        forward(size)
        left(angle)
        hilbert(level - 1, angle)
        forward(size)
        hilbert(level - 1, angle)
        left(angle)
        forward(size)
        hilbert(level - 1, -angle)
        right(angle)

诚然，这将是一种暴力解决方案而不是一个封闭形式的解决方案。

- hughdbrown

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JaakkoK · Accepted Answer

这很容易，因为希尔伯特曲线是一种分形，即递归。它通过水平和垂直平分每个正方形，将其分成四个部分来工作。因此，您每次使用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,1]范围内）为0，否则为1。类似地，如果前两位的值为1或2，则y坐标中的第一位为0。要确定是否将0或1位添加到坐标中，您需要检查该级别的马蹄铁的定向。

编辑：我开始编写算法，结果发现它并不难，所以这里有一些伪C代码。它是伪代码，因为我使用后缀b表示二进制常量，并将整数视为位数组，但将其更改为有效的C不应该太难。

在代码中，pos表示方向的3位整数。前两位是0在正方形中的x和y坐标，第三位指示1是否具有与0相同的x坐标。 pos的初始值为011b，这意味着0的坐标为

（0，1），而1具有与0相同的x坐标。ad是地址，视为2位整数的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地图正确放置了它们，因此我相当有信心代码是正确的。