Cet algorithme m'a servi a deux occasions. La première fois, il a été intégré à un autre algorithme de décomposition de polygône en triangles. Il s'agissait du projet OTIS qui est présent sur ce site. La deuxième fois, il s'agissait de définir si une caméra appartenait à une pièce. C'était pour mon stage avec DCN Equipements Navals.

Si mes souvenirs sont bons, je l'ai trouvé sur une page de l'INRIA. Toutefois je serai bien incapable de me souvenir du lien exact.



PRINCIPE :

L'idée est très simple. Il s'agit de tirer une demi-droite à partir du point que l'on désire tester et de compter le nombre d'intersection avec les côtés du polygône. Etant donné que rien ne vaut un bon exemple pratique. En voilà un :

On a un polygône quelconque dont on ne connaît que les coordonnées de ses sommets.

Pour savoir si un point quelconque appartient au contour, on tire une demi droite horizontal à partir de ce point.

Ensuite il suffit de compter le nombre d'intersection entre la demi-droite et le contour du polygône. Si le résultat est pair, le point est à l'extérieur, s'il est impair, il est à l'intérieur. Au niveau de la programmation, il s'agit d'un algo d'intersection de deux segments. On pourrait se contenter de comparer les coordonnées du point avec ceux des extrémités de chaque segment composant le contour. Mais cela poserait un problème si la demi-droite n'était pas horizontale, or dans certains cas particulier, cela peut être le cas .
Ici, le nombre d'intersection est égal à 3. Le point testé est à l'intérieur du polygône. Bien que le principe soit simple, il existe quelque cas particuliers.

  • Tout d'abord si le nombre d'intersection est égal à 0, qui ni pair, ni impair, le point est à l'extérieur du contour.

  • Si le point testé est un sommet du polygône. Le nombre d'intersection est au minimum égal à 2 et peut être pair ou impair. Une pour chaque segment composant le polygône passant par ce sommet. Il est donc préférable de tester si le point est un sommet avant de se servir de la demi-droite.

  • Il y a un cas bien plus génant. Si le point testé est aligné avec un côté du polygône, le nombre d'intersection est infini. Or dans un programme, rien n'est plus embêtant qu'une boucle infinie. Il est nécessaire donc de tester le nombre d'intersection lors de l'application de l'aglo. Si ce nombre devient supérieur au nombre de côté du polygône, il y a un problème et on arrête l'exécution de l'algo. Dans ce cas précis, la solution consiste à réappliquer l'algo avec une demi-droite différente. Elle peut partir à l'opposé ou être simplement décalée de quelques degrés.