#JCourtin 07/2016

##modules
from matplotlib import pyplot as plt
from math import sin, cos, atan, pi
import random as rnd
import operator #permet de trier des tuples selon 1 attribut

##création d'un nuage de points  -> dictionnaire  {index:(x,y)}
def nuage(N, R):    
    r=[R*rnd.random() for k in range(N)]
    theta=[2*pi*rnd.random() for k in range(N)]
    #renvoyer un dictionnaire {k:(x,y)} qui représente le nuage de points:
    return {#???? for k in range(N)} #A corriger
     

#Affichage
def plotNuage(nuage):
    x,y=#Liste des coordonnées x et y     
    x0,y0=nuage[getStartIndex(nuage)] #de quoi s'agit-il ?
    env=envellope(nuage)
    #expliquer comment fonctionne la commande suivante :
    xEnv, yEnv = [nuage[k][0] for k in env], [nuage[k][1] for k in env]
    plt.close()
    plt.plot(#??)                  #Afficher les points  : carrés rouges
    plt.plot(#???)                 #Afficher l'enveloppe : ligne polygonale fermée
    plt.plot(#????)                #Afficher ses points  : ronds verts
    plt.plot(#???)                 #Point de départ : rond bleu
    plt.plot()
    plt.show()
    

    
##recherche de l'enveloppe convexe

#point de départ (le plus bas)
def getStartIndex(nuage):
    #Rédiger le corps de fontion qui trouve l'indice du point dont l'ordonnée 
    #est la plus basse possible.
    return  indexMin

#renvoit ?????? #A compléter
def nuageTri(nuage):
    startIndex=getStartIndex(nuage)
    start=nuage[startIndex]
    #A quoi correspond l'objet liste ci-dessous ? précisément ?
    list=[(k, angleHorizontale(start, nuage[k])) for k in nuage.keys() if k!=startIndex]
    #expliquer ce que fait la commande suivante 
    list.sort(key=operator.itemgetter(1))#LA formule magique ....
    #et que renvoit on finalement ???
    return [tup[0] for tup in list]
    
#renvoit ????
def envellope(nuage):
    start=getStartIndex(nuage)
    pointAngle = [start] + nuageTri(nuage)
    k=1
    while (k < len(pointAngle)-1):   #Justifier les bornes
        xS, yS = nuage[pointAngle[#?]]# point précédent    
        xP, yP = nuage[pointAngle[k]]# point
        xN, yN = nuage[pointAngle[#?]]# point suivant
        vecDir=(xP-xS, yP-yS);        vecDirNext=(#??,#??)
        
        if (angleRotation(vecDir, vecDirNext) < 0.): #Expliquer cette partie 
            pointAngle.pop(k)  #Que fait-on ? et pourquoi ?
            k=k-1        #corriger
        else:
            k=k+1        #si nécessaire
    #et que renvoit on finalement ???
    return pointAngle+[start]
    
##Fonction de géométrie
def angleHorizontale(start, point):
    xS, yS = start        
    xP, yP = point
    hypo=#pythagore                            #renvoit l'angle en rad
    cosAlpha=(xP-xS)/hypo                      #toujours sur [0, 2*pi]

    if (cosAlpha>0):
        return atan((yP-yS)/(xP-xS))%(2*pi)    #proposer des tests de cette fonction
    elif (cosAlpha<0):                         #dans la console, pour vérifier qu'elle 
        return atan((yP-yS)/(xP-xS))+pi        #fonction dans tous les cas.
    elif (yP>yS):
        return #??
    else:
        return #??
        
        

def angleRotation(vecDir, vecDirNext):
    u,v=vecDir;       x,y=vecDirNext
    vectorielAlpha=u*x-y*v    #Corriger la formule, de quoi s'agit-il ?
    return vectorielAlpha     #Pourquoi ne cherche-t-on pas alpha lui même ?

################################## MAIN ########################################
if(__name__=="__main__"):

    N=1000
    R=10.
    
    monNuage=nuage(N,R)
    plotNuage(monNuage)