Version imprimable

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

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

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)$.

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).

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).

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)].

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.

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.

La méthode sera la suivante :

1. 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$.
2. Calculer les coordonnées de $\overrightarrow{AC}$.
3. 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}}$
4. 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.

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.

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

SI xA < xC < xB OU xA > xC > xB OU yA < yC < yB OU yA > yC > yB ALORS
  RENVOYER Faux

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é.

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

Cela correspond à l'algorithme suivant :

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