8

This is my first time using TikZ, and I'm trying to draw something related to the Hilbert space-filling curve, based on a recent popular article (HTML, PDF). Specifically, I'm trying to draw the first few iterations of the curve, with nodes labelled by quaternary strings (strings on the alphabet {0,1,2,3}). I have something that sort of works, but I would like to know if there's a better way of doing it. The first iteration is straightforward enough — I can get this image:

Hilbert curve, iteration 1

with this code:

  \begin{tikzpicture}
    \node (0) at (0, 0) {$0$};
    \node (1) at (0, 1) {$1$};
    \node (2) at (1, 1) {$2$};
    \node (3) at (1, 0) {$3$};
    \draw [->] (0) -- (1);
    \draw [->] (1) -- (2);
    \draw [->] (2) -- (3);
  \end{tikzpicture}

The second iteration involves four copies of this, where the first and last are flipped and rotated, and I was able to get this image:

Hilbert curve, iteration 2

with this code:

  \begin{tikzpicture}
    \foreach \quadrant / \xscale / \rotate / \xshift / \yshift in
        {0 / -1 / 90 / 0 / 0,
         1 / +1 / 00 / 0 / 2,
         2 / +1 / 00 / 2 / 2,
         3 / -1 / -90 / 3 / 1}  % (3, 1) = (1, 1) + (2, 0): the former is just to rotate
    {
      \begin{scope}[shift = {(\xshift, \yshift)}, xscale = \xscale, rotate = \rotate]
        \node (\quadrant0) at (0, 0) {$\quadrant0$};
        \node (\quadrant1) at (0, 1) {$\quadrant1$};
        \node (\quadrant2) at (1, 1) {$\quadrant2$};
        \node (\quadrant3) at (1, 0) {$\quadrant3$};
        \draw [->] (\quadrant0) -- (\quadrant1);
        \draw [->] (\quadrant1) -- (\quadrant2);
        \draw [->] (\quadrant2) -- (\quadrant3);
      \end{scope}
    }
    \draw [->] (0, 1) -- (0, 2);
    \draw [->] (1, 2) -- (2, 2);
    \draw [->] (3, 2) -- (3, 1);
  \end{tikzpicture}

There is one real issue and a couple of code cleanliness issues:

  1. The arrows that go across different quadrants (the last three lines in the code) look ugly, as they are drawn between coordinates and not between nodes. I tried to draw it between nodes, with code like \draw [->] (03) -- (10); but I got error messages like "ERROR: Package pgf Error: No shape named 03 is known." So I guess that in the foreach loop, even when \quadrant has the value 0, the line \node (\quadrant3) at (1, 0) {$\quadrant3$}; either doesn't really create a node with name 03, or it's not accessible outside the loop. How do I use that node corresponding to 03, outside the loop?

  2. Is there a better way to draw the figure, than what I've done? (E.g. a better way to do the flip+rotate?)

  3. Inside the foreach loop, I've just prefixed \quadrant to each node in the code for the previous figure; is there a way of reusing that code (possibly writing it more generally in the first place, with prefix set to empty string) instead of repeating it?


The third iteration has four copies of the second iteration, and there are no new issues except that the number of ugly arrows is more now, and I had to essentially repeat all the code from the second iteration again (just prefixed q to most variable names).

Hilbert curve, iteration 3

  \begin{tikzpicture}
   \foreach \qquadrant / \qxscale / \qrotate / \qxshift / \qyshift in
       {0 / -1 / 90 / 0 / 0,
        1 / +1 / 00 / 0 / 4,
        2 / +1 / 00 / 4 / 4,
        3 / -1 / -90 / 7 / 3}   % (7, 3) = (3, 3) + (4, 0)
   {
    \begin{scope}[shift = {(\qxshift, \qyshift)}, xscale = \qxscale, rotate = \qrotate]
    \foreach \quadrant / \xscale / \rotate / \xshift / \yshift in
        {0 / -1 / 90 / 0 / 0,
         1 / +1 / 00 / 0 / 2,
         2 / +1 / 00 / 2 / 2,
         3 / -1 / -90 / 3 / 1}  % (3, 1) = (1, 1) + (2, 0): the former is just to rotate
    {
      \begin{scope}[shift = {(\xshift, \yshift)}, xscale = \xscale, rotate = \rotate]
        \node (\qquadrant\quadrant0) at (0, 0) {$\qquadrant\quadrant0$};
        \node (\qquadrant\quadrant1) at (0, 1) {$\qquadrant\quadrant1$};
        \node (\qquadrant\quadrant2) at (1, 1) {$\qquadrant\quadrant2$};
        \node (\qquadrant\quadrant3) at (1, 0) {$\qquadrant\quadrant3$};
        \draw [->] (\qquadrant\quadrant0) -- (\qquadrant\quadrant1);
        \draw [->] (\qquadrant\quadrant1) -- (\qquadrant\quadrant2);
        \draw [->] (\qquadrant\quadrant2) -- (\qquadrant\quadrant3);
      \end{scope}
    }
    \draw [->] (0, 1) -- (0, 2);
    \draw [->] (1, 2) -- (2, 2);
    \draw [->] (3, 2) -- (3, 1);
    \end{scope}
   }
   \draw [->] (0, 3) -- (0, 4);
   \draw [->] (3, 4) -- (4, 4);
   \draw [->] (7, 4) -- (7, 3);
  \end{tikzpicture}

I don't expect to draw figures beyond the third iteration (the horizontal arrows already have become pretty short because of the long node names anyway), and I'm willing to live with the code duplication, so just fixing the arrows for these three figures will be enough for me.


Edit: I was looking for a conventional programming solution, but thanks to the answers/comments, I've learned of Lindenmayer systems, which look extremely fascinating. I've accepted an answer, and hope to explore these systems in more detail.

Meanwhile, while trying to make a further minimal example out of the issue I was facing above, I figured out the answer myself. It turned out to be embarrasingly trivial: it had to do with the space between the numbers and the slash, in \foreach \quadrant / \xscale [...] in  {0 / -1 [...]. So the nodes inside the loop were being created with names like 0 3 rather than 03. Changing the 0 / etc. to 0/ etc. gives the following figure:

Hilbert curve, iteration 3, fixed

with the folowing code (which I now know how to write better, but keeping it similar to the above for contrast or rather similarity):

  \begin{tikzpicture}
   \foreach \qquadrant / \qxscale / \qrotate / \qxshift / \qyshift in
       {0/ -1 / 90 / 0 / 0,
        1/ +1 / 00 / 0 / 4,
        2/ +1 / 00 / 4 / 4,
        3/ -1 / -90 / 7 / 3}   % (7, 3) = (3, 3) + (4, 0)
   {
    \begin{scope}[shift = {(\qxshift, \qyshift)}, xscale = \qxscale, rotate = \qrotate]
    \foreach \quadrant / \xscale / \rotate / \xshift / \yshift in
        {0/ -1 / 90 / 0 / 0,
         1/ +1 / 00 / 0 / 2,
         2/ +1 / 00 / 2 / 2,
         3/ -1 / -90 / 3 / 1}  % (3, 1) = (1, 1) + (2, 0): the former is just to rotate
    {
      \begin{scope}[shift = {(\xshift, \yshift)}, xscale = \xscale, rotate = \rotate]
        \node (\qquadrant\quadrant0) at (0, 0) {$\qquadrant\quadrant0$};
        \node (\qquadrant\quadrant1) at (0, 1) {$\qquadrant\quadrant1$};
        \node (\qquadrant\quadrant2) at (1, 1) {$\qquadrant\quadrant2$};
        \node (\qquadrant\quadrant3) at (1, 0) {$\qquadrant\quadrant3$};
        \draw [->] (\qquadrant\quadrant0) -- (\qquadrant\quadrant1);
        \draw [->] (\qquadrant\quadrant1) -- (\qquadrant\quadrant2);
        \draw [->] (\qquadrant\quadrant2) -- (\qquadrant\quadrant3);
      \end{scope}
    }
    \draw [->] (\qquadrant03) -- (\qquadrant10);
    \draw [->] (\qquadrant13) -- (\qquadrant20);
    \draw [->] (\qquadrant23) -- (\qquadrant30);
    \end{scope}
   }
   \draw [->] (033) -- (100);
   \draw [->] (133) -- (200);
   \draw [->] (233) -- (300);
  \end{tikzpicture}
8

As Marc points out, Lindenmayer systems (section 37 "Lindenmayer System Drawing Library" in the 2.10 manual) can do it. However it requires a bit of fiddling to get the node text correct for which I use the base conversion stuff (section 64.4 "Base Conversion").

Note, however, that afew extra spaces creep in to the document from somewhere, and I'm not sure where.

\documentclass[border=0.125cm]{standalone}

\usepackage{tikz}
\usetikzlibrary{lindenmayersystems}

\newcount\hilbertnodecount
\newcount\hilbertnodepreviouscount

\pgfdeclarelindenmayersystem{hilbert curve}{
    % Symbol to initialise things
    \symbol{I}{\hilbertnodecount=0}
    % Symbol to draw node
    \symbol{X}{%
        \pgflsystemdrawforward%
        \node [every hilbert node/.try, hilbert node \the\hilbertnodecount/.try ] 
            (hilbert-\the\hilbertnodecount) {};
        \ifnum\hilbertnodecount>0\relax%
            \hilbertnodepreviouscount=\hilbertnodecount%
            \advance\hilbertnodepreviouscount by-1\relax%
            \path [hilbert node path/.try] (hilbert-\the\hilbertnodepreviouscount) -- (hilbert-\the\hilbertnodecount);
        \fi%
        \advance\hilbertnodecount by1%
    }
    % Symbol to turn left
    \symbol{+}{\pgflsystemturnright} 
    % Symbol to turn right
    \symbol{-}{\pgflsystemturnleft}
    % Initial rule (to reset \hilbertnodecount and draw first node)
    \rule{S -> IXA}
    % Rules to draw Hilbert curve
    \rule{A -> +BX-AXA-XB+}
    \rule{B -> -AX+BXB+XA-}
}

\makeatletter
% Need a teensy hack to get the order
\def\tikzlsystemorder{\pgf@lsystem@order}%
\makeatother

\tikzset{
    hilbert nodes/.style={
        lindenmayer system={hilbert curve, axiom=S, order=#1, angle=90},
        insert path={lindenmayer system}
    },
    hilbert step/.style={%
        /pgf/lindenmayer system/step=#1
    }
}




\tikzset{%
    every hilbert node/.style={
        draw=none,
        %minimum size=0.75cm, <- change minimum size
        %font=\tiny, <- change font
        execute at end node={% <- code for printing number
            % Get the number of digits
            \pgfmathparse{int(\tikzlsystemorder-1)}%
            \let\ndigits=\pgfmathresult%
            % Ensure result of base conversion are padded with digits%
            \pgfmathsetbasenumberlength{\ndigits}%
            % Convert the node number to base 4
            \pgfmathdectobase\n{\hilbertnodecount}{4}%
            \n%
        }
    },
    hilbert step=1cm,% <- distance between nodes
    hilbert node path/.style={draw, ->}% <- style for lines between nodes
}

\begin{document}
\begin{tabular}{c} %
\tikz[yscale=-1]\path [hilbert nodes=2]; \\[1cm]
\tikz[yscale=-1]\path [hilbert nodes=3]; \\[1cm]
\tikz[yscale=-1]\path [hilbert nodes=4]; 
\end{tabular}
\end{document}

enter image description here

  • Thanks for this, though I must confess I find this code harder to understand than mine (but naturally). Anyway, is it possible to make the output closer to the one in the question, so as to not have the boxes (the text is smaller, so it's harder to read)? I can't figure out where in the above code that is being set... – ShreevatsaR May 7 '13 at 8:37
  • The every hilbert node style is applied to every node with numbers, to change the font use the font key, to stop the border being drawn, comment out the draw key. You may or may not want to stop the node being enlarged to some minimum size, in which case comment out (or change) the minimum size key. – Mark Wibrow May 7 '13 at 9:12
  • This is wonderful, thanks... and after staring at the code a little bit, I even understand the code a little. :-) – ShreevatsaR May 7 '13 at 12:40
4

Here a solution based on this example of texample.net The code is not optimized as \foreach \i in {4,8,12,16} ... and I used too many counters :(

Update

I removed the \foreach \i in {4,8,12,16} ...

\documentclass{standalone}
\usepackage{tikz}

\pgfmathsetmacro\HilbertLastX{0}
\pgfmathsetmacro\HilbertLastY{0}

\newcounter{Order}
\newcounter{Num}
\newcounter{HilbertOrder}
\newcounter{GlobalHilbertOrder}

\tikzset{hilbert/.style={minimum height=1.5ex,minimum width=3ex,inner sep=0pt,outer sep=0pt,font=\tiny}}

\def\AddNewNode#1#2{%
\pgfmathsetmacro\HilbertLastX{\HilbertLastX+#1}
\pgfmathsetmacro\HilbertLastY{\HilbertLastY+#2}
\addtocounter{Num}{1}
\node[hilbert] (tmp) at (\HilbertLastX cm,\HilbertLastY cm) {};
\draw[red,->] (last) -- (tmp);
\pgfmathsetbasenumberlength{3}%
\pgfmathdectobase\mynumber{\theNum}{4}
\node[hilbert] (last) at (\HilbertLastX cm,\HilbertLastY cm) {\mynumber};
}%

\def\Hilbert[#1,#2,#3,#4,#5,#6,#7,#8] {
  \ifnum\value{HilbertOrder} > 0%
     \addtocounter{HilbertOrder}{-1}     
     \Hilbert[#5,#6,#7,#8,#1,#2,#3,#4]
     \AddNewNode {#1} {#2}
     \Hilbert[#1,#2,#3,#4,#5,#6,#7,#8]
     \AddNewNode {#5} {#6}
     \Hilbert[#1,#2,#3,#4,#5,#6,#7,#8]
     \AddNewNode {#3} {#4}
     \Hilbert[#7,#8,#5,#6,#3,#4,#1,#2]
     \addtocounter{HilbertOrder}{1}
     \addtocounter{GlobalHilbertOrder}{1}
      \ifnum\value{Order} >1
          \pgfmathparse{mod(\value{Order},4)}
          \ifdim\pgfmathresult pt =0pt \addtocounter{GlobalHilbertOrder}{-1}\fi
    \fi
      \addtocounter{Order}{1}
  \fi
}% 

\def\hilbert((#1,#2),#3){%
 \pgfmathsetmacro\HilbertLastX{\HilbertLastX+#1}
 \pgfmathsetmacro\HilbertLastY{\HilbertLastY+#2}
 \path (\HilbertLastX,\HilbertLastY);
 \setcounter{HilbertOrder}{#3}
 \Hilbert[1,0,-1,0,0,1,0,-1]
}%

\begin{document}
\parindent=0pt

\begin{tikzpicture}[node distance=0cm,every path/.style={thin}]
    \node[hilbert] (last) at (\HilbertLastX cm,\HilbertLastY cm) {000};
    \setcounter{GlobalHilbertOrder}{0}  \setcounter{Order}{0} \setcounter{Num}{0} 
    \hilbert((0mm,0mm),3);
\end{tikzpicture}

\end{document}

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.