====== Algorithme Quickhull ======

{{ :nsi:tds:animation_depicting_the_quickhull_algorithm.gif?direct |}}

Pour plus d'information, la [[https://fr.wikipedia.org/wiki/Quickhull|page Wikipedia]]

===== Principe =====

On se donne un ensemble de points du plan, répartis d'une façon arbitraire.

<WRAP tip>Comprenez bien : on n'a aucune information a priori sur leurs distribution. On ne peut pas espérer par exemple qu'ils soient alignés ou forme une carré ou quoique ce soit...</WRAP>

On dispose des coordonnées de tous les points.

On souhaite déterminer les sommets du plus petit polygone convexe non croisé qui recouvre tous les points. On l'appelle l'enveloppe convexe du nuage.

<WRAP info>**Polygone :** c'est une forme du plan fermée. Le polygone est délimité par des sommets et les segments liant deux sommets consécutifs (les côtés).

**Convexe :** Cela signifie que si on trace un segment entre n'importe quelle paire de sommets, la totalité du segment est à l'intérieur du polygone.

**Non croisé :** Les côtés ne se touchent jamais ailleurs qu'en des sommets.
</WRAP>

===== Votre travail =====

Vous allez devoir programmer l'algorithme quickhull. Toutes les explications sont données ensuite. Pour les besoins des tests vous aurez aussi besoin de fonctions supplémentaires.

Vous êtes libres du choix d'implémentation. Vous pouvez vous contenter de fonctions. Vous pouvez créer des classes. C'est à vous de décider.

Votre programme devra
  * générer une liste de points aléatoires,
  * exécuter l'algorithme quickhull sur ce nuage afin d'obtenir les coordonnées du polygone,
  * représenter le nuage de points et le polygone.

==== Générer aléatoirement les coordonnées du nuage de points ====

Le module ''random'' contient toutes les fonctions utiles. Je vous laisse faire.

==== Représenter le nuage ====

On utilisera ''matplotlib''

<code python>
import matplotlib.pyplot as plt # bibliothèque graphique

# je suppose que les coordonnées x sont dans x_values
# et les coordonnées y dans y_values

plt.figure() # crée une figure vide
plt.title("Nuage de points")
plt.scatter(xValues, yValues, marker="o", c="red", s=10)
# scatter -> nuage de points
# marker = 'o' définit la forme des points
# c = 'red' choisit la couleur
# s = 10 définit la taille des points
</code>

<WRAP tip>**Petite astuce :** J'ai choisi de mettre les x dans un tableau et les y dans un autre. On aurait pu préférer utiliser un tableau ''coords'' contenant des paires de coordonnées comme ''%%coords = [(3,25), (74,12) ...]%%''. Il est très simple de passer d'une forme à l'autre :

<code python>
# passer de x_values, y_values à coords :
coords = zip(x_values, y_values)

# passer de coords à x_values, y_values
x_values, y_values = zip(*coords)
</code>
</WRAP>

==== Représenter un polygone ====

Toujours avec ''matplotlib'',

<code python>
# les coordonnées des sommets sont dans x_polygone, y_polygone
plt.plot(x_polygone, y_polygone, c="blue", lineWidth=5)
# pour que le polygone se referme, il faut penser
# à répéter en dernier les coordonnées du premier point.
</code>

===== Algorithme Quickhull =====

Ce n'est pas si simple et si vous regardez l'algorithme tel qu'il est donné sur Wikipedia, c'est un peu emmêlé. Je vais donc vous détailler l'ensemble.

<WRAP important>Pour construire l'enveloppe dans le bon ordre, il est important de bien définir ce qu'on appellera gauche et droite. Quand on parlera de droite, ce sera toujours une droite définie par deux points, par exemple $(AB)​$ et quand on dira //à gauche de (AB)//, il faudra comprendre à gauche de la droite quand on est sur $A​$ et qu'on regarde vers $B​$. De ce fait, prendre $(AB)​$ ou $(BA)​$ n'aura pas le même effet : la gauche de $(AB)​$ est la droite de $(BA)​$ (on ne regarde pas dans le même sens !)

De plus, quand on dira //à gauche//, c'est strictement, les points sur la droite sont ignorés.

</WRAP>

==== Récurence ====

  - S'amorce avec un nuage $\mathcal{E}$ et une droite $(AB)$.
  - Constituer un sous nuage $\mathcal{E}_{sub}$ constitué des points de $\mathcal{E}$ avec les conditions :
    * absicsses entre $x_A$ et $x_B$, inclus. Attention, en général on ne sait pas si $x_A \leqslant x_B$ ou  $x_A \geqslant x_B$.
    * strictement à gauche de la droite $(AB)$
  - Si $\mathcal{E}_{sub}$ est vide ou ne contient que un point, renvoyer $\mathcal{E}_{sub}$
  - Sélection, dans $\mathcal{E}_{sub}$, du point $K$ le plus éloigné de $(AB)$.
  - Effectuer la récurrence sur $\mathcal{E}_{sub}$ et la droite $(AK)$.
  - Effectuer la récurrence sur $\mathcal{E}_{sub}$ et la droite $(KB)$. 
  - Renvoyer les points obtenus à l'étape (5) suivis de K suivi des points obtenus à l'étape (6)

==== Fonction principale ====

C'est la fonction appelée en premier et qui se charge d'amorcer la récurrence.

$\mathcal{E}$ est le nuage de points.

  - Si le nuage a 1 point ou moins, il n'y a rien à faire.
  - Choisir $P$ le point le plus à gauche et $Q$ le point le plus à droite en faisant en sorte que $P \neq Q$.
  - Lancer la récurrence avec $\mathcal{E}$ et la droite $(PQ)$
  - Lancer la récurrence avec $\mathcal{E}$ et la droite $(QP)$
  - Renvoyer le point $P$, suivi du résultat de l'étape (3), suivi de $Q$, suivi du résultat de l'étape (4), suivi de $P$.\\ //$P$ est répété pour refermer le polygone.//

<WRAP tip>Pour bien comprendre cet algo, faite le d'abord tourner à la main sur un dessin !</WRAP>

==== Mathématiques utiles ====

Dans l'algorithme, on parle de droites, de côtés et de distance. On n'est pas obligé de calculer l'équation de droites ni de calculer des distances. On peut utiliser des outils plus efficaces basés sur les vecteurs. Pour tout cela, on utilise un outil appelé le produit vectoriel.

=== Produit vectoriel ===

On calcule la quantité $\overrightarrow{AB} \wedge \overrightarrow{AM}$. Cette quantité est en fait un vecteur mais comme notre problème est dans le plan, seul une partie de cette quantité a un intérêt : $\delta = x_{\overrightarrow{AB}} \cdot y_{\overrightarrow{AM}} - y_{\overrightarrow{AB}} \cdot x_{\overrightarrow{AM}}$

=== Côté ===

Le signe de $\delta$ donne le côté : $M$ à gauche de $(AB)$ $\Leftrightarrow \delta > 0$

== Distance ==

La valeur absolue $|\delta|$ ne donne pas la distance entre $M$ et $(AB)$ mais une grandeur proportionnelle ce qui nous suffit ici.

<WRAP tip>Pour info : $|\delta| = PQ \times d$ où $d$ est la distance entre $(AB)$ et $M$. Dans notre problème, on veut seulement déterminer un point le plus éloigné. On n'a donc pas besoin de connaître une distance précise, seulement de classer les distances.</WRAP>