How to write python code to plot the process of the Euclidean algorithm on a rectangle

Question

I am a new coder and want to write some code to plot various rectangles in matplotlib, taking the animation from this link to demonstrate continued fractions. Namely, I am trying to write a function that takes the width and height of a rectangle and plots the rectangle along with lines to demonstrate this euclidean tiling process (starting with squares equal in side length to the width of the original rectangle, and then doing the same process recursively with the smaller rectangle that's left over).

I tried writing the following code:

import matplotlib.pyplot as plt

def draw_squares_on_rectangle(width, height, ax=None, leftover_x=0, leftover_y=0, leftover_width=None, leftover_height=None):
    if ax is None:
        fig, ax = plt.subplots()
        ax.set_aspect('equal', adjustable='box')
        plt.xlim([0, width])
        plt.ylim([0, height])

    if leftover_width is None:
        leftover_width = width
    if leftover_height is None:
        leftover_height = height

    square_size = min(width, height)
    if square_size >= 1:
        x = 0
        y = 0
        while x + square_size <= width and y + square_size <= height:
            rect = plt.Rectangle((x, y), square_size, square_size, fill=False)
            ax.add_patch(rect)
            if x + square_size == width:
                x = 0
                y += square_size
            else:
                x += square_size

        leftover_width = width - x
        leftover_height = height - y
        if leftover_width > 0 and leftover_height > 0:
            if leftover_width > leftover_height:
                draw_squares_on_rectangle(leftover_width, square_size, ax, leftover_x+x, leftover_y, leftover_width, square_size)
                draw_squares_on_rectangle(width - leftover_width, leftover_height, ax, leftover_x, leftover_y+y, width - leftover_width, leftover_height)
            else:
                draw_squares_on_rectangle(square_size, leftover_height, ax, leftover_x, leftover_y+y, square_size, leftover_height)
                draw_squares_on_rectangle(leftover_width, height - leftover_height, ax, leftover_x+x, leftover_y, leftover_width, height - leftover_height)

    if leftover_width == leftover_height == 1:
        return

    if leftover_width == 1 and leftover_height > 1:
        draw_squares_on_rectangle(1, leftover_height, ax, leftover_x, leftover_y, 1, leftover_height)
    elif leftover_height == 1 and leftover_width > 1:
        draw_squares_on_rectangle(leftover_width, 1, ax, leftover_x, leftover_y, leftover_width, 1)

    if ax is None:
        plt.show()

However, this seems only to perform the first 'square-tiling' step without the recursion. Can anyone help me out? Thank you

score 1 · Accepted Answer · answered Mar 27 '23 at 18:30

Here is an example of a possible direction you could take to solve that problem. The idea is to keep tiling the rectangle until the remaining area is smaller than a certain percentage of the original area (variable thresh in my code). This leftover area being smaller than the threshold will be your stop criteria for the recursion. The idea then is to tile the rectangle until the threshold is reach and add the patches in a list of patches. You can then design an animation with FuncAnimation (doc here), by adding each patch to the figure at each iteration. See code below:

import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
import matplotlib.animation as animation
import numpy as np

fig,ax=plt.subplots(figsize=(20,20))

w0=0.28 #width 0.32
h0=0.745 #height
x0=0.5-w0/2 #x value for origin
y0=0.1 #y value for origin

d0=0 #orignal depth of the process
or_area0=h0*w0 #original area of rectangle
left_area0=h0*w0 #original left over area of rectangle

# Setting up plot
rect=Rectangle((x0,y0), w0, h0,edgecolor='k',facecolor='w',lw=3) #create patch for original rectangle
plt.box(False)
ax.set_xticks([])
ax.set_yticks([])
ax.set_xlim([0,1])
ax.set_ylim([0,1])
ax.set_aspect('equal')
# create colormap
colors=plt.cm.tab20(np.linspace(0,1,20))

#create list of patch and append the original rectangle
r_l=[]
r_l.append(rect)
def rec_rect(x,y,w,h,d,left_area,or_area,thresh):
  if left_area>thresh*or_area/100.: #check if the leftover area is less than thresh percent of the original area
    n=0
    if h<w: #check if the height is bigger than the width
      while n*h<w-h:
        r_l.append(Rectangle((x+n*h,y),h,h,edgecolor='k',facecolor=colors[d],lw=3))
        n+=1
      d+=1
      left_area=(w-n*h)*h #compute leftover area 
      rec_rect(x+n*h,y,w-n*h,h,d,left_area,or_area,thresh) #call the function again with updated rectangle
    else:
      while n*w<h-w:
        r_l.append(Rectangle((x,y+n*w),w,w,edgecolor='k',fc=colors[d],lw=3))
        n+=1
      d+=1
      left_area=w*(h-n*w)  #compute leftover area 
      rec_rect(x,y+n*w,w,h-n*w,d,left_area,or_area,thresh) #call the function again with updated rectangle

rec_rect(x0,y0,w0,h0,d0,left_area0,or_area0,0.01) #calling tiling function

def update(i):
  ax.add_patch(r_l[i])

ani=animation.FuncAnimation(fig,update,frames=len(r_l),interval=1000)
plt.show()

How to write python code to plot the process of the Euclidean algorithm on a rectangle

1 Answers1