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; unsigned state, s, row; state ... |
Get Hacker's Delight now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.