Aujourd'hui : une archive tar compressée contenant :
- un fichier convexe.ml contenant un début d'implémentation
- un fichier Makefile permettant de compiler en tapant simplement la commande "make"

Objectif :
Étant donné un ensemble de points, en calculer l'enveloppe convexe, c'est à dire le plus petit ensemble convexe qui contient tous les points.
Pour reformuler, si il se tenait un clou à chaque point, c'est la forme que prendrait un élastique que l'on aurait tendu pour envelopper tous les clous puis laché.

Visualisation :
Nous allons utiliser la bibliothèque graphique pour tracer les points et le polygone correspondant à l'enveloppe convexe, ce qui permet une autocorrection très simple.
Le code fournit contient des fonctions pour récupérer les coordonnées des points sur lequel l'utilisation clique, et quelques fonctions d'affichage.
Le programme final doit laisser l'utilisateur cliquer sur des points et recalcule et affiche en temps réel l'enveloppe convexe des points cliqués.

Méthode :
* Nous allons utiliser l'ordre lexicographique sur les points en les implémentants par des couples d'entier. Cela nous permet de parcourir les points avec une _droite de balayage_, c'est-à-dire que lorsque l'on considère un point, tous les points à gauche ont été traités, et aucun point à droite n'a encore été traité, ce qui permet de facilement définir des invariants lors de notre algorithme.
Pour ceci, nous maintiendrons la liste des points triés par ordre croissant.

* Nous allons séparer l'enveloppe convexe en deux parties : la partie supérieure (tous les points doivent être en dessous de cette courbe) et la partie inférieure (tous les points doivent être au dessus de cette courbe), nous n'expliquerons que comment déterminer la partie supérieure, à vous d'adapter pour faire l'autre partie.

* Pour savoir si un point C est à droite ou à gauche d'une demi-droite [AB), on s'intéresse au signe du déterminant entre les vecteurs AB et AC.

* Si l'enveloppe convexe en train d'être construite termine par les points A puis B : si C est à gauche de [AB), alors B n'est pas dans l'enveloppe convexe. Si C est à droite de [AB), à priori, A, B et C appartiennent tous trois à l'enveloppe convexe (peut changer suivant les points qu'il reste à analyser)

Analyse de l'algorithme :
* On construit peu à peu la courbe correspondant à la partie supérieure de l'enveloppe convexe. À chaque étape, tous les points déjà considérés sont en dessous de cette courbe, et l'aire sous la courbe est convexe. Autrement dit, si on note P1, P2, ..., Pk les points de cette enveloppe, Pi+2 est à droite de [PiPi+1)

* En terme de complexité, chaque point peut être au plus ajouté une fois et retirer une fois de l'enveloppe convexe en construction, donc la complexité est linéaire en le nombre de points. Le tri des points domine la complexité avec une complexité en O(nlog n) où n est le nombre de points