Discussion :

[SuperBIBI]

Bonjour,
je recherche une formule pour savoir si un point est inclus dans un polygone quelconque.
C'est à dire quelque soit le nombre de sommet du polygone et même si le polygone est concave.
Toutes les informations que j'ai trouvé m'on parues à l'adresse de matheux.
il faudrait une explication très claire.
Merci d'avance

[Laurent Gomila]

Il y a principalement deux méthodes pour ça : la demi-droite, et les angles. Il me semble que la seconde ne fonctionne qu'avec les polygones convexes, je vais donc essayer de t'expliquer la première qui est en fait très simple.

La méthode de la demi-droite consiste à calculer les intersections entre ton polygone et une demi-droite, ayant comme origine le point à tester et ayant une direction quelconque (avec une droite parallèle à l'axe des x ou des y les calculs seront cependant plus simples). Si ce nombre d'intersections est impair alors le point est à l'intérieur du polygone, s'il est pair alors le point se trouve à l'extérieur. Plutôt simple non ?

Si tu as besoin d'explications plus poussées concernant le calcul des intersections n'hésite pas.

[alveric]

La méthode de la demi-droite consiste à calculer les intersections entre ton polygone et une demi-droite, ayant comme origine le point à tester et ayant une direction quelconque (avec une droite parallèle à l'axe des x ou des y les calculs seront cependant plus simples). Si ce nombre d'intersections est impair alors le point est à l'intérieur du polygone, s'il est pair alors le point se trouve à l'extérieur. Plutôt simple non ?

Avec cette methode, il faut faire attention aux "petits" cas particuliers: si la droite passe par un sommet du polygone, ou si elle coincide avec un cote, ou si le point qu'on veut tester se trouve, comme par hasard, sur un cote/sommet...

[Kangourou]

ca a deja ete traite, il y a un peu de tps il est vrai.

La methode des demi droites est assez simple a mettre en oeuvre, a part si on veut prendre en comtpe tous les cas embetant : quand le polygone a des cotes sur la demi droite de test, par exemple. Dans ce cas ca devient un peu penible.

J'ai une preference pour la methode des angles. Elle est un peu plus robuste, et permet en pllus de savoir en plus combien de fois le polygone "s'enroule" autour du point. (et elle marche pour tous les types de polygones...)

tout est explique ici :
http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/

A+

[SuperBIBI]

Bonjour,

J'avais déjà testé plusieurs méthode, mais celle du lien de Kangourou me donne toute satisfaction.
Le code est simple et très facilement portable.

merci de vos réponses.