import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon
import random

# Genetic Algorithm Parameters
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
NUM_VERTICES = 30  # Number of vertices in the polygon

# Helper Functions
def generate_initial_population():
    population = []
    for _ in range(POPULATION_SIZE):
        # Random angles between 0 and 2*pi, sorted to ensure consistent vertex ordering
        angles = np.sort(np.random.uniform(0, 2 * np.pi, NUM_VERTICES))
        # Random radii, normalized to have perimeter 1
        radii = np.random.uniform(0.1, 1.0, NUM_VERTICES)
        shape = np.column_stack((radii * np.cos(angles), radii * np.sin(angles)))
        population.append(shape)
    return population

def calculate_perimeter(shape):
    perimeter = 0
    for i in range(len(shape)):
        perimeter += np.linalg.norm(shape[i] - shape[i - 1])
    return perimeter

def normalize_shape(shape):
    perimeter = calculate_perimeter(shape)
    if perimeter == 0:
        return shape
    return shape / perimeter

def calculate_area(shape):
    # Using Shoelace formula
    x = shape[:, 0]
    y = shape[:, 1]
    return 0.5 * np.abs(np.dot(x, np.roll(y, 1)) - np.dot(y, np.roll(x, 1)))

def fitness(shape):
    return calculate_area(shape)

def selection(population):
    # Sort population based on fitness (descending)
    sorted_population = sorted(population, key=lambda x: fitness(x), reverse=True)
    # Select top 50%
    return sorted_population[:POPULATION_SIZE // 2]

def crossover(parent1, parent2):
    # Single point crossover
    point = random.randint(1, NUM_VERTICES - 1)
    child1 = np.vstack((parent1[:point], parent2[point:]))
    child2 = np.vstack((parent2[:point], parent1[point:]))
    return child1, child2

def mutate(shape):
    for i in range(NUM_VERTICES):
        if random.random() < MUTATION_RATE:
            # Small perturbation
            delta_radius = np.random.normal(0, 0.05)
            delta_angle = np.random.normal(0, 0.1)
            r = np.linalg.norm(shape[i])
            theta = np.arctan2(shape[i,1], shape[i,0])
            r = max(0.1, r + delta_radius)  # Prevent radius from becoming too small
            theta = (theta + delta_angle) % (2 * np.pi)
            shape[i] = [r * np.cos(theta), r * np.sin(theta)]
    return shape

def create_next_generation(selected_population):
    next_generation = selected_population.copy()
    while len(next_generation) < POPULATION_SIZE:
        parent1, parent2 = random.sample(selected_population, 2)
        child1, child2 = crossover(parent1, parent2)
        child1 = mutate(child1)
        child2 = mutate(child2)
        child1 = normalize_shape(child1)
        child2 = normalize_shape(child2)
        next_generation.extend([child1, child2])
    return next_generation[:POPULATION_SIZE]

def genetic_algorithm():
    population = generate_initial_population()
    best_shape = None
    best_fitness = -1
    fitness_history = []
    best_shapes_at_intervals = {}  # To store best shapes at every 100th generation
    max_diff = 0
    generation_of_max_diff = 0
    previous_best_fitness = None
    # Store best shapes for max fitness difference
    shape_before_max_diff = None
    shape_at_max_diff = None

    for generation in range(1, GENERATIONS + 1):
        # Normalize all shapes
        population = [normalize_shape(shape) for shape in population]

        # Evaluate fitness
        fitness_values = [fitness(shape) for shape in population]
        generation_best_fitness = max(fitness_values)
        generation_best_shape = population[np.argmax(fitness_values)]

        # Calculate fitness difference
        if previous_best_fitness is not None:
            fitness_diff = abs(generation_best_fitness - previous_best_fitness)
            if fitness_diff > max_diff:
                max_diff = fitness_diff
                generation_of_max_diff = generation
                shape_before_max_diff = best_shape.copy() if best_shape is not None else None
                shape_at_max_diff = generation_best_shape.copy()
        previous_best_fitness = generation_best_fitness

        # Update global best if current is better
        if generation_best_fitness > best_fitness:
            best_fitness = generation_best_fitness
            best_shape = generation_best_shape.copy()

        fitness_history.append(best_fitness)

        # Check if current generation is a 100th generation
        if generation % 100 == 0:
            best_shapes_at_intervals[generation] = best_shape.copy()
            print(f"Generation {generation}: Best Fitness = {best_fitness:.6f}")

        # Selection
        selected = selection(population)

        # Create next generation
        population = create_next_generation(selected)

    return best_shape, fitness_history, best_shapes_at_intervals, max_diff, generation_of_max_diff, shape_before_max_diff, shape_at_max_diff

def plot_shape(shape, title="Shape"):
    plt.figure(figsize=(6,6))
    polygon = Polygon(shape, closed=True, fill=True, edgecolor='r', alpha=0.5)
    plt.gca().add_patch(polygon)
    plt.xlim(-1.5, 1.5)
    plt.ylim(-1.5, 1.5)
    plt.gca().set_aspect('equal', adjustable='box')
    plt.title(title)
    plt.show()

def plot_fitness_history(fitness_history):
    plt.figure(figsize=(10,5))
    plt.plot(fitness_history)
    plt.xlabel('Generation')
    plt.ylabel('Best Fitness (Area)')
    plt.title('Fitness Evolution')
    plt.grid(True)
    plt.show()

def plot_selected_shapes(best_shapes_at_intervals):
    num_plots = len(best_shapes_at_intervals)
    cols = 2 if num_plots > 1 else 1
    rows = (num_plots + cols - 1) // cols
    plt.figure(figsize=(12, 6 * rows))
    
    for idx, (generation, shape) in enumerate(sorted(best_shapes_at_intervals.items())):
        plt.subplot(rows, cols, idx + 1)
        polygon = Polygon(shape, closed=True, fill=True, edgecolor='r', alpha=0.5)
        plt.gca().add_patch(polygon)
        plt.xlim(-1.5, 1.5)
        plt.ylim(-1.5, 1.5)
        plt.gca().set_aspect('equal', adjustable='box')
        plt.title(f"Generation {generation}\nArea: {calculate_area(shape):.6f}")

    plt.tight_layout()
    plt.show()

def plot_max_diff_shapes(shape_before, shape_at, generation, diff):
    plt.figure(figsize=(12,6))
    
    plt.subplot(1,2,1)
    polygon1 = Polygon(shape_before, closed=True, fill=True, edgecolor='b', alpha=0.5)
    plt.gca().add_patch(polygon1)
    plt.xlim(-1.5, 1.5)
    plt.ylim(-1.5, 1.5)
    plt.gca().set_aspect('equal', adjustable='box')
    plt.title(f"Generation {generation -1}\nArea: {calculate_area(shape_before):.6f}")
    
    plt.subplot(1,2,2)
    polygon2 = Polygon(shape_at, closed=True, fill=True, edgecolor='g', alpha=0.5)
    plt.gca().add_patch(polygon2)
    plt.xlim(-1.5, 1.5)
    plt.ylim(-1.5, 1.5)
    plt.gca().set_aspect('equal', adjustable='box')
    plt.title(f"Generation {generation}\nArea: {calculate_area(shape_at):.6f}\nFitness Diff: {diff:.6f}")
    
    plt.tight_layout()
    plt.show()

# Run the Genetic Algorithm
best_shape, fitness_history, best_shapes_at_intervals, max_diff, generation_of_max_diff, shape_before_max_diff, shape_at_max_diff = genetic_algorithm()

# Plot the best shape overall
plot_shape(best_shape, title=f"Final Best Shape with Area: {best_fitness:.6f}")

# Plot fitness history
plot_fitness_history(fitness_history)

# Plot best shapes at every 100th generation
plot_selected_shapes(best_shapes_at_intervals)

# Plot shapes from the generation with maximum fitness difference
if shape_before_max_diff is not None and shape_at_max_diff is not None:
    plot_max_diff_shapes(shape_before_max_diff, shape_at_max_diff, generation_of_max_diff, max_diff)
    print(f"The maximum fitness difference of {max_diff:.6f} occurred between Generation {generation_of_max_diff -1} and Generation {generation_of_max_diff}.")
else:
    print("Insufficient data to determine maximum fitness difference.") // 이 코드가 하는 일을 설명하고, 이 코드를 더욱 업그레이드 시킬 방법을 말해봐.