Given the coordinates of a point on the Hilbert curve, the distance from the origin to the point can be calculated by means of a state transition table similar to Table 14-2. Table 14-5 is such a table.
Its interpretation is similar to that of the previous section. First, x and y should be padded with leading zeros so that they are of length n bits, where n is the order of the Hilbert curve. Second, the bits of x and y are scanned from left to right, and s is built up from left to right.
A C program implementing these steps is shown in Figure 14-9.
unsigned hil_s_from_xy(unsigned x, unsigned y, int n) {int i;
unsigned state, s, row;
state = 0; // Initialize.
s = 0;
for (i = n - 1; i >= 0; i--) {row = 4*state | 2*((x >> i) & 1) | (y >> i) & 1;
s = (s << 2) | (0x361E9CB4 >> 2*row) & 3;
state = (0x8FE65831 >> 2*row) & 3;
}
return s;
}
[L&S] give an algorithm for computing s from (x, y) that is similar to their algorithm for going in the other direction (Table 14-3). It is a left-to-right algorithm, shown in Table 14-6 and Figure 14-10.
unsigned hil_s_from_xy(unsigned x, unsigned y, int n) {int i, xi, yi;
unsigned s, temp;
s = 0; // Initialize.
for (i = n - 1; i >= 0; i--) {xi = (x >> i) & 1; // Get bit i of x.
yi = (y >> i) & 1; // Get bit i of y.
if (yi == 0) {temp = x; // Swap x and y and,
x = y^(-xi); // if xi = 1,
y = temp^(-xi); // complement them.
}
s = 4*s + 2*xi + (xi^yi); // Append two bits to s. } return s;
}
Table 14-6. Lam and Shapiro method for computing S from (X, Y) |
||
|
If the next (to right) two bits of (x, y) are |
then |
and append to s |
|
(0, 0) |
Swap x and y |
00 |
|
(0, 1) |
No change |
01 |
|
(1, 0) |
Swap and complement x and y |
11 |
|
(1, 1) |
No change |
10 |