algorithm - 实现互联网的希尔伯特图

Question

在XKCD comic 195建议使用 Hilbert curve 设计互联网地址空间的 map 。这样来自相似 IP 地址的项目将聚集在一起。

给定一个 IP 地址，我如何在这样的 map 上计算它的二维坐标(在 0 到 1 的范围内)？

Answer 1

这很简单，因为希尔伯特曲线是分形的，也就是说，它是递归的。它的工作原理是将每个正方形水平和垂直平分，将其分成四 block 。所以你一次取两位 IP 地址，从左边开始，用它们来确定象限，然后继续，使用接下来的两位，用那个象限而不是整个正方形，等等，直到你有用尽地址中的所有位。

每个正方形中曲线的基本形状是马蹄形的:

 0 3 1 2

where the numbers correspond to the top two bits and therefore determine the traversal order. In the xkcd map, this square is the traversal order at the highest level. Possibly rotated and/or reflected, this shape is present at each 2x2 square.

Determination of how the "horseshoe" is oriented in each of the subsquares is determined by one rule: the 0 corner of the 0 square is in the corner of the larger square. Thus, the subsquare corresponding to 0 above must be traversed in the order

 0 1 3 2

and, looking at the whole previous square and showing four bits, we get the following shape for the next division of the square:

 00 01 32 33 03 02 31 30 10 13 20 23 11 12 21 22

This is how the square always gets divided at the next level. Now, to continue, just focus on the latter two bits, orient this more detailed shape according to how the horseshoe shape of those bits is oriented, and continue with a similar division.

To determine the actual coordinates, each two bits determine one bit of binary precision in the real number coordinates. So, on the first level, the first bit after the binary point (assuming coordinates in the [0,1] range) in the x coordinate is 0 if the first two bits of the address have the value 0 or 1, and 1 otherwise. Similarly, the first bit in the y coordinate is 0 if the first two bits have the value 1 or 2. To determine whether to add a 0 or 1 bit to the coordinates, you need to check the orientation of the horseshoe at that level.

EDIT: I started working out the algorithm and it turns out that it's not that hard after all, so here's some pseudo-C. It's pseudo because I use a b suffix for binary constants and treat integers as arrays of bits, but changing it to proper C shouldn't be too hard.

In the code, pos is a 3-bit integer for the orientation. The first two bits are the x and y coordinates of 0 in the square and the third bit indicates whether 1 has the same x coordinate as 0. The initial value of pos is 011b, meaning that the coordinates of 0 are (0, 1) and 1 has the same x coordinate as 0. ad is the address, treated as an n-element array of 2-bit integers, and starting from the most significant bits.

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 映射正确放置了它们，所以我有点相信代码是正确的。