### 14-4 Incrementing the Coordinates on the Hilbert Curve

Given the (x, y) coordinates of a point on the order n Hilbert curve, how can one find the coordinates of the next point? One way is to convert (x, y) to s, add 1 to s, and then convert the new value of s back to (x, y), using algorithms given above.

A slightly (but not dramatically) better way is based on the fact that as one moves along the Hilbert curve, at each step either x or y, but not both, is either incremented or decremented (by 1). The algorithm to be described scans the coordinate numbers from left to right to determine the type of U-curve that the rightmost two bits are on. Then, based on the U-curve and the value of the rightmost two bits, it increments or decrements either x or y.

That's basically it, but there is a complication when the path is at the end of a U-curve (which happens once every four steps). At this point, the direction to take is determined by the previous bits of x and y and by the higher order U-curve with which these bits are associated. If that point is also at the end of its U-curve, then the previous bits and the U-curve there determine the direction to take, and so on.

Table 14-7 describes this algorithm. In this table, the A, B, C, and D denote the U-curves as shown in Table 14-1 on page 246. To use the table, first pad x and y with leading zeros so they are n bits long, where n is the order of the Hilbert curve. Start in state A and scan the bits of x and y from left to right. The first row of Table 14-7 means that if the current state is A and the currently scanned bits are (0, 0), then set a variable to indicate to increment y, and enter state B. The other rows are interpreted similarly, with a suffix minus sign indicating to decrement the associated coordinate. A dash in the third column means do not alter the variable that keeps track of the coordinate changes.

After scanning the last (rightmost) bits of x and y, increment or decrement the appropriate coordinate as indicated by the final value of the variable.

A C program implementing these steps is shown in Figure 14-11. Variable dx is initialized in such a way that if invoked many times, the algorithm cycles around, generating the same Hilbert curve over and over again. (However, the step that connects one cycle to the next is not a unit step.)

##### Figure 14-11 Program for taking one step on the Hilbert curve.
`void hil_inc_xy(unsigned *xp, unsigned *yp, int n) {`
` `
`牋 int i; `
`牋爑nsigned x, y, state, dx, dy, row, dochange; `
` `
`牋 x = *xp; `
`牋爕 = *yp; `
`牋爏tate = 0;牋牋牋牋牋牋牋牋牋 // Initialize. `
`牋燿x = -((1 << n) - 1);牋牋牋?// Init. -(2**n - 1). `
`牋燿y = 0; `
` `
`牋 for (i = n-1; i >= 0; i--) {牋牋牋牋 // Do n times. `
`牋牋牋row = 4*state | 2*((x >> i) & 1) | (y >> i) & 1; `
`牋牋牋dochange = (0xBDDB >> row) & 1; `
`牋牋牋if (dochange) {`
`牋牋牋牋 dx = ((0x16451659 >> 2*row) & 3) - 1; `
`牋牋牋牋燿y = ((0x51166516 >> 2*row) & 3) - 1; `
`牋牋牋} `
`牋牋牋state = (0x8FE65831 >> 2*row) & 3; `
`牋爙 `
`牋?xp = *xp + dx; `
`牋?yp = *yp + dy; `
`} `
##### Table 14-7. Taking one step on the Hilbert curve

If the current state is

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

then prepare to inc/dec

and enter state

A

(0, 0)

y+

B

A

(0, 1)

x+

A

A

(1, 0)

?/p>

D

A

(1, 1)

y-

A

B

(0, 0)

x+

A

B

(0, 1)

?/p>

C

B

(1, 0)

y+

B

B

(1, 1)

x-

B

C

(0, 0)

y+

C

C

(0, 1)

?/p>

B

C

(1, 0)

x-

C

C

(1, 1)

y-

D

D

(0, 0)

x+

D

D

(0, 1)

y-

D

D

(1, 0)

?/p>

A

D

(1, 1)

x-

C

Table 14-7 can readily be implemented in logic, as shown in Figure 14-12. In this figure, the variables have the following meanings:

##### Figure 14-12. Logic circuit for incrementing (x, y) by one step along the Hilbert curve.

 xi: Bit i of input x. yi: Bit i of input y. X, Y: xi and yi swapped and complemented, according to Si+1 and Ci+1. I: If 1, increment; if 0, decrement (by 1). W: If 1, increment or decrement x; if 0, increment or decrement y. S: If 1, swap xi and yi. C: If 1, complement xi and yi.

S and C together identify the "state" of Table 14-7, with (C, S) = (0, 0), (0, 1), (1, 0), and (1, 1) denoting states A, B, C, and D, respectively. The output signals are I0 and W0, which tell, respectively, whether to increment or decrement, and which variable to change. (In addition to the logic shown, an incrementer/decrementer circuit is required, with MUX's to route either x or y to the incrementer/ decrementer, and a circuit to route the altered value back to the register that holds x or y. Alternatively, two incrementer/decrementer circuits could be used.)