import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

# Function to calculate cross product to check for counter-clockwise turn
def ccw(p1, p2, p3):
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])

# Graham Scan Algorithm
def graham_scan(points):
    # Find the point with the lowest y-coordinate (and leftmost if tie)
    P0 = min(points, key=lambda p: (p[1], p[0]))
    points = sorted(points, key=lambda p: (np.arctan2(p[1]-P0[1], p[0]-P0[0]), -np.hypot(p[0]-P0[0], p[1]-P0[1])))
    
    # Initialize stack with the first two points
    stack = [P0]
    steps = [stack.copy()]

    for point in points:
        while len(stack) > 1 and ccw(stack[-2], stack[-1], point) <= 0:
            stack.pop()
            steps.append(stack.copy())
        stack.append(point)
        steps.append(stack.copy())
    
    return stack, steps

# Generate random points
np.random.seed(42)
num_points = 20
points = np.random.rand(num_points, 2) * 10

# Perform Graham Scan and record steps
hull, steps = graham_scan(points)

# Set up the figure and axis for animation
fig, ax = plt.subplots()
ax.set_xlim(0, 10)
ax.set_ylim(0, 10)
ax.set_xticks([])
ax.set_yticks([])
# ax.set_title("Graham's Scan Algorithm")

# Plot points
ax.scatter(points[:, 0], points[:, 1], color='blue')

# Initialize the line for the hull
hull_line, = ax.plot([], [], color='red', lw=2)

# Animation function
def update(frame):
    step = steps[frame]
    hull_line.set_data([p[0] for p in step] + [step[0][0]], 
                       [p[1] for p in step] + [step[0][1]])
    return hull_line,

# Create the animation
ani = FuncAnimation(fig, update, frames=len(steps), interval=100, repeat=False)

if True:
    # save it as mp4
    ani.save('graham-scan.mp4', writer='ffmpeg', fps=5)

plt.show()