Here be dragon (curve)s

If you take a strip of paper and fold it in half, then fold in half again in the same direction, and repeatedly do this. When you unfold it, if you allow each crease to become a 90° angle, then the shape that the paper makes is known as a Dragon Curve.

I first learned about these as a younger teenager, and spent far too long trying to draw them on an eight bit computer.

It is relatively straight-forward to be see how to construct them recursively, unfortunately there were a couple of challenges.

1. I'm not sure that my understanding of recursion was particularly solid.
2. The primary programming language that I had access to (BBC Basic) didn't support recursion — I did have access to LOGO, but for some reason I don't recall trying to solve this problem with it. It would likely be trivial.

At some point I stumbled across a solution that doesn't require recursion, and reduces the problem to a simple rendering exercise.

As programmers we are familiar with the binary representation of the integers, and the natural sequence of them — 0000, 0001, 0010, 0011, etc.

There are different orderings of the natural numbers that have different properties in binary. One of these is the Gray code, in which each element of the sequence differs from the previous element by only a single changed bit (either 0→1 or 1→0).

To generate this in an iterative process, we take the XOR of each natural number with itself shifted right by one bit (divided by two).

The rightmost column above is the popcount or population count of the XOR result. This is the count of the number of 1's in the binary number, also known as the Hamming weight.

If we assign a direction to each of these numbers: 0 →, 1 ↓, 2 ←, 3 ↑, and draw equal length segments according to the sequence in the right hand column, this will draw the following

I have only shown the first 8 values in the sequence above, partially to keep it shorter, but also because after the 8th value we will start getting popcount values that are greater than 3. We handle this by simply using the popcount modulo 4 as the direction.

This method is very simple, and draws dragon curves — all the curves on this parge are drawn using it — but why?

I don't know a formal proof, but intuitively there are a few things that I consider

1. Because each element in the sequence differs by a single bit from the previous one, this necessarily causes the popcount to alternate between even and odd values. This means that there will never be two consecutive values the same, and that — given the direction assignments — the directions will alternate between horizontal and vertical — this may be simpler to think about as turning either left or right at each element.

2. Each time the we add another significant bit to the natural number that we are deriving the sequence from we add another potential bit that contributes to the popcount, which when considering the physical analog of folding paper, represents another fold.

3. Another name for the Gray code is the reflected binary code, which refers to a different construction of the same code:

   1. Starting with the sequence [0, 1]
   2. Create two copies of the sequence so far
   3. Prefix each element of the first copy with a 0
   4. Reverse the order of the second copy and prefix each element with a 1
   5. Concatenate the two copies
   6. Repeat from step 2.

   The first few iterations of this process create [00, 01, 11, 10], [000, 001, 011, 010, 110, 111, 101, 100], [0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1001]

   The reversal of the order in Step 4. is then analogous to the folding process, and the addition of the 1 to the elements in the second copy is a rotation through 90°

Below is the dragon curve representing 12 folds of the paper (nearly impossible in practice due to physical limits) that was always my goal to be able to render as a teenager. Each of the 4096 folds or turns is drawn with an arc, showing that they never cross.