Recurrency procedure for carpet

Question

I try defined recurrency procedure for this shape:

I know that if n==0 then we need plot square. But clockwise?

Next is plot smaller square, but I have a problem with a tour around the square. My procedure should be allowed for a variable number of stages.

Can you have an idea of how to define this procedure?

Answer 1

I have a way to do this without recursion, but again, I'm not sure if it meets the requirements of your assignment. This is far too complicated for me to type in a comment box, but it's a provisional answer only.

I would do it with a queue. First draw a square of side $S$, centered at the origin. Now for $n=0,1,2,3$ enqueue a record of the form $$\left(\frac S2, x_n, y_n, n, 2\right)$$ These are to be interpreted as $$(side,center_x, center_y, type, stage),$$ where $$x_n=\frac{3S\sqrt2}{4}\cos\left(\frac{n\pi}{2}+\frac{\pi}{4}\right)\\ y_n=\frac{3S\sqrt2}{4}\sin\left(\frac{n\pi}{2}+\frac{\pi}{4}\right) $$ Now, while the queue is not empty, do the following:

• Deque a record
• Draw the square
• If the next stage would exceed the limit, dequeue another record
• Otherwise, use the same sort of procedure to enqueue $3$ more records

In the last step, we reduce the current side by a factor of $2$ and increase the stage by $1$. We get the centers of the squares in much the same way as in the first step. First, pretend that the current square is centered at the origin, so we can use exactly the same formula. Then just add the $x$ and $y$ coordinates of the current center to the computed $x$ and $y$ coordinates.

The only wrinkle is that we don't add a square of the type opposite to the current type to the queue. (I made an earlier edit saying this is unnecessary, but I was wrong.)

Your computer graphics system may not allow for negative coordinates, but this is no problem. Just add the $x$ and $y$ coordinates of the first square to the $x$ and $y$ coordinates of the centers of the first $4$ squares in the queue.

Mathematically, it looks like this will draw the squares counter-clockwise, but since the $y$-coordinate in computer graphics increases as the point moves down, I believe this will draw them clockwise on the screen.

This should draw the big square, then the $4$ stage $2$ squares, then $3$ stage $3$ squares touching each stage $2$ square, and so on. When the stage $3$ squares are drawn, first $3$ will be drawn, in clockwise order, around one of the stage $2$ squares, then we will move clockwise to the next stage $2$ square and draw $3$ stage $3$ squares touching it, and so on.

This worked for me:

from math import sin, cos, sqrt, pi
import tkinter as tk
from argparse import ArgumentParser
from collections import namedtuple

Square = namedtuple('Square', 'side x y type stage'.split())

parser = ArgumentParser()
parser.add_argument('side', type=int, help='side of big sqaure in pixels')
parser.add_argument('stages', type=int, help='number of stages')
parser.add_argument('--color', help='string recognized by Tk', default='red')
args = parser.parse_args()

root=tk.Tk()
canvas = tk.Canvas(root, height=1000, width=1000)
canvas.pack()

x0,y0 = int(canvas['width'])//2, int(canvas['height'])//2

def drawSquare(side, x, y):
    canvas.create_rectangle(x-side//2,  y-side//2, x+side//2, y+side//2, fill = args.color, outline=args.color)

drawSquare(args.side, x0, y0)

Q = []
for n in range(4):
    theta = n*pi/2+pi/4
    r = 3*sqrt(2)*args.side/4
    x = x0+r*cos(theta)
    y = y0+r*sin(theta)
    Q.append(Square(side=args.side//2,x=x,y=y,type=n,stage=1))
while Q:
    sq = Q.pop(0)
    drawSquare(sq.side, sq.x, sq.y)
    stage = sq.stage+1
    if stage==args.stages:
        continue
    for n in range(4):
        if n == (sq.type+2)%4:
            continue
        theta = n*pi/2+pi/4
        r = 3*sqrt(2)*sq.side/4
        x = sq.x+r*cos(theta)
        y = sq.y+r*sin(theta)
        Q.append(Square(side=sq.side//2,x=x,y=y,type=n,stage=stage))        

root.mainloop()

With the arguments 200 5 this produced