CODEWITHSUNDEEP
python
Eli B
Eli B

Reputation: 51

Matplotlib Sierpinski Triangle

from tkinter import *
import timeit
import matplotlib.pyplot as plt
#------------------------------------------------------------------------
# ST_Recur
#------------------------------------------------------------------------
def midpoint(p1,p2):
    return ((p1[0]+p2[0])/2,(p1[1]+p2[1])/2)
def ST_Recur(level, p1, p2, p3):
    if level == 1:
        canvas.create_polygon(p1, p2, p3)
        canvas.update
    else:
        p4 = midpoint(p1, p2)
        p5 = midpoint(p2, p3)
        p6 = midpoint(p1, p3)
        ST_Recur(level - 1,p1,p4,p6)
        ST_Recur(level - 1,p4,p2,p5)
        ST_Recur(level - 1,p6, p5,p3)

#------------------------------------------------------------------------
# DrawSierpinskiTriangle
#------------------------------------------------------------------------
def DrawSierpinskiTriangle(event=None):
    global size
    level = int(levels.get())
    canvas.delete("all")
    p1 = (0.1*size, 0.9*size)   # bottom left
    p2 = (0.5*size, 0.1*size)   # top
    p3 = (0.9*size, 0.9*size)   # bottom right
    ST_Recur( level, p1, p2, p3)



#===================================================================================
root = Tk()
root.title("Sierpinski Triangle")

#---- entry box for level number
Label(root, text="Levels:").grid(row=1, column=1, sticky=W)
levels = StringVar()
levels_entry = Entry(root, width=7, textvariable=levels)
levels_entry.grid(row=1, column=2)

#---- button to draw
Button(root, text="Draw", command=DrawSierpinskiTriangle).grid(row=1, column=3)
#---- return key to draw
root.bind("<Return>", DrawSierpinskiTriangle)

#---- canvas to draw
size = 500
canvas = Canvas(root, width=size, height=size, borderwidth=1, highlightbackground='black', background='white')
canvas.grid(row=1, column=4)

#---- space out widgets
for child in root.winfo_children():
    child.grid_configure(padx=5, pady=5)

#---- start event loop
start = timeit.timeit()
a = ST_Recur
end = timeit.timeit()
print(start - end)

plt.plot(start - end)
plt.show()


root.mainloop()

Could someone please help me plot a graph of this Sierpinski Triangle program? I'm trying to determine whether or not the program is linear O(n^2) or exponential O(Logn). I'm unsure of how to integrate the ST_recure function and the running time into mat plot lib. The goal is to measure the running time and plot.

Upvotes: 0

Views: 1725

Answers (1)

Code-Apprentice
Code-Apprentice

Reputation: 83567

From comments:

the problem size is the number of levels to be drawn

This is a key detail. When we analyze an algorithm, we need a way to measure the "size" of different inputs. For your homework assignment, you need a loop of some kind that calls ST_Recur() with varying values of level. You also need to time each call and gather the data for level vs time it takes to run. Then you can graph that data in a line plot or something similar.

Upvotes: 1

Related Questions