GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Aire d'un polygone convexe ======

{{ polygone.pdf |Version imprimable}}

Dans cet exercice, on traite d'un problème de géométrie : on souhaite calculer l'aire d'un polygone quelconque.

<WRAP info>
**Polygone :** figure géométrique plane formée d'une ligne brisée (appelée aussi ligne polygonale) fermée, c'est-à-dire d'une suite de segments qui commence et termine en un même point.
</WRAP>

Vous devrez implémenter les fonctions nécessaires en Python. Les fonctions à compléter se trouvent dans le fichier {{ .:polygone.py |}}.

<WRAP tip>
La signature des fonctions et leur documentation -- //commentaire sous la signature de chaque fonction// -- vous donnent des informations utiles. Lisez-les !

La suite du document est là pour vous donner des explications supplémentaires.
</WRAP>

<WRAP important>
Je vous fournis le fichier {{ .:test_polygone.py |}} qui est un fichier de test. Placez ce fichier dans le même répertoire que polygone.py et exécutez-le. Tous les tests doivent réussir.
</WRAP>

===== Coordonnées =====

Dans tous l'exercice, on se place dans un repère orthonormé $(O;I,J)$. Chaque point aura donc une paire de coordonnées $(x;y)$ que l'on représentera par un tuple. Par exemple ''%%(4,7)%%'' représente les coordonnées $(4;7)$.

<WRAP tip>
En général, quand les Français utilisent ''%%;%%'', les anglophones utilisent plutôt ''%%,%%''.
</WRAP>

En géométrie, un point peut avoir un nom. On parle ainsi du point A, du point B... Mais cela n'a rien d'obligatoire. On ne s'embarrasse donc pas de donner un nom aux points, on ne donne que leurs coordonnées.

Les coordonnées peuvent aussi être des coordonnées de vecteur. Par exemple le vecteur reliant le point de coordonnées ''%%(4,17)%%'' au point de coordonnées ''%%(12,-5)%%'' a les coordonnées ''%%(8,-22)%%''.

===== Polygone =====

==== Définition ====

Un polygone peut être défini par ses points, donnés dans un ordre précis.

Dans notre programme, le polygone sera représenté par un tableau de coordonnées.

**Exemples :**
  * ''%%[(1,1), (5,1), (1,4)]%%'' définit un triangle. C'est d'ailleurs un triangle rectangle.
  * ''%%[(2,0), (10,2), (9,6), (1,4)]%%'' définit un quadrilatère. C'est d'ailleurs un rectangle.
  * ''%%[(3,0), (9,-2), (4,-6), (-1,-3), (0,0)]%%'' définit un pentagone (5 côtés).

==== Nettoyage ====

Est-ce que ''%%[(3,0), (9,-2), (4,-6), (4-6), (9,-2), (-1,-3), (0,0), (3,0)]%%'' est un polygone acceptable ? C'est un tableau de coordonnées, est-ce que cela suffit ?

**Non !** On souhaite que les sommets consécutifs soient distincts.
  * Ici on constate que ''%%(4,-6)%%'' est répété consécutivement.
  * De même ''%%(3,0)%%'' est le premier et le dernier sommet.
  * En revanche, ''%%(9,-2)%%'' est répété mais pas consécutivement.

La fonction ''%%clean%%'' doit produire une **copie** nettoyée du polygone. Ici, elle devrait donc renvoyer ''%%[(3,0), (9,-2), (4-6), (9,-2), (-1,-3), (0,0)]%%''.

<WRAP tip>
En cas de répétition consécutive, c'est la 2e occurrence qui est supprimée. Si le dernier point est identique au premier, c'est le dernier que l'on supprime.
</WRAP>

<WRAP box>
Implémentez la fonction ''%%clean(polygone)%%''.
</WRAP>

==== Convexité ====

Ci-dessous, les figures vous montre ce que l'on appelle **convexité** pour un polygone. Celui de droite n'est pas convexe car une des diagonales passe en dehors du polygone.

{{ .:polygone_convexite.png?nolink&600 |}}

<WRAP tip>
Un triangle est toujours convexe.
</WRAP>

=== De quel côté ===

Pour déterminer si un polygone est convexe, on aura besoin de pouvoir déterminer la position relative d'un point par rapport à une droite.

On se donne deux points, par exemple $A$ et $B$ dont on connaît les coordonnées. On suppose que $A \neq B$ pour pouvoir déterminer la droite $(AB)$. On se demande si un point $C$ est d'un côté ou de l'autre de la droite, ou même sur la droite.

{{ .:polygone_quel_cote.png?nolink&600 |}}

La méthode sera la suivante :
  - Déterminer les coordonnées du vecteur $\overrightarrow{AB}$.\\ **Calcul :** on sait que $\overrightarrow{AB}\begin{pmatrix}x_B-x_A\\y_B-y_A\end{pmatrix}$ ou encore $x_{\overrightarrow{AB}} = x_B - x_A$ et $y_{\overrightarrow{AB}} = y_B - y_A$.
  - Calculer les coordonnées de $\overrightarrow{AC}$.
  - Faire un produit particulier entre $\overrightarrow{AB}$ et $\overrightarrow{AC}$, on l'appelle le produit vectoriel.\\ **Calcul :** $\delta = \overrightarrow{AB} \times \overrightarrow{AC} = x_{\overrightarrow{AB}}\cdot y_{\overrightarrow{AC}} - y_{\overrightarrow{AB}}\cdot x_{\overrightarrow{AC}}$
  - Décision :
    * Si $\delta=0$, alors $C\in(AB)$.
    * Si $\delta>0$, alors $C$ sur la gauche quand on regarde $B$ depuis $A$.
    * Si $\delta<0$, alors $C$ sur la droite.

<WRAP box>
**À faire :**
  - Compléter la fonction ''%%vecteur(A,B)%%'' qui calcul les coordonnées de $\overrightarrow{AB}$.
  - Compléter la fonction ''%%product(vAB,vAC)%%'' qui calcule le produit vectoriel comme décrit ci-dessus.
  - Compléter la fonction ''%%get_side_of_AB(A,B,C)%%'' qui renvoie ''%%1%%'', ''%%-1%%'' ou ''%%0%%'' selon la position de C par rapport à A et B.\\ //Précondition : A et B distincts//
</WRAP>

==== Convexe ou pas ====

Munis de la fonction ''%%get_side_of_AB(A,B,C)%%'', on va pouvoir déterminer la convexité d'un polygone quelconque et compléter la fonction ''%%is_convexe(polygone)%%''. En effet, un polygone convexe tourne toujours dans le même sens, toujours à gauche ou toujours à droite. Nous allons parcourir les sommets et déterminer, avec ''%%get_side_of_AB(A,B,C)%%'', dans quel sens tourne le polygone. S'il tourne parfois à gauche et parfois à droite, alors il n'est pas convexe.

Voici un algorithme.

<code lang-none linenums>
FONCTION is_convexe
ENTRÉE : polygone
SORTIE : Vrai si le polygone est convexe, Faux sinon
DÉBUT
    soit T un tableau vide,
    POUR CHAQUE point du polygone,
        soit A ce point
        soient B et C les points suivants,
        soit c le côté de C par rapport à (AB),
        stocker c dans T
    FIN
    SI T contient 1 et -1 ALORS
        RENVOYER Faux
    SINON
        RENVOYER Vrai
    FIN
FIN
</code>
    
<WRAP box>
Implémentez cet algorithme.
</WRAP>

<WRAP tip>
Il peut exister des cas particuliers où cet algorithme renvoie un mauvais résultats. Cela peut arriver dans certains cas où 3 sommets $A, B, C$ consécutifs sont tels que $C \in ]AB[$. On ignore ce cas particulier. Pour contourner ce problème on pourrait ajouter dans la boucle quelque chose comme :

<code lang-none>
SI xA < xC < xB OU xA > xC > xB OU yA < yC < yB OU yA > yC > yB ALORS
  RENVOYER Faux
</code>
</WRAP>

===== Calcul d'aire =====

==== Cas d'un triangle ====

Soit $A(x_A\,;\,y_A)$, $B(x_B\,;\,y_B)$ et $C(x_C\,;\,y_C)$, pour calculer l'aire de $ABC$ :

\[\mathcal{A} = \frac{1}{2}\cdot\left|\overrightarrow{AB} \times \overrightarrow{AC}\right|\]

où $\times$ est le produit de vecteurs déjà rencontré.

<WRAP tip>
Le produit vectoriel renvoie un résultat positif ou négatif selon que l'on parcours les sommets dans le sens trigonométrique ou pas. Les deux barres verticales représentent une valeur absolue, ce qui signifie que si le résultat a un signe moins, on l'enlève. En Python, la valeur absolue fait partie des instructions de base et est appelée ''%%abs%%''.
</WRAP>

<WRAP box>
Implémentez la fonction ''%%aire_triangle(A,B,C)%%''
</WRAP>

==== Aire polygone ====

On propose de découper le polygone successivement en triangles comme sur la figure ci-dessous.

{{ .:polygone_aires.png?nolink&600 |}}

Cela correspond à l'algorithme suivant :

<code lang-none linenums>
FONCTION aire_polygone
ENTRÉE : polygone
PRÉREQUIS : polygone est convexe
SORTIE : aire du polygone
DÉBUT
    soit A le premier point du polygone
    soit t valant initialement 0
    POUR CHAQUE point de polygone, à partir du 2e et jusqu'à l'avant dernier,
        soit B ce point,
        soit C le point suivant
        soit s l'aire de ABC
        ajouter s à t
    FIN
    RENVOYER t
FIN
</code>

<WRAP box>
Implémentez la fonction.
</WRAP>