import matplotlib.pyplot as plt
from random import randrange

li = [(2.1,5.1),(1.9,0.4),(0.5,1.1),(2.2,4.9),(1.6,6.8),(1.5,5.1),(-2.5,-1.8),(1.1,0.3),(-2.1,-2.5),(-3.0,-3.1),(-3.0,1.5),(-2.5,1.4),(-2.7,1.8),(-2.6,1.9),(0.8,1.1)]
l2 = [(4.9,2.9),(5.,3.),(4.5,3.5),(4.6,3.4),(0.1,0.),(0.,0.1),(0.5,0.6),(0.6,0.5),(-2.1,-3.1),(-2.2,-3.0),(-2.7,-3.5),(-2.6,-3.4)]

def afficher_liste_points(points,col = "black") :
    """
    Affiche une liste de points en noir
    """
    fig = plt.figure(1)

    X, Y = [p[0] for p in points], [p[1] for p in points]
    plt.scatter(X,Y,color = col)

def effacer_liste_points(points) :
    """
    Affiche une liste de points en noir
    """


    X, Y = [p[0] for p in points], [p[1] for p in points]
    plt.scatter(X,Y,color = 'white')

def afficher_multiple_liste(classe_points) :



    couleur = ['b','y','r','g','brown']
    i = 0
    for points in classe_points :
        X, Y = [p[0] for p in points], [p[1] for p in points]
        plt.scatter(X,Y,color = couleur[i])
        i+=1



"""
plt.figure(1)
afficher_liste_points(l)
"""

def choix_aleatoire(liste,k) :
    non_choisi = [i for i in range (len(liste))]
    rep = []
    while len(rep) < k :
        j = randrange(0,len(non_choisi))
        rep.append(liste[non_choisi[j]])
        non_choisi.pop(j)
    return rep


## Question 2

def barycentre(points) :
    x, y = 0, 0
    for xp,yp in points :
        x += xp
        y += yp
    return (x/len(points),y/len(points))

















## Question 3


def barycentre_classe(classes) :
    rep = []
    for l in classes :
        rep.append(barycentre(l))
    return rep

## Question 4
def distance_euclidienne(p1,p2) :
    x1, y1 = p1
    x2, y2 = p2
    return ((x1-x2)**2+(y1-y2)**2)**(1/2)














## Question 5

def plus_proche_indice(centres,point) :
    dist_min = distance_euclidienne(centres[0],point)
    ind_min = 0

    for i in range (1,len(centres)) :
        if distance_euclidienne(centres[i],point) < dist_min :
            dist_min = distance_euclidienne(centres[i],point)
            ind_min = i
    return ind_min





















def classe_points(centres,L) :
    # Une liste vide par centre
    rep = [[] for i in range(len(centres))]

    for point in L :
        i = plus_proche_indice(centres,point)
        rep[i].append(point)
    return rep




















def k_moyenne(liste,k,affichage = True) :
    assert k <= len(liste)

    # On choisit les k premiers éléments comme centre
    #centres = liste[:k]
    centres = choix_aleatoire(liste,k)
    #centres = [(1.1,0.3),(1.6,6.8),(-2.7,1.8),(0.8,1.1)]
    classe = [[] for i in range (k)]


    if affichage :
        fig = plt.figure(1)
        plt.xlim(-5, 6)
        plt.ylim(-4, 7)
        afficher_liste_points(liste)
        numboucle = 0
        afficher_liste_points(centres, "m")
        plt.savefig("k_moyenne" + str(numboucle))
        numboucle+= 1

    while True :
        ancien_centre = centres[:]
        classe_apres_boucle = classe_points(centres,liste)

        if classe_apres_boucle == classe :
            break

        # Question 11
        for i in range(len(classe_apres_boucle)-1,-1,-1) :
            if classe_apres_boucle[i] == [] :

                classe_apres_boucle.pop(i)

        # Fin 11



        centres = barycentre_classe(classe_apres_boucle)
        classe = classe_apres_boucle
        if affichage :
            effacer_liste_points(ancien_centre)
            afficher_multiple_liste(classe_apres_boucle)
            afficher_liste_points(centres,"m")
            plt.savefig("k_moyenne" + str(numboucle))
            numboucle+= 1

    if affichage :
        plt.show()
        plt.close()



    return classe_apres_boucle




def eps_moyen(classe) :
    rep = 0
    bary = barycentre(classe)
    for p in classe :
        rep += distance_euclidienne(p,bary)
    return rep/len(classe)




















def eps_max(cls) :
    eps_m = 0
    for cl in cls :
        eps = eps_moyen(cl)
        if eps > eps_m :
            eps_m = eps
    return eps_m



def k_moyenne_multiple(liste,k,nb) :
    classes = k_moyenne(liste,k,False)
    eps_cla = eps_max(classes)
    for n in range (nb-1) :
        classes_temp = k_moyenne(liste,k,False)
        if eps_max(classes_temp) < eps_cla :
            eps_cla = eps_max(classes_temp)
            classes = classes_temp
    return classes













def tracer_k(liste,nb,max_k) :

    l_k = [k for k in range (2,max_k+1)]
    eps = []
    for k in l_k :
        eps.append(eps_max(k_moyenne_multiple(liste,k,nb)))
    fig =plt.figure(4)
    plt.plot(l_k,eps)
    plt.show()





def tracer_nb(liste,nb_max,k,rep) :
    l_nb = [nb for nb in range (1,nb_max+1)]
    eps = []
    for nb in l_nb :
        s = 0
        for j in range(rep) :
            s += eps_max(k_moyenne_multiple(liste,k,nb))
        eps.append(s)
    plt.plot(l_nb,eps)
    plt.show()