Reasoning the calculation of the Hilbert's distance

Question

I'm not a mathematician, I'm a computer science student, and I'm attending to a course called Advanced Functional Programming. There's this homework where I need to implement the Hilbert R-tree data type. In case any of you are not familiar with this structure, it is used to store spatial data, and it is very good for being queried, since it shows a nice overall performance (Here you can find more info on this structure).

The thing is, I do understand how the structure works, but it uses the Hilbert distance as the key for sorting the info within the structure. Actually, I've found an implementation of the Hilbert distance algorithm in Haskell (which happens to be the language that I'll be using on my homework), and I'm allowed to use it as long as I make reference to the original author. It works, but I don't quite understand how does this algorithm work, and I would really like to.

Could anyone please explain me in a simple way how does this work?

Since this question has to do more with the mathematical background of the algorithm instead of with the implementation, I decided to post my question here instead of in StackOverflow; but, in any case, I'm not mathematician, so please be gentle in your explanation =)

thanks!

Answer 1

The Hilbert curve of order $n$ consists of 4 pieces, each of which is a Hilbert curve of order $n-1$. See the picture here. The algorithm computes the distance from $(x,y)$ to the bottom left corner via a recursion. The operator

case (compare x side, compare y side) of

determines in which of 4 pieces (quadrants) the point $(x,y)$ is located. The simplest case is

(LT, LT) -> step result y x

which means we are in the bottom left quadrant. This piece of the curve is just the $(n-1)$ order curve reflected about the diagonal: this reflection is why we interchange y and x. Next case is

(LT, _)  -> step (result + area) x (y - side)

which means we are in the top left quadrant. To get to such a point, we must travel all of the bottom-left quadrant (this is why the term "area" added), and then we enter the $(n-1)$-order curve in the normal orientation. To compute how far we travel within the top-left quadrant, we replace y by y-side (bringing the point down into bottom-left) and call the function again. The other two cases should be understandable now:

(_, _)   -> step (result + area * 2) (x - side) (y - side)

is the top-right quadrant. We travel area*2 just to get there, and then we call the function with x-side and y-side, thus bringing the point into the bottom-left corner.

(_, LT)  -> step (result + area * 3) (side - y - 1) (side * 2 - x - 1)

is the bottom-right quadrant, the most remote one. To get here we first travel by 3 other quadrants (hence area*3). To find the length of our path within the bottom-right corner we call the procedure again, taking care to flip the coordinates correctly. Look at the picture and imagine reflecting the bottom-right quadrant so that it coincides with the bottom-left one. We must reflect the curve in both x and y directions, so that the entrance into the bottom-right quadrant is mapped to the bottom-left corner of the square.