Bonjour!
 
Je suis en train de réaliser une fonction me permettant de détecter si un point est oui ou non à l'intérieur d'un polygone quelconque (donc pas forcément convexe)
 
J'ai trouvé l'algorithme suivant : on prend notre point que l'on note M et on trace une demi droite partant de M et allant vers l'infini dans une direction donnée. Si cette demi droite ne rencontre aucun sommet du polygone et que le nombre d'intersections avec les segments de notre polygone est pair, alors on est dehors, si ce nombre est impair est dedans, si la demi droite rencontre un sommet du polygone on ne peut rien conclure ...
 
J'ai programmé la fonction permettant de calculer l'intersection entre deux segments (je calcule les alpha, beta, h de chacun des segments (où alpha et beta et h sont les coefficients de l'équation alpha*x+beta*y+h=0)), je résouds un système 2x2 en x et y puis je vérifie si le point obtenu est bien situé entre les sommets de chacun des deux segments (si d'ailleurs pour cet algorithme vous auriez quelque chose de plus léger je suis preneur)
 
Ainsi il me reste à déterminer la demi droite ...
Cependant, je n'ai pas tellement d'idée concernant comment faire pour détecter si cette demi droite rencontre un des sommets du polygone
Bien sur je pourrais faire une boucle, tester chacun des sommets, et si ca ne marche pas prendre une autre demi droite aléatoirement et recommencer, mais ca ne me satisfait pas tellement, car dans le cas ou notre polygone est assez petit et comporte plein de points, on risque alors de retomber sur un autre point et que la boucle dure assez longtemps ...  
 
Donc voila voila j'aimerais savoir si vous aviez une idée d'une part pour déterminer cette droite en complexité O(n) voire O(1) et si vous auriez une idée pour optimiser l'algorithme d'intersection entre deux segments que j'utilise
 
Merci d'avance
 
NC