### 14-3 Distance from Coordinates on the Hilbert Curve

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.

##### Figure 14-9 Program for computing s from (x, y).
`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.

##### Figure 14-10 Lam and Shapiro method for computing s from (x, y).
`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-5. State transition table for computing S from (X, Y)

If the current state is

and the next (to right) two bits of (x, y) are

then append to s

and enter state

A

(0, 0)

00

B

A

(0, 1)

01

A

A

(1, 0)

11

D

A

(1, 1)

10

A

B

(0, 0)

00

A

B

(0, 1)

11

C

B

(1, 0)

01

B

B

(1, 1)

10

B

C

(0, 0)

10

C

C

(0, 1)

11

B

C

(1, 0)

01

C

C

(1, 1)

00

D

D

(0, 0)

10

D

D

(0, 1)

01

D

D

(1, 0)

11

A

D

(1, 1)

00

C

##### 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