Riempire un poligono con bubble sort in Python

bubble-fill.py

import tkinter as tk

# Funzione per disegnare un poligono
def draw_polygon(canvas, vertices):
    canvas.create_polygon(vertices, outline='black', fill='')

# Funzione Bubble Sort per ordinare le intersezioni lungo l'asse x
def bubble_sort(canvas, intersections):
    n = len(intersections)
    for i in range(n):
        for j in range(0, n-i-1):
            if intersections[j][0] > intersections[j+1][0]:
                intersections[j], intersections[j+1] = intersections[j+1], intersections[j]
                print ("swap ",intersections[j][0], intersections[j+1][0])
                # Disegna il testo "Bubble Sort" nel canvas
                canvas.create_text(15, 15, anchor="nw", text="Riempire un poligono con Bubble Sort", fill="blue")
                canvas.update()

# Funzione per riempire il poligono
def fill_polygon(canvas, vertices, delay=1):
    # Calcolo del range verticale del poligono
    min_y = min(vertices, key=lambda vertex: vertex[1])[1]
    max_y = max(vertices, key=lambda vertex: vertex[1])[1]
    # min_x = min(vertices, key=lambda vertex: vertex[0])[0]
    # max_x = max(vertices, key=lambda vertex: vertex[0])[0]

    # # Disegno delle linee orizzontali e verticali per evidenziare le variabili min e max
    # canvas.create_line(min_x, min_y, max_x, min_y, fill='blue', width=2)  # Linea orizzontale per min_y
    # canvas.create_line(min_x, max_y, max_x, max_y, fill='blue', width=2)  # Linea orizzontale per max_y
    # canvas.create_line(min_x, min_y, min_x, max_y, fill='green', width=2)  # Linea verticale per min_x
    # canvas.create_line(max_x, min_y, max_x, max_y, fill='green', width=2)  # Linea verticale per max_x

    # Disegno del poligono
    draw_polygon(canvas, vertices)

    # Iterazione attraverso le scanline verticali
    for y in range(min_y, max_y + 1):
        print ("scanline y=",y)
        # Lista per memorizzare le intersezioni con la scanline
        intersections = []

        # Iterazione attraverso i lati del poligono
        for i in range(len(vertices)):
            p1 = vertices[i]
            p2 = vertices[(i + 1) % len(vertices)]
            
            # Controllo se il lato attraversa la scanline corrente
            if p1[1] < y <= p2[1] or p2[1] < y <= p1[1]:
                # Calcolo della coordinata x dell'intersezione con la scanline
                x_intersection = p1[0] + (y - p1[1]) * (p2[0] - p1[0]) / (p2[1] - p1[1])
                # Aggiunta dell'intersezione come coppia (x, y) alla lista
                intersections.append((x_intersection, y))

        print("intersections prima: ", intersections)
        # Ordinamento delle intersezioni lungo l'asse x utilizzando Bubble Sort
        bubble_sort(canvas, intersections)
        print("intersections dopo: ", intersections)

        # Disegno delle linee orizzontali tra le intersezioni
        for i in range(0, len(intersections), 2):
            x_start = int(intersections[i][0])
            x_end = int(intersections[i + 1][0])

            # Disegno della linea orizzontale sul canvas
            for x in range(x_start, x_end + 1):
                canvas.create_rectangle(x, y, x+1, y+1, outline='', fill='black')
                canvas.update()
                canvas.after(delay)
        
        print (intersections)

# Creazione della finestra e del canvas
root = tk.Tk()
canvas = tk.Canvas(root, width=400, height=400)
canvas.pack()

# Definizione dei vertici del poligono
vertices = [(50, 50), (200, 100), (150, 200), (100, 150)]

# Riempimento del poligono con ritardo
fill_polygon(canvas, vertices)

root.mainloop()