How to create iterations of the Sierpinski carpet

Question

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.

Answer 1

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.

Answer 2

with an up-to-date https://ctan.org/pkg/pst-fractal and running lualatex :

\documentclass[pstricks]{standalone}
\usepackage{pst-fractal} 
\begin{document}    

\begin{pspicture}(18,3)
\multido{\iA=1+1,\iB=0+12}{6}{%
  \psSierCarpet[scale=0.25,n=\iA](\iB,0.2)}
\end{pspicture}

\end{document}

and with option basecolor=red,linecolor=blue:

Answer 3

You have gotten the tikz answer you were looking for, so I feel free to add an answer made with MetaPost/MetaFun. Probably the code can be optimized, and probably one can do something similar with tikz (but I cannot). The first version draws a square and loops and unfills the parts that should be white. The second uses recursion.

Regarding the timing:

First version: 2.9s
Second version: 1.8s

I have wrapped it into MetaPost pages in ConTeXt lmtx. The file can be compiled with context.

\starttext
\startMPpage[offset=1dk]
vardef sierpinski(expr w, n) =
image(
fill unitsquare scaled w ;
for i = 1 upto n :
    for j = 1 upto (3^(i-1)) :
        for k = 1 upto (3^(i-1)) :
            unfill unitsquare scaled (w/(3^i)) shifted ( (3*j-2)*w/(3^i), (3*k-2)*w/(3^i) ) ;
        endfor
    endfor
endfor)
enddef ;

for i = 1 upto 3 :
    draw sierpinski(3cm,i)   shifted (4*(i-1)*cm,  0  ) ;
    draw sierpinski(3cm,i+3) shifted (4*(i-1)*cm, -4cm) ;
endfor ;
\stopMPpage

\startMPpage[offset=1dk]
vardef Sierpinski(expr w,n) =
    save tmppic ;
    picture tmppic ;
    if n = 1 :
        image(
        fill unitsquare scaled w ;
        unfill unitsquare scaled (w/3) shifted (w/3,w/3) ;
        )
    else :
        tmppic := Sierpinski(w, n - 1) scaled 1/3 ;
        image(
        for i = 1 upto 3 :
            for j = 1 upto 3 :
                if ((i*j) <> 4) :
                    draw tmppic shifted (((i-1)/3)*w,((j-1)/3)*w) ;
                fi
            endfor
        endfor
        ) 
    fi
enddef ;

for i = 1 upto 3 :
    draw Sierpinski(3cm,i)   shifted (4*(i-1)*cm,  0  ) ;
    draw Sierpinski(3cm,i+3) shifted (4*(i-1)*cm, -4cm) ;
endfor ;
\stopMPpage
\stoptext

The output looks the same in both variants (as far as I can see), so I only show one of them.

Answer 4

Optimized PGF placing white rectangles.

Here's a PGF version of Sandy G's TikZ nodes-based solution.

A few ideas to further speed up the process:

• No evaluate key from \foreach since it it adds parsing overhand

• Using \inteval (eTeX integer mathematics) that should be faster than PGFmath.

• Using quick versions of a few PGFmath functions.

• Using quick versions of \pgfqpointxy.

• Using quick version \pgfusepathqfill.

  We could probably also add quick versions of \pgfpointadd or something like \inteval for decimal values. (I'm just drawing a rectangle from (\x-\s, \x-\s) to (\x+\s, \x+\s) after all.)

(There are also lightweight loop implementation available but I don't know how much they actually add to the compilation time.)

That said, as with Sandy G's solution, this draws white rectangles where you don't actually need one. I'm not a mathematician but there's probably a formula to skip those (but then we already calculated \x and possibly \y).

Either way, since TeX breaks down with \sirpinksiPGFpicture{6} we can create a 6-leveled picture by just placing eight 5s in a matrix. (Which is the first step of the recursion.)

Code

\documentclass{article}
\usepackage{pgf,pgffor}
\def        \pgfmathqint#1.#2\relax{#1} % not really PGFmath
\newcommand*\pgfmathqdouble[2]{\edef#1{\the\numexpr2*#2\relax}}%
\makeatletter
\newcommand*\pgfmathqpow[3]{%
  \pgfmathpow@{#2}{#3}\edef#1{\expandafter\pgfmathqint\pgfmathresult\relax}}
\makeatother
\newcommand*\sirpinksiPGFpicture[2][1cm]{%
\pgfpicture
  \pgfsetxvec{\pgfqpoint{#1}{0pt}}
  \pgfsetyvec{\pgfqpoint{0pt}{#1}}
  \pgfsetbaselinepointnow{\pgfqpointxy{.5}{.5}}% for tabular solution
  \pgfpathrectangle{\pgfpointorigin}{\pgfqpointxy{1}{1}}
  \pgfusepathqfill
  \foreach \n in {1,...,#2}{
    \edef\m{\the\numexpr\n-1\relax}
    \pgfmathqpow\p{3}{\m}
    \pgfmathqdouble\pDoubled{\p}%
    \pgfmathsetmacro\s{.5/3^\n}
    \foreach \k in {1,...,\p}{
      \pgfmathsetmacro\x{(2*\k-1)/\pDoubled}
      \foreach \j in {1,...,\p}{
        \pgfmathsetmacro\y{(2*\j-1)/\pDoubled}
        \pgfpathrectanglecorners
          {\pgfpointadd{\pgfqpointxy{\x}{\y}}{\pgfqpointxy{-\s}{-\s}}}
          {\pgfpointadd{\pgfqpointxy{\x}{\y}}{\pgfqpointxy{\s}{\s}}}}}}
  \pgfsetfillcolor{white}
  \pgfusepathqfill
\endpgfpicture}
\begin{document}
\centering
\foreach \N in {1,...,5} {\sirpinksiPGFpicture[.19\linewidth]{\N} }

\vspace{5ex}
% save the picture for level 5 in a box
% this makes it easy to reuse it without
% PGF having to recalculate it over and over again
\newsavebox\sirpAtFive
\savebox\sirpAtFive{\sirpinksiPGFpicture[.333\linewidth]{5}}%
\begin{tabular}{@{}c@{}c@{}c@{}}
  \usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
  \usebox\sirpAtFive &                      &   \usebox\sirpAtFive \\
  \usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
\end{tabular}
\end{document}

Output

TikZ/PGFkeys with recursion

A TikZ/PGFkeys based solution that uses recursion and the even odd rule on only one path!

This only places those “white” rectangles that are actually needed. However, it doesn't actually fill them with white but cuts them out from the base rectangle.

The most important handler here is scoped since it places everything in a group.

There's also a solution that creates level-dependent carpet/split <level> styles that restore the values from before but both break down when used as startCarpet = 6.

It looks like that's just the limit of TeX/PGF/TikZ even when using PGF, no PGFkeys and not everything on one single path.

---

We can also draw a bunch of boxes (similar to my \fbox version) instead of filling an area which just needs a few adjustments but this also doesn't work anymore with level 6.

Of course, as with the PGF version you can use a box:

\newsavebox\sirpAtFive
\savebox\sirpAtFive{\tikz[baseline={(.5,.5)},x=.3333\linewidth,y=.3333\linewidth]{
   \fill[even odd rule] (-.5,-.5) rectangle +(1,1) [startCarpet={5}];}}%
\begin{tabular}{@{}c@{}c@{}c@{}}
  \usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
  \usebox\sirpAtFive &                      &   \usebox\sirpAtFive \\
  \usebox\sirpAtFive &   \usebox\sirpAtFive &   \usebox\sirpAtFive \\
\end{tabular}

However, TeX broke down again when I'm trying to place this on the same page as the other five.

Code

\documentclass[varwidth]{standalone}
\usepackage{tikz}
\makeatletter
\pgfqkeys{/handlers}{
  .scoped/.code=\begingroup\pgfkeys@exp@call{#1}\endgroup,
  .--/.code=% decrements a value (only TeX integers!)
    \pgfkeyssetevalue{\pgfkeyscurrentpath}
      {\the\numexpr\pgfkeysvalueof{\pgfkeyscurrentpath}-1\relax},
  .value/.code=% copies the value of one key to another w/o expanding it
    \pgfkeysgetvalue{#1}\pgfkeys@temp
    \expandafter\pgfkeys@exp@call\expandafter{\pgfkeys@temp},
  /utils/TeX/ifnum/.code n args={3}{% \usetikzlibrary{ext.misc}
    \ifnum#1\relax\expandafter\pgfutil@firstoftwo\else
    \expandafter\pgfutil@secondoftwo\fi{\pgfkeysalso{#2}}{\pgfkeysalso{#3}}}}
\makeatother
\tikzset{
  startCarpet/.style={% initialize
    carpet/shiftWidth/.initial=1, carpet/drawWidth/.initial=.3333,
    carpet/level/.initial/.expanded={#1}, carpet/do},% and go!
  carpet/do/.style={%
    carpet/place,% level = 1? Stop recursion and do nothing more
    /utils/TeX/ifnum={\pgfkeysvalueof{/tikz/carpet/level}=1}{}{%
      carpet/level/.--, % level = level - 1
      carpet/shiftWidth/.value=/tikz/carpet/drawWidth,
      carpet/drawWidth/.evaluated=\pgfkeysvalueof{/tikz/carpet/drawWidth}/3,
      carpet/split/.scoped/.list={-+, {0*}+, ++, -{0*}, +{0*}, --, {0*}-, +-}}},
  carpet/split/.style 2 args={% #1 = x-prefix, #2 = y-prefix
    shift={(#1\pgfkeysvalueof{/tikz/carpet/shiftWidth},
            #2\pgfkeysvalueof{/tikz/carpet/shiftWidth})},
    carpet/do},
  carpet/place/.default=\pgfkeysvalueof{/tikz/carpet/drawWidth},
  carpet/place/.style={insert path={(-#1/2, -#1/2) rectangle +(#1,#1)}}}
\begin{document}
\foreach \N in {1,...,5}
  \space\tikz[x=.19\linewidth,y=.19\linewidth]
   \fill[even odd rule] (-.5,-.5) rectangle +(1,1) (0,0) [startCarpet={\N}];
\end{document}

Answer 5

Here's a pure LaTeX and recursion version.

This obviouly only works because youre using rectangles (which are very easily placed with a tabular).

Code

\documentclass{article}
\newcommand*\startCarpet[2][1em]{{%
  \renewcommand*\arraystretch{0}%
  \setlength\fboxsep{0pt}\setlength\fboxrule{#1}%
  \edef\BOX{\noexpand\fbox{%
    \noexpand\rule[-\the\dimexpr#1/2\relax]{0pt}{#1}\noexpand\rule{#1}{0pt}}}%
  \def\TAB##1{\tabular{@{}c@{}c@{}c@{}}##1&##1&##1\\##1&&##1\\##1&##1&##1\endtabular}%
  \def\level{#2}%
  \def\doCarpet{%
    \ifnum\level=0
      \def\next{\TAB{\BOX}}%
    \else
      \def\next{%
        \edef\level{\inteval{\level-1}}%
        \TAB{\doCarpet}}%
    \fi
    \next}
  \doCarpet}}
\begin{document}
\centering
\startCarpet{0}
\startCarpet[.3333em]{1}
\startCarpet[.1111em]{2}

\startCarpet[.117em]{3}
\end{document}

Output