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 Cartesian coordinates.

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 `index=7`: Let’s start by writing index value as binary number: 7 dec is equal 0111bin. The last two bits of 0111bin are 11bin, they corresponds to the bottom right node of the `N=2` Hilbert curve (marked green on the image). This node has Cartesian coordinates `(x:1, y:0)`. 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). To transform `N=2` into `N=4` coords we must notice that left upper corner of `N=4` curve is just translated copy of `N=2` curve. So to get `N=4` coords we must apply translation `(x:0, y:2)` to `N=2` coords:

We end with `(x:1, y:2)` point that correctly represent node with index 7 inside `N=4` curve.

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 `N=K` curve. In general when computing coords bottom-up we have four cases: Cases B and C are really simple since `N=2K` curve contains copies of `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 `N=2K` curve. 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=2K` curve and `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:

Finally let’s see full algorithm code in JavaScript:

Having this algorithm we may draw Hilbert curve as follows:

And here are results: ##### Github

Source code: hilbert_curve