Contours
Objectif : dans un espace à 2 dimensions, déterminer si un point est ou non à l’intérieur d’un contour (polygone).
Algorithme du lancer de rayon
source : https://en.wikipedia.org/wiki/Point_in_polygon
Un moyen simple de déterminer si un point se trouve à l’intérieur ou à l’extérieur d’un polygone simple consiste à tester le nombre de fois qu’un rayon, partant du point et allant dans une direction fixe, coupe les bords du polygone.
- Si le point est à l’extérieur du polygone, le rayon coupera son bord un nombre pair de fois.
- Si le point se trouve à l’intérieur du polygone, il coupera l’arête un nombre impair de fois.
D’un point de vue algorithmique, il suffit donc de choisir une direction et un sens pour le rayon (\(+\vec x\) par exemple) et de compter combien de segments du contour sont coupés par cette demi-droite.
Reste à déterminer si les segments se croisent ou pas :
