[Tex/LaTex] Drawing iterations of a recursive structure in TikZ / using node names defined in a loop

recursiontikz-pgf

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:

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?
Is there a better way to draw the figure, than what I've done? (E.g. a better way to do the flip+rotate?)
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}

Best Answer

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

Related Solutions

[Tex/LaTex] Rotate a node but not its content: the case of the ellipse decoration

The source of the difficulty is that ellipses are constructed in a particular way in TikZ. They are paths that start from the x-axis and proceed counter-clockwise around their centre. The vast majority of the time, the exact parametrisation doesn't matter. You appear to have found the one situation where it does!

In the actual question, you only want to be able to mirror the ellipse, and so draw it starting from the negative x-axis (the title of the question suggests a more flexible approach). That's actually not too hard since we can exploit the symmetry of the ellipse. The key is to provide it with a negative x-radius, since then it will start from the negative x-axis (and proceed clockwise, but we could correct for that by negating the y-radius as well). To do this, we interrupt the call from the node shape to the drawing command and flip the sign of the x-radius. The simplest way to do this is to redefine the \pgfpathellipse macro to do the negation and then call the original macro. The following code does this.

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{decorations,shapes,decorations.markings}
\makeatletter
\let\origpgfpathellipse=\pgfpathellipse
\def\revpgfpathellipse#1#2#3{%
  #2%
  \pgf@xa=-\pgf@x
  \origpgfpathellipse{#1}{\pgfqpoint{\pgf@xa}{0pt}}{#3}}
\makeatother

\tikzset{
  reversed ellipse/.style={
    ellipse,
    reverse the ellipse%
  },
  reverse the ellipse/.code={
    \let\pgfpathellipse=\revpgfpathellipse
  }
}
\begin{document}
\begin{tikzpicture}
\node[ellipse,
  draw,
  postaction={
    decorate,
    decoration={
      markings,
      mark=at position 1 with {
        \arrow[line width=5pt,blue]{>}
      }
    }
  }
] at (0,0) {hello world};

\node[reversed ellipse,
  draw,
  postaction={
    decorate,
    decoration={
      markings,
      mark=at position 1 with {
        \arrow[line width=5pt,blue]{>}
      }
    }
  }
] at (0,-2) {hello world};
\end{tikzpicture}

\end{document}

Here's the result:

rotated ellipse

(the arrow got clipped, but you can see where it lies)

[Tex/LaTex] TikZ: Using Loop to Draw Grid of Nodes

It's possible to use a minimum code

\documentclass{minimal}
\usepackage{tikz}

\begin{document}
\begin{tikzpicture}[darkstyle/.style={circle,draw,fill=gray!40,minimum size=20}]
  \foreach \x in {0,...,4}
    \foreach \y in {0,...,4} 
       {\pgfmathtruncatemacro{\label}{\x - 5 *  \y +21}
       \node [darkstyle]  (\x\y) at (1.5*\x,1.5*\y) {\label};} 

  \foreach \x in {0,...,4}
    \foreach \y [count=\yi] in {0,...,3}  
      \draw (\x\y)--(\x\yi) (\y\x)--(\yi\x) ;

\end{tikzpicture}
\end{document}

enter image description here

Only for information you can get the grid with tkz-berge

\documentclass[border=0.25cm]{standalone}
\usepackage{tkz-berge}

\begin{document}

 \begin{tikzpicture}
      \GraphInit[vstyle=Shade]
   \grGrid[Math,RA=2,RB=2]{5}{5}
 \end{tikzpicture}

\end{document}

enter image description here

Best Answer

Related Solutions

[Tex/LaTex] Rotate a node but not its content: the case of the ellipse decoration

[Tex/LaTex] TikZ: Using Loop to Draw Grid of Nodes

Related Question