Un point est-il dans un polygone ?

Dans cet exercice, on traite d'un problème de géométrie : on souhaite déterminer si un point est à l'intérieur ou à l'extérieur d'un polygone quelconque.

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.

Coordonnées

Dans tous l'exercice, on se place dans un repère $(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énéral, quand les Français utilisent ;, les anglophones utilisent plutôt ,.

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

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.

Implémentez la fonction clean(polygone).

Ce que l'on veut faire

Considérant un point de coordonnées connues, et un polygone également connu, on souhaite déterminer si le point est à l'intérieur du polygone.

Principe de la méthode

On détermine d'abord si le point est sur un côté ou un sommet,
Sinon, on trace une ligne horizontale à l'infini vers la droite et on compte toutes les intersections avec les côté du polygone.
- Si le nombre d'intersections est pair, alors le point est en dehors,
- sinon il est à l'intérieur.

Il faut toutefois tenir compte de cas particulier comme g sur la figure. Si la ligne horizontale touche le polygone par un sommet, faut-il compter 2 intersections ou 1 ? Dans le cas de la figure on voit qu'il faudrait en compter 0 car les côtés touchés par le sommet sont en-dessous de la ligne horizontale.

Dans ce genre de travail, vous pouvez toujours limiter l'étendue du problème. Vous pouvez par exemple considérer, dans un premier temps, que le cas de points comme g n'arrivera pas. Puis si vous en avez le temps, vous pouvez voir comment prendre en compte ce cas.

Organisation générale

Une fois le polygone nettoyé, il apparaît comme un tableau [A,B,C,D,E] (exemple d'un pentagone) où A, B, C, D, E sont des paires de coordonnées comme (5,12). Donc en Python,

A[0] me permet d'atteindre l'abscisse de A,
A[1] me permet d'atteindre l'ordonnée de A,
mais il est plus élégant d'écrire x, y = A qui distribue les coordonnées de A sur les variables x et y.

Il faudra alors envisager les segments [AB], [BC], [CD], [DE] et ne pas oublier [EA].

Le point considéré est par exemple F.

Il nous faut :

Une fonction appartient_segment(R,T,S) qui renvoie True si le point S appartient au segment [RT], False sinon.
Une fonction coupe_horizontale(R,T,S) qui renvoie True si le segment [RT] coupe l'horizontale partant depuis S vers la droite, False sinon.
Une fonction est_au_bord(polygone,S) qui renvoie True si S est sur un bord du polygone.
Une fonction est_interieur(polygone,S) qui renvoie True si S est à l'intérieur du polygone.