I want to visualize an algorithm (Graham scan) in python with tkinter. I want to animate the algorithm and I am stuck.
I basically want to draw and delete lines but I don't understand canvas.after() well enough to make it work.
draw_line() returns the line object but when I call it in canvas.after(..., draw_line, ...) I don't see a way to get the return value or how to call another canvas.after() to change the color/delete that line if the function draw_line() hasn't been called yet because of the delay.
Thanks in advance.
from tkinter import *
import math
import random
class Point:
def __init__(self, _x, _y, _a=0):
self.x = _x
self.y = _y
self.angle = _a
def get_co(self):
return self.x, self.y
def draw_hull(hull):
for i in range(len(hull) - 1):
canvas.create_line(hull[i][0], hull[i][1], hull[i 1][0], hull[i 1][1], fill="red", width=2)
def draw_line(p1, p2, color="yellow"):
return canvas.create_line(p1.x, p1.y, p2.x, p2.y, fill=color, width=2)
def convex_hull(list_points):
# find bottom point
bottom_point = Point(math.inf, math.inf)
for point in list_points:
if point[1] < bottom_point.y:
bottom_point = Point(point[0], point[1])
# calculate angles between the bottom point and the other points
points = []
for point in list_points:
if point != bottom_point.get_co():
new_point = Point(point[0], point[1])
angle = calculate_angle(bottom_point, new_point)
new_point.angle = angle
points.append(new_point)
# sort the points by angle
swaps = None
while swaps != 0:
swaps = 0
for i in range(len(points) - 1):
point1 = points[i]
point2 = points[i 1]
if point1.angle > point2.angle:
points[i], points[i 1] = points[i 1], points[i]
swaps = 1
# go through the points and add them to the convex hull
# if the angle between 3 points ever exeeds 180 degrees, discard the middle point
hull = [bottom_point, points[0]]
i = 1
while i < len(points):
####### DRAW LINE #######
canvas.after(i*500, draw_line, hull[-2], hull[-1])
##############
# check angle
angle = calculate_angle(hull[-2], hull[-1], points[i])
if angle == -1:
########## DELETE LINE ##########
# change color of line to red and delete it a bit later
# canvas.itemconfig(line, fill="red")
# canvas.after(i*500 250, canvas.delete, line)
####################
# pop the point of the stack
hull.pop()
else:
########## CHANGE COLOR OF LINE ##########
# change color of line to green
# canvas.itemconfig(line, fill="green")
####################
# move to the next point
hull.append(points[i])
i = 1
# add bottom point again for loop
hull.append(bottom_point)
# give easy return list (with coordinate-tupels not class objects)
output = []
for point in hull:
output.append(point.get_co())
return output
def calculate_angle(point1, point2, point3=None):
if point3 is None:
if point2.x - point1.x == 0:
return 90
elif point2.x - point1.x > 0:
return math.degrees(math.atan((point2.y - point1.y)/(point2.x - point1.x)))
else:
return 180 - math.degrees(math.atan((point2.y - point1.y)/(point1.x - point2.x)))
else:
v1 = Point(point1.x - point2.x, point1.y - point2.y)
v2 = Point(point3.x - point2.x, point3.y - point2.y)
det = (v1.x * v2.y) - (v2.x * v1.y)
if det < 0:
return 1
else:
return -1
window = Tk()
window.geometry("1000x600")
canvas = Canvas(window, width=1000, height=600)
canvas.pack()
POINTSIZE = 2
points = []
for i in range(100):
x = random.randint(50, 950)
y = random.randint(50, 550)
points.append((x, y))
canvas.create_oval(x - POINTSIZE, y - POINTSIZE, x POINTSIZE, y POINTSIZE, fill="black")
hull = convex_hull(points)
# draw_hull(hull)
window.mainloop()
CodePudding user response：
If you have questions about the code, let me know. Because I dont know where to start to explain, since I made major changes to your code.
Anyway, I would be glad if you share your code again, once you are done with, on CodeReview and please do let me know. Because it was fun to work with and your code seems incomplete to me.
Happy Coding:
import tkinter as tk
import random
import math
class Point:
def __init__(self, _x, _y, _a=0):
self.x = _x
self.y = _y
self.angle = _a
return None
def get_co(self):
return self.x, self.y
class Window(tk.Tk):
def __init__(self,_w,_h):
super().__init__()
self.POINTSIZE = 2
self.points = []
self.swaps = None
self.count = 1
self.delay = 200
self.title('Graham scan simulation')
self.toolbar = tk.Frame(self,background='grey')
self.refresh_button = tk.Button(self.toolbar,text='Refresh',
command=self.refresh)
self.start_button = tk.Button(self.toolbar,text='Start',
command = self.convex_hull)
self.canvas = tk.Canvas(self,width=_w,height=_h)
self.toolbar.pack(side=tk.TOP,fill=tk.BOTH,expand=True)
self.refresh_button.pack(side=tk.LEFT)
self.start_button.pack(side=tk.LEFT)
self.canvas.pack(side=tk.BOTTOM,fill=tk.BOTH,expand=True)
def generate_points(self):
for point_instance in self.points:
yield point_instance
def find_bottom_point(self):
bottom_point = Point(math.inf,math.inf)
for point in self.generate_points():
if point.y < bottom_point.y:
bottom_point = point
return bottom_point
def calculate_angle(self,point1, point2):
if point2.x - point1.x == 0:
return 90
elif point2.x - point1.x > 0:
return math.degrees(math.atan((point2.y - point1.y)/(point2.x - point1.x)))
else:
return 180 - math.degrees(math.atan((point2.y - point1.y)/(point1.x - point2.x)))
def calculate_angels_by_bottom_point(self,bottom_point):
for point in self.generate_points():
if point != bottom_point:
angle = self.calculate_angle(bottom_point,point)
point.angle = angle
def sort_points(self,event_variable):
if self.swaps != 0:
self.swaps = 0
for i in range(len(self.points)-1):
point1 = self.points[i]
point2 = self.points[i 1]
if point1.angle > point2.angle:
self.points[i], self.points[i 1] = self.points[i 1], self.points[i]
self.swaps = 1
if self.swaps == 0:
event_variable.set(1)
self.after(20,self.sort_points,event_variable)
def check_angle(self,point1,point2,point3):
v1 = Point(point1.x - point2.x, point1.y - point2.y)
v2 = Point(point3.x - point2.x, point3.y - point2.y)
det = (v1.x * v2.y) - (v2.x * v1.y)
if det < 0:
return 1
else:
return -1
def draw_line(self,p1,p2,color='yellow'):
return self.canvas.create_line(p1.x,p1.y, p2.x,p2.y, fill='yellow',tags='line')
def clear_red_lines(self,p1,p2):
shapes = self.canvas.find_withtag('line')
for shape in shapes:
if self.canvas.itemcget(shape,'fill') == 'red':
coords = self.canvas.coords(shape)
overlapped = self.canvas.find_overlapping(*coords)
for i in overlapped:
coords2 = self.canvas.coords(i)
if coords == coords2:
self.canvas.delete(i)
self.canvas.delete(shape)
def animated_draw(self,hull):
if self.count != len(self.points):
line = self.draw_line(hull[-2],hull[-1])
check_mark = self.check_angle(hull[-2],hull[-1],self.points[self.count])
if check_mark == -1:
self.canvas.itemconfig(line,fill='red')
self.after(self.delay-100,lambda:self.clear_red_lines(hull[-2],hull[-1]))
hull.pop()
else:
self.canvas.itemconfig(line,fill='green')
hull.append(self.points[self.count])
self.count = 1
self.after(self.delay,self.animated_draw,hull)
def convex_hull(self):
bottom_point = self.find_bottom_point()
self.calculate_angels_by_bottom_point(bottom_point)
event_variable = tk.IntVar(self,value=0)
self.sort_points(event_variable)
self.wait_variable(event_variable)
self.points.pop(0)
self.animated_draw(hull = [bottom_point, self.points[0]])
def generate_listpoints(self,_amount):
'''using a generator for memory purpose'''
for i in range(_amount):
x = random.randint(50, 950)
y = random.randint(50, 550)
yield x,y
def refresh(self):
self.swaps = None
self.count = 1
self.points= []
self.populate_canvas()
def populate_canvas(self):
self.canvas.delete('all')
for x,y in self.generate_listpoints(100):
self.points.append(Point(x, y))#instead of creating throwing instances away.
self.canvas.create_oval(x - self.POINTSIZE,
y - self.POINTSIZE,
x self.POINTSIZE,
y self.POINTSIZE,
fill="black")
root = Window(1000,600)
root.mainloop()