#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):
    #On veut ici générer des points aléatoirement dans le plan :
    #On jette un rayon puis un angle entre 0 et 2*pi  
    #
    #Pouvez-vous deviner quelle sera l'allure de la distribution de points ?
    #
    r=[#?*rnd.random() for k in range(N)]
    theta=[#??]
    #On veut ensuite manipuler les coordonnées obtenus en cartésiennes
    #Pourquoi ne pas directement jeter des points en cartésiennes ???s
    #
    #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[#Comment obtenir l'indice du point de départ]
    env=enveloppe(nuage)
    #Quel est l'objet env renvoyé par enveloppe(nuage) ?
    #
    #On veut deux listes xEnv et yEnv permettant de tracer l'enveloppe
    xEnv, yEnv = [#?, #?]
    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 enveloppe(nuage):
    start=getStartIndex(nuage)
    pointAngle = [start] + nuageTri(nuage)
    k=1
    while (k < len(pointAngle)-1):   #Justifier les bornes
        xS, yS = #coordonnées du point précédent    
        xP, yP = #coordonnées du point en cours
        xN, yN = #coordonnées du point suivant
        
        #vecteur directeur de S vers P;  puis de P vers N
        vecDir=(#??,#??);        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]       #Pourquoi ajouter start : on l'avais déjà !!!
    
##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 #??  #attention ajouter %(2*pi)    #proposer des tests de cette fonction
    elif (cosAlpha<0):                            #dans la console, pour vérifier qu'elle 
        return #?? #attention ajouter+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)