#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):
    #Etant donné un point de départ S, on veut trier les points P selon l'angle
    #Que fait SP par rapport à l'horizontal.
    #
    #A l'aide des fonctions ci dessous obtenir le point de départ 
    #
    #Créer la liste des tuple (indice, angleHorizontale) pour tous les points 
    #SAUF le point de départ.
    list=[#??]
    #expliquer ce que fait la commande suivante 
    list.sort(key=operator.itemgetter(1))  #C'est LA formule magique .... du TD.
    #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          #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):
    #Ecrire un code qui evalue l'angle que font les points soit SP par rapport
    #l'axe des x -> horizontal et vers la droite.
    return #angle entre 0 et 2*pi

def angleRotation(vecDir, vecDirNext):
    u,v=vecDir;       x,y=vecDirNext
    vectorielAlpha= #?        #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)