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;
牋爑nsigned state, s, row;
牋 state = 0;牋牋牋牋牋牋牋牋牋牋牋牋牋?// Initialize.
牋爏 = 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;
牋爙
牋爎eturn 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;
牋爑nsigned s, temp;
牋 s = 0;牋牋牋牋牋牋牋牋牋牋牋牋 // Initialize.
牋爁or (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,
牋牋牋牋爔 = y^(-xi);牋牋牋牋牋牋 // if xi = 1,
牋牋牋牋爕 = temp^(-xi);牋牋牋牋?// complement them.
牋牋牋}
牋牋牋s = 4*s + 2*xi + (xi^yi);牋 // Append two bits to s. 牋?/span>} 牋爎eturn 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 |