Déterminer si un point est contenu dans un polygone


Il faut pour cela imaginer une demi droite qui partirait du point vers l'infini. On calcule ensuite le nombre d'intersection entre les segments constituants ce polygone et cette demi-droite. Si le nombre obtenu est impair, alors le point est contenu dans le polygone.

Ici un seule intersection...

Dans cet exemple, la demi-droite qui part du point A coupe une seule fois le polygone, donc le point A est intérieur à la figure.
Par contre, la demi-droite qui part du point B coupe 2 fois le polygone. 2 étant un chiffre pair, on peut en déduire que le point B est à l'extérieur.

La direction de la demi-droite n'a pas d'importance. Cependant, l'implémentation est plus facile avec une demi-droite horizontale ou verticale.

 

Comme me l'a fait très justement remarqué Philippe, cet algorithme ne fonctionne pas si la demi-droite passe par l'un des vertex de la polyligne comme dans le schéma ci-dessous :

Le point est bien à l'intérieur, mais le nombre d'intersection est pair !

Il faut donc éliminer toutes les intersections qui correspondent à des vertex, sauf si on n'en trouve qu'une (dans ce cas, on ne peut pas déterminer si le point est intérieur ou non à la polyligne et il faut alors essayer avec une droite orientée dans une direction différente).

Exemple en VBA pour AutoCAD