{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Enveloppe convexe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*N'hésitez pas à ajouter des définitions préliminaires.*\n",
    "\n",
    "### Définition (Enveloppe convexe)\n",
    "\n",
    "Soit Q un ensemble fini de points dans le plan (i.e, $Q \\subseteq \\mathbb{R}^2$). L'enveloppe convexe $CH(Q)$ est ...\n",
    "\n",
    "### Exemples\n",
    "*Donner au moins un exemple et un contre-exemple*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Utilitaires Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import de librairie utilisées dans la suite\n",
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "\n",
    "def generation_points(n=100, xmin=0, xmax=1, ymin=0, ymax=1):\n",
    "    \"\"\"Génère un ensemble de n points ayant une abscisse comprise\n",
    "    entre xmin et xmax, et une ordonnée comprise entre ymin et ymax\"\"\"\n",
    "    return [(random.uniform(xmin, xmax), random.uniform(ymin, ymax)) for i in range(n)]\n",
    "\n",
    "def afficher_enveloppe(polygone, ensemble_points=None):\n",
    "    \"\"\"Affiche une enveloppe convexe représentée par polygone en violet\n",
    "    et potentiellement un ensemble de point inclus dans l'enveloppe convexe\n",
    "    en noir\"\"\"\n",
    "    x, y = zip(*polygone)\n",
    "    plt.scatter(x, y, color=\"purple\")\n",
    "    if ensemble_points is not None:\n",
    "        interieur = set(ensemble_points) - set(polygone)\n",
    "        xe, ye = zip(*interieur)\n",
    "        plt.scatter(xe, ye, color=\"black\")\n",
    "    plt.plot((*x, x[0]), (*y, y[0]), 'b-')\n",
    "    plt.show()\n",
    "\n",
    "    \n",
    "# Exemple d'utilisation\n",
    "# points = [(0.5, 0.5), (0, 0.5), (0, 0), (1, 0), (1, 1), (0, 1), (0.5, 0), (1, 0.5), (0.5, 1), (0.2, 0.4)]\n",
    "# polygone = [(0, 0), (1, 0), (1, 1), (0, 1)]\n",
    "# afficher_enveloppe(polygone, points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Orientation de trois points p, q, r\n",
    "\n",
    "*Étant donné trois points $p$, $q$, $r$ et leurs coordonnées, expliquer comment calculer si $r$ est à gauche de $[pq]$ ou non.*\n",
    "\n",
    "\n",
    "Dans la suite, le type `point` désigne `tuple[float, float]`.\n",
    "Écrire une fonction python `orientation` de type `point * point * point -> int` qui renvoie 0 si les points p, q et r sont colinéaires, 1 si les points sont orientés vers la gauche, 2 si les points sont orientés vers la droite.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def orientation(p, q, r):\n",
    "    \"\"\"N'oubliez pas de documenter votre fonction !\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tester si un ensemble de points est convexe\n",
    "Écrire une fonction python `est_convexe` de type `list[point] -> bool` qui renvoie vrai si et seulement si le polygone donné en argument est convexe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_convexe(points):\n",
    "    \"\"\"N'oubliez pas de documenter votre fonction\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testez votre fonction `est_convexe` sur au moins trois polygones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Écrivez ici vos tests\n",
    "# N'hésitez pas à utiliser afficher_enveloppe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculer l'enveloppe convexe selon l'agorithme de Jarvis\n",
    "\n",
    "*Définir une fonction `enveloppe_convexe_jarvis`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def enveloppe_convexe_jarvis(p):\n",
    "    \"\"\" ... \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tester la fonction `enveloppe_convexe_jarvis` sur au moins un exemple à vous, et affichez le résultat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tester la fonction `enveloppe_convexe_jarvis` en utilisant la fonction `generation_points` pour générer l'ensemble de points dont vous voulez calculer l'enveloppe convexe, et affichez le résultat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Complexité\n",
    "\n",
    "Quelle est la complexité de l'algorithme de Jarvis (justifier) ? \n",
    "\n",
    "#### Correction de l'algorithme\n",
    "\n",
    "Pourquoi l'algorithme de Jarvis renvoie bien une enveloppe convexe ? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculer l'enveloppe convexe selon l'algorithme de Graham"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Définir une fonction `enveloppe_convexe_graham`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def enveloppe_convexe_jarvis(p):\n",
    "    \"\"\" ... \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tester la fonction `enveloppe_convexe_graham` sur au moins un exemple à vous, et affichez le résultat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tester la fonction `enveloppe_convexe_graham` en utilisant la fonction `generation_points` pour générer l'ensemble de points dont vous voulez calculer l'enveloppe convexe, et affichez le résultat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Complexité\n",
    "\n",
    "Quelle est la complexité de l'algorithme de Graham (justifier) ? \n",
    "\n",
    "#### Correction de l'algorithme \n",
    "\n",
    "Pourquoi l'algorithme de Graham renvoie bien une enveloppe convexe ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ajout d'un point à une enveloppe convexe\n",
    "\n",
    "Définir une fonction `ajout_point_enveloppe` de type `point * list[point] -> list[point]` qui étant donné un point $P$ et une enveloppe convexe $C$ renvoie l'enveloppe convexe de $C \\cup P$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bibliographie"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}