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

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

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

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

===== 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 ====

{{ :nsi:tds:polygon1.png?direct|}}

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

<WRAP important>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.</WRAP>

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