In this post I will describe how to draw Hilbert curve iteratively.
To avoid recursion we will use
hindex2xy algorithm that
translates Hilbert curve node index to
To index Hilbert curve nodes we assume that
curve starts in the left bottom corner and ends in the right bottom corner.
Indexes start at zero. Here is example numbering of
N=8 Hilbert curve:
We expect that
hindex2xy(17) = (x:1, y:4) and
hindex2xy(40) = (x:6, y:6).
hindex2xy algorithm uses bottom-up approach to compute node coordinates without
using recursion. When we look at the binary representation of the node indexes we may
notice that the last two bits represent node position inside
N=2 Hilbert curve.
Next two bits represent where that
N=2 Hilbert curve is located inside bigger
N=4 curve etc.
Example will show us
how it works for
N=4 Hilbert curve and
Let’s start by writing index value as binary number: 7 dec is equal 0111bin.
The last two bits of 0111bin are
corresponds to the bottom right node of the
N=2 Hilbert curve (marked green on the image).
This node has Cartesian coordinates
Now let’s move to the next two bits:
01bin, these bits corresponds to the left upper corner of
N=4 Hilbert curve
(marked yellow on the image).
N=4 coords we must notice that
left upper corner of
N=4 curve is just translated copy of
So to get
N=4 coords we must apply translation
(x:0, y:2) to
We end with
(x:1, y:2) point that correctly
represent node with index 7 inside
Let’s assume that we want to find out coords of node in
N=2K Hilbert curve,
given that we have coords
(x,y) of node in
In general when computing coords bottom-up we have four cases:
Cases B and C are really simple since
N=2K curve contains copies
N=K curve in B and C squares. In case B we should
transform coords using equation:
And in case C we should use equation:
In cases A and D we must be careful when transforming coords because we must
preserve order of traversal of
N=K curve inside
I marked each curve start and end with red and blue dots so we can
see better how we should perform transformation.
In case A first node of
N=K curve should coincide with first node of
N=K curve should end next to the start of “case B” curve.
We can achieve this by flipping coords around diagonal:
Case D is similar to case A, we must flip coords but around second diagonal: In addition to that we must translate node coords to the right:
Having this algorithm we may draw Hilbert curve as follows:
And here are results:
Source code: hilbert_curve