TikZ-PGF – How to Create Iterations of the Sierpinski Carpet

diagramsfractalslindenmayertikz-pgf

What I want to do is create a sequence of iterations of the Sierpinski carpet. The Sierpinski carpet is created by dividing the square into nine congruent subsquares and removing the middle one, then then dividing the remaining subsquares into nine smaller subsquares and removing the middle one, then iterating the process.

I created the diagram below using tikz by drawing and, where necessary, filling each individual rectangle. However, this is a tedious and inefficient process, particularly as the next iteration would require an additional 512 white rectangles.

\begin{tikzpicture}
\fill (0, 0) rectangle (1, 1);
\begin{scope}[xshift = 1.5 cm]
\fill (0, 0) rectangle (1, 1);
\fill[color=white] (1/3, 1/3) rectangle (2/3, 2/3);
\end{scope}
\begin{scope}[xshift = 3 cm]
\fill (0, 0) rectangle (1, 1);
\fill[color=white] (1/3, 1/3) rectangle (2/3, 2/3);
\fill[color=white] (1/9, 1/9) rectangle (2/9, 2/9);
\fill[color=white] (4/9, 1/9) rectangle (5/9, 2/9);
\fill[color=white] (7/9, 1/9) rectangle (8/9, 2/9);
\fill[color=white] (1/9, 4/9) rectangle (2/9, 5/9);
\fill[color=white] (7/9, 4/9) rectangle (8/9, 5/9);
\fill[color=white] (1/9, 7/9) rectangle (2/9, 8/9);
\fill[color=white] (4/9, 7/9) rectangle (5/9, 8/9);
\fill[color=white] (7/9, 7/9) rectangle (8/9, 8/9);
\end{scope}
\begin{scope}[xshift = 4.5 cm]
\fill (0, 0) rectangle (1, 1);
\fill[color=white] (1/3, 1/3) rectangle (2/3, 2/3);
\fill[color=white] (1/9, 1/9) rectangle (2/9, 2/9);
\fill[color=white] (4/9, 1/9) rectangle (5/9, 2/9);
\fill[color=white] (7/9, 1/9) rectangle (8/9, 2/9);
\fill[color=white] (1/9, 4/9) rectangle (2/9, 5/9);
\fill[color=white] (7/9, 4/9) rectangle (8/9, 5/9);
\fill[color=white] (1/9, 7/9) rectangle (2/9, 8/9);
\fill[color=white] (4/9, 7/9) rectangle (5/9, 8/9);
\fill[color=white] (7/9, 7/9) rectangle (8/9, 8/9);
\fill[color=white] (4/81, 4/81) rectangle (5/81, 5/81);
\fill[color=white] (13/81, 4/81) rectangle (14/81, 5/81);
\fill[color=white] (22/81, 4/81) rectangle (23/81, 5/81);
\fill[color=white] (31/81, 4/81) rectangle (32/81, 5/81);
\fill[color=white] (40/81, 4/81) rectangle (41/81, 5/81);
\fill[color=white] (49/81, 4/81) rectangle (50/81, 5/81);
\fill[color=white] (58/81, 4/81) rectangle (59/81, 5/81);
\fill[color=white] (67/81, 4/81) rectangle (68/81, 5/81);
\fill[color=white] (76/81, 4/81) rectangle (77/81, 5/81);
\fill[color=white] (4/81, 13/81) rectangle (5/81, 14/81);
\fill[color=white] (22/81, 13/81) rectangle (23/81, 14/81);
\fill[color=white] (31/81, 13/81) rectangle (32/81, 14/81);
\fill[color=white] (49/81, 13/81) rectangle (50/81, 14/81);
\fill[color=white] (58/81, 13/81) rectangle (59/81, 14/81);
\fill[color=white] (76/81, 13/81) rectangle (77/81, 14/81);
\fill[color=white] (4/81, 22/81) rectangle (5/81, 23/81);
\fill[color=white] (13/81, 22/81) rectangle (14/81, 23/81);
\fill[color=white] (22/81, 22/81) rectangle (23/81, 23/81);
\fill[color=white] (31/81, 22/81) rectangle (32/81, 23/81);
\fill[color=white] (40/81, 22/81) rectangle (41/81, 23/81);
\fill[color=white] (49/81, 22/81) rectangle (50/81, 23/81);
\fill[color=white] (58/81, 22/81) rectangle (59/81, 23/81);
\fill[color=white] (67/81, 22/81) rectangle (68/81, 23/81);
\fill[color=white] (76/81, 22/81) rectangle (77/81, 23/81);
\fill[color=white] (4/81, 31/81) rectangle (5/81, 32/81);
\fill[color=white] (13/81, 31/81) rectangle (14/81, 32/81);
\fill[color=white] (22/81, 31/81) rectangle (23/81, 32/81);
\fill[color=white] (58/81, 31/81) rectangle (59/81, 32/81);
\fill[color=white] (67/81, 31/81) rectangle (68/81, 32/81);
\fill[color=white] (76/81, 31/81) rectangle (77/81, 32/81);
\fill[color=white] (4/81, 40/81) rectangle (5/81, 41/81);
\fill[color=white] (22/81, 40/81) rectangle (23/81, 41/81);
\fill[color=white] (58/81, 40/81) rectangle (59/81, 41/81);
\fill[color=white] (76/81, 40/81) rectangle (77/81, 41/81);
\fill[color=white] (4/81, 49/81) rectangle (5/81, 50/81);
\fill[color=white] (13/81, 49/81) rectangle (14/81, 50/81);
\fill[color=white] (22/81, 49/81) rectangle (23/81, 50/81);
\fill[color=white] (58/81, 49/81) rectangle (59/81, 50/81);
\fill[color=white] (67/81, 49/81) rectangle (68/81, 50/81);
\fill[color=white] (76/81, 49/81) rectangle (77/81, 50/81);
\fill[color=white] (4/81, 58/81) rectangle (5/81, 59/81);
\fill[color=white] (13/81, 58/81) rectangle (14/81, 59/81);
\fill[color=white] (22/81, 58/81) rectangle (23/81, 59/81);
\fill[color=white] (31/81, 58/81) rectangle (32/81, 59/81);
\fill[color=white] (40/81, 58/81) rectangle (41/81, 59/81);
\fill[color=white] (49/81, 58/81) rectangle (50/81, 59/81);
\fill[color=white] (58/81, 58/81) rectangle (59/81, 59/81);
\fill[color=white] (67/81, 58/81) rectangle (68/81, 59/81);
\fill[color=white] (76/81, 58/81) rectangle (77/81, 59/81);
\fill[color=white] (4/81, 67/81) rectangle (5/81, 68/81);
\fill[color=white] (22/81, 67/81) rectangle (23/81, 68/81);
\fill[color=white] (31/81, 67/81) rectangle (32/81, 68/81);
\fill[color=white] (49/81, 67/81) rectangle (50/81, 68/81);
\fill[color=white] (58/81, 67/81) rectangle (59/81, 68/81);
\fill[color=white] (76/81, 67/81) rectangle (77/81, 68/81);
\fill[color=white] (4/81, 76/81) rectangle (5/81, 77/81);
\fill[color=white] (13/81, 76/81) rectangle (14/81, 77/81);
\fill[color=white] (22/81, 76/81) rectangle (23/81, 77/81);
\fill[color=white] (31/81, 76/81) rectangle (32/81, 77/81);
\fill[color=white] (40/81, 76/81) rectangle (41/81, 77/81);
\fill[color=white] (49/81, 76/81) rectangle (50/81, 77/81);
\fill[color=white] (58/81, 76/81) rectangle (59/81, 77/81);
\fill[color=white] (67/81, 76/81) rectangle (68/81, 77/81);
\fill[color=white] (76/81, 76/81) rectangle (77/81, 77/81);
\end{scope}
\end{tikzpicture}

What I was hoping to do is adapt Jake's solution using lindenmayer systems to How to create a Sierpinski triangle in LaTeX? to a rectangle, as marsupilam did for a hexagon in Tikz Fractal – Sierpinski Hexagon.

I am aware that questions about generating a Sierpinski carpet have been asked previously. Mark Wibrow's answer to Generating a Sierpinski carpet with tikz does not use a lindenmayer system and causes my system to hang. Henri Menke's answer to Drawing a Simple Fractal in Tikz is beautiful, but it becomes quite small when I reduce the order of the fractal and sits on a vertex rather than a side. I wish to keep each iteration the same size, as shown above.

I suppose that if I set order=\level, I would want to set the \squarewidth=9^\level since each square is divided into nine squares and that I should set the angle=90 since each angle is a right angle. However, I am confused about how to adapt the rules for the symbols X and Y that Jake and marsupilam used in their answers to generate the patterns shown above.

Best Answer

Here is a macro that places white nodes at the appropriate locations.

\sierpinski[options]{levels}

The option I have in mind is scale=, but rotate= will work as well. Or xscale= if you want rectangles that aren't squares. Be sure to use transform shape.

\documentclass{article}

\usepackage{tikz}

\newcommand{\sierpinski}[2][]{\tikz[#1]{
  \draw[fill=black] rectangle(1,1);
    \foreach \n[evaluate=\n as \m using \n-1, evaluate=\n as \s using 1/3^\n, evaluate=\m as \p using 3^\m] in {1,...,#2}{
      \foreach \k[evaluate=\k as \x using (2*\k-1)/2/3^\m] in {1,...,\p}{
        \foreach \j[evaluate=\j as \y using (2*\j-1)/2/3^\m] in {1,...,\p}{
          \node[fill=white, minimum size=\s cm, inner sep=0] at (\x,\y){};
}}}}}

\begin{document}

\tikz{\draw[fill=black] rectangle(1,1);}\quad\sierpinski{1}\quad\sierpinski{2}\quad\sierpinski{3}\quad\sierpinski{4}

\end{document}

Here is \sierpinski[scale=3, transform shape]{5}, which is about all my machine can handle. It's O(9ⁿ), so prepare to wait.

Related Solutions

[Tex/LaTex] Drawing multiple iterations of cellular automatons inline, possibly with TikZ

EDIT: Added LuaTeX version

Probably not what is exactly wanted. Also somewhat crude, and slow. Using LuaTeX or PSTricks would be very good choice to speed this up. But I'm old fashioned and stuck in my ways, so...

\documentclass[tikz]{standalone}

\usepackage{tikz}

% Each cell is stored globally as a macro 
% for example \csname cell-glider-1-7\endcsname
\def\setcell#1#2#3{%
    \pgfmathparse{int(#2)}\let\cx=\pgfmathresult%
    \pgfmathparse{int(#3)}\let\cy=\pgfmathresult%
    \expandafter\xdef\csname cell-#1-\cx-\cy\endcsname%
}

% Cells are accessed by parsing #2 and #3 to integers
% and assigning the cell contents to the macro #4
\def\getcell#1#2#3#4{%
    \pgfmathparse{int(#2)}\let\cx=\pgfmathresult%
    \pgfmathparse{int(#3)}\let\cy=\pgfmathresult%
    \def\marshal{\xdef#4}%
    \marshal{\csname cell-#1-\cx-\cy\endcsname}%
}


% We flip the current from `current' to `next' 
% which is probably misleading. The texts can be
% any arbitrary string as long as they are different.
\def\currenttext{current}
\def\nexttext{next}

\let\currentgeneration=\currenttext
\let\nextgeneration=\nexttext

\def\switchgenerations{%
    \ifx\currentgeneration\currenttext%
        \global\let\currentgeneration=\nexttext%
        \global\let\nextgeneration=\currenttext%
    \else%
        \global\let\currentgeneration=\currenttext%
        \global\let\nextgeneration=\nexttext%
    \fi%
}

% Define colors \csname color-#1\endcsname
% Which can be used according to the cell contents
% So \csname color-0\endcsname holds the color for cells with value 0
\def\setcolor#1{\expandafter\xdef\csname color-#1\endcsname}
\def\getcolor#1{\csname color-#1\endcsname}


% Define a 10x10 board with a border of 1 so edge
% detection is not necessary.
\foreach \x in {0,...,11}{%
    \foreach \y in {0,...,11}{%
        \setcell{\currentgeneration}{\x}{\y}{0}%
    }% %
}%



% Copy this board for the next generation
% This is HUGELY inefficient. What would be better is
% to maintain a list of only changing cells (hard in LaTeX)
\foreach \x in {0,...,11}{%
    \foreach \y in {0,...,11}{%
        \setcell{\nextgeneration}{\x}{\y}{0}%
    }%
}
\newcount\neighbors

\def\updategenerations{%
\begingroup\nullfont% Hmm lots of unwanted spaces occur here
\foreach \x in {1,...,10}{%
    \foreach \y in {1,...,10}{%
        \getcell{\currentgeneration}{\x}{\y}{\n}%
        \getcell{\currentgeneration}{\x-1}{\y}{\a}%
        \getcell{\currentgeneration}{\x+1}{\y}{\b}%
        \getcell{\currentgeneration}{\x}{\y-1}{\c}%
        \getcell{\currentgeneration}{\x}{\y+1}{\d}%
        \getcell{\currentgeneration}{\x-1}{\y-1}{\e}%
        \getcell{\currentgeneration}{\x+1}{\y-1}{\f}
        \getcell{\currentgeneration}{\x-1}{\y+1}{\g}%
        \getcell{\currentgeneration}{\x+1}{\y+1}{\h}%
        \pgfmathsetcount\neighbors{\a+\b+\c+\d+\e+\f+\g+\h}%
        % Here are the neighbor rules
        \ifcase\neighbors %
            \setcell{\nextgeneration}{\x}{\y}{0}% 0 neighbors
        \or
            \setcell{\nextgeneration}{\x}{\y}{0}% 1 neighbors
        \or
            \ifnum\n=1\relax
            \setcell{\nextgeneration}{\x}{\y}{1}% 2 neighbors
            \fi
        \or
            \setcell{\nextgeneration}{\x}{\y}{1}% 3 neighbors
        \else
            \setcell{\nextgeneration}{\x}{\y}{0}% more than 3 neighbors
        \fi%    
    }%
}%
\endgroup%
\switchgenerations%
}



\def\drawcurrentgeneration{%}
\begin{tikzpicture}[x=10pt,y=10pt]
\foreach \x in {1,...,10}{%
    \foreach \y in {1,...,10}{%
        \setcell{\nextgeneration}{\x}{\y}{0}% Do here for a *minor* increment in speed
        \getcell{\currentgeneration}{\x}{\y}{\value}%
        \edef\c{\getcolor{\value}}%
        \fill [fill=\c](\x, \y) rectangle ++(1,1);
    }
}
\end{tikzpicture}%
}

\setcolor{0}{blue!5}
\setcolor{1}{blue!20}

\setcell{\currentgeneration}{1}{8}{1}
\setcell{\currentgeneration}{2}{8}{1}
\setcell{\currentgeneration}{3}{8}{1}
\setcell{\currentgeneration}{3}{9}{1}
\setcell{\currentgeneration}{2}{10}{1}


\begin{document}

\drawcurrentgeneration
\foreach \iteration in {1,...,28}{
    \updategenerations
    \drawcurrentgeneration
}

\end{document}

And here's how it could be done in LuaTeX:

\documentclass[tikz]{standalone}

\usepackage{tikz}

\directlua{
    function declareCells(n)
        MNew = {}
        for i = 0, n+1 do 
            MNew[i] = {}
            for j = 0, n+1 do
                MNew[i][j] = 0
            end
        end
        return MNew
    end
    function upDateCells(M, n)
        MNew = declareCells(n)
        for i = 1, n do 
            for j = 1, n do
                nb = - M[i][j]
                for ni = -1, 1 do
                    for nj = -1, 1 do
                        nb = nb + M[i+ni][j+nj]
                    end
                end
                if nb < 2 then
                    MNew[i][j] = 0
                elseif nb < 4 then
                    if M[i][j] == 1 then
                        MNew[i][j] = 1
                    elseif nb == 3 then
                        MNew[i][j] = 1
                    end
                else
                    MNew[i][j] = 0
                end
            end
        end
        return MNew
    end
}

\def\declarecells#1#2{
    \directlua{
        #1=declareCells(#2)
            #1size=#2
}}

\def\updatecells#1{
    \directlua{
        #1 = upDateCells(#1, #1size)
}}

\def\getcell#1#2#3#4{%
    \edef#4{\directlua{tex.print(#1[#2][#3])}}%
}

\def\setcell#1#2#3#4{%
    \directlua{#1[#2][#3]=#4}%
}


\def\setcolor#1{\expandafter\xdef\csname color-#1\endcsname}
\def\getcolor#1{\csname color-#1\endcsname}

\setcolor{0}{blue!5}
\setcolor{1}{blue!20}

\def\drawcells#1{%
    \edef\n{\directlua{tex.print(#1size)}}
    \begin{tikzpicture}[x=10pt,y=10pt]
        \foreach \x in {1,...,\n}{%
            \foreach \y in {1,...,\n}{%
                \getcell{#1}{\x}{\y}{\value}% 
                \edef\c{\getcolor{\value}}%
                \fill [fill=\c](\x, \y) rectangle ++(1,1);
            }
        }
        \end{tikzpicture}%
}

\begin{document}

\declarecells{glider}{10}
\setcell{glider}{1}{8}{1}
\setcell{glider}{2}{8}{1}
\setcell{glider}{3}{8}{1}
\setcell{glider}{3}{9}{1}
\setcell{glider}{2}{10}{1}

\drawcells{glider}
\foreach \iteration in {1,...,28}{
    \updatecells{glider}
    \drawcells{glider}
}

\end{document}

The result is the same as before.

enter image description here

[Tex/LaTex] Numerical conditional within tikz keys

I am definitely unfamiliar with both beamer and tikz (do not quite get what the \only are supposed to do) but perhaps this could go in the direction you want:

\documentclass{beamer}
\usepackage{tikz}
\usetikzlibrary{chains}
\newcounter{count}

% helper macro:
\long\def\GobToSemiColon #1;{}

\newcommand\myPicture{
\begin{tikzpicture}
  \begin{scope}[start chain = going below]
  \ifnum\value{count}<1 \expandafter\GobToSemiColon\fi
  \ifnum\value{count}>3 \expandafter\GobToSemiColon\fi
  \node[draw, rectangle, on chain] {display only when counter is between
    1 and 3};

  \ifnum\value{count}>-1 \expandafter\GobToSemiColon\fi
  \node[draw, rectangle, on chain] {display only when counter is
    negative}; 

  \ifnum\value{count}<100 \expandafter\GobToSemiColon\fi
  \ifnum\value{count}>200 \expandafter\GobToSemiColon\fi  
  \node[draw, rectangle, on chain] {display only if counter is between
    100 and 200};

  \ifnum\value{count}<3 \expandafter\GobToSemiColon\fi
  \ifnum\value{count}>20 \expandafter\GobToSemiColon\fi
  \node[draw, circle, on chain] {only when counter is in the range 3 to 20};
  \end{scope}
\end{tikzpicture}
}

\begin{document}
\begin{frame}
\only{\setcounter{count}{-3}\myPicture}
\only{\setcounter{count}{105}\myPicture}
\only{\setcounter{count}{39}\myPicture}
\only{\setcounter{count}{2}\myPicture}
\only{\setcounter{count}{5}\myPicture}
\end{frame}
\end{document}

beamer

Best Answer

Related Solutions

[Tex/LaTex] Drawing multiple iterations of cellular automatons inline, possibly with TikZ

[Tex/LaTex] Numerical conditional within tikz keys

Related Question