Point dans un polygone

Le principe de ce code est de chercher si un point P est dedans ou dehors d’un polygone donné.

Dans un premier temps on crée le polygone et on cherche ce que l’on appelle la bounding box du polygone (le rectangle minimum qui enveloppe le polygone). Ceci est fait lors de la création du polygone.

En suite une série de tests est à faire (par une méthode de paliers - dans le but de réduire au maximum le nombre de calculs effectués), voici la série de tests :

1) on vérifie que le point est dans la bounding box. Si le point est dehors de la bounding box, il y a aucune possibilité qu’il soit dedans le polygone. Si le point est dans la bounding box, il existe la possibilité que ce point soit dans le polygone (cela ne veux pas dire que le point est dans le polygone, mais cela n’est pas exclu - il faut faire plus de tests).

2) on applique une méthode qui s’appelle ray casting : on dessine un segment (ligne) entre un point sur l’extérieur du polygone et le point P, ce segment, que l’on appelle OP, est parallèle à l’axe des abscisses (l’axe x). Plusieurs cas de figure se posent : a) le point P est sur un des vertex du polygone, dans ce cas on doit vérifier comment ce vertex est composé (selon le cas on a une ou deux intersections) b) le segment OP intercepte des droites du polygone, on doit encore vérifier comment cette interception est faite (selon le cas on a aucune, une ou deux intersections) c) on compte combien d’intersections sont faites entre le segment OP et le polygone, si le chiffre est paire le point P est dans le polygone, s’il est impaire ou nul il est dehors.

Cette méthode de calcul est mieux expliquée ici : http://en.wikipedia.org/wiki/Point_...