In this note we will learn how to draw the Hilbert Curve using a computer program written in Scheme.
There are a number of descriptions in books, papers, and online that talk about how to draw the curve. (For a list of the materials that I reviewed while trying to learn this, see the References section below.) Unfortunately, I found most of the descriptions very difficult to understand!
Most descriptions of how to draw the Hilbert curve seem to fall into one of the following categories:
- Using magic tables of numbers to generate coordinates, which is fine if you already understand how to construct the curve and then work backwards from there to figure out how to generate those magic numbers. But it doesn’t really help you understand how to draw it in the first place.
- A “grammatical” approach using L-systems (about which see the wiki article linked above), which is fine if you want to take a detour into writing an interpreter for L-systems. Unfortunately, I did not — or at least, I did not think it would teach me much about how to actually draw the Hilbert curve. But it’s definitely a cool approach!
- Iterating over C arrays and doing magical bitshifts to represent both the points on the curve and the various rotations/reflections that are applied to those points.
In my opinion, none of these approaches are really useful for learning. They are fine if you are looking for implementation techniques for something you already understand.
Thankfully all was not lost. I spent a lot of time reading, and scratching my head, and drawing curves in my notebook. Then, I found the excellent article Crinkly Curves by Brian Hayes. In addition to the great information in the article, Hayes linked to a really helpful visualization on his website called “Constructing the Hilbert Curve”. I urge you to try it, since seeing the visualization is important to what follows.
Seeing this is what helped me finally understand. Thank you, Brian Hayes!
The algorithm displayed in Hayes’ visualization is approximately what I ended up implementing, and it looked like this in Scheme:
(define (hilbert order width) (let loop ((count 0) (shape (h0 width))) (if (= count order) shape (let* ((next-shape (shrink-shape shape 0.5)) (upper-left (reflect-shape (rotate-shape next-shape (* 3.14159 1.5)))) (upper-right (translate-shape next-shape 'east width)) (lower-left (translate-shape next-shape 'south width)) (lower-left* (reflect-shape (rotate-shape lower-left (* 3.14159 .5)))) (lower-right (translate-shape next-shape 'southeast width))) (loop (+ count 1) (merge-shapes upper-left upper-right lower-right lower-left*))))))
It works like this:
- Given a “shape” (starting with the zeroth order Hilbert curve, which is just point in the center of a square), make 4 copies of that shape, each of which fits in a square 1/2 the width of the original square. Then, “move” the shape to one of the 4 corners of the original square. (The “move” is accomplished by a call to
translate-shapeas shown above.)
- Depending on which corner of the full-sized square the shape is now in, it may need to be rotated (spun) around its axis so it points in the right direction. In some cases it may also need to be reflected so that the locality of the points in the curve is correctly preserved. Note that the calls to
rotate-shapetake a radians argument, a unit for measuring angles. 360 degrees is equal to
(* 3.14159 2)in radians. For more information, see this article.
- Keep repeating the previous two steps, bumping a counter and accumulating a list of points until we have all of the points for an Nth order curve. We accumulate the list of points using
merge-shapes, which is really just
- Base case: The counter is now equal to the
orderargument, telling us we have an Nth order Hilbert curve. So we return the accumulated list of points.
These “points” are really just 2-element
(X Y) lists, as you can see below:
> (hilbert 2 600)) ((74.99970147174234 75.00029852944591) (224.9997014705541 74.99970147174234) (225.00029852825764 224.9997014705541) (75.00029852944591 225.00029852825764) (75 375) (75 525) (225 525) (225 375) (375 375) (375 525) (525 525) (525 375) (525.0000995095512 224.99990049031675) (375.00009950968325 225.00009950955126) (374.99990049044874 75.00009950968327) (524.9999004903167 74.99990049044875))
Using some not-so-interesting utility code that builds an SVG (XML) file and does some geometry things like shape rotation, etc., we can draw this list of points by outputting it into an SVG polyline:
(let ((content (tag->string (svg (shape->polyline (rotate-shape (hilbert 5 600) (* 3.14159 0.5))))))) (with-output-to-file "hilbert.svg" (lambda () (display content))))
hilbert.svg output by the above code looks like this:
We can make an even prettier picture if we stack the curves atop each other in the same image as follows:
(let ((content (tag->string (svg (reverse (list (shape->polyline (rotate-shape (hilbert 1 600) (* 3.14159 0.5)) 'black) (shape->polyline (rotate-shape (hilbert 2 600) (* 3.14159 0.5)) 'red) (shape->polyline (rotate-shape (hilbert 3 600) (* 3.14159 0.5)) 'blue) (shape->polyline (rotate-shape (hilbert 4 600) (* 3.14159 0.5)) 'orange) (shape->polyline (rotate-shape (hilbert 5 600) (* 3.14159 0.5)) 'yellow))))))) (with-output-to-file "multi-hilbert.svg" (lambda () (display content))))
Here is the image in
- Algorithms + Data Structures = Programs, a book by Niklaus Wirth (p. 131-132)
- Table-driven algorithms for generating space-filling curves, a paper by J.G. Griffiths
- Crinkly Curves, an article by Brian Hayes
- Constructing the Hilbert Curve, an animation by Brian Hayes
- Wikipedia article on Hilbert Curve
- Hilbert curve implementations on Rosetta Code