point ou non dans un polygone quelconque

Voila mon problème: j'ai une liste de points (ordonés) qui me forment un polygone. J'ai aussi un autre point et la question que je veux résoudre est: le point est il dans le polygone ou pas.

J'ai vu ce sujet traité mais qu'avec le cas ou le polygone était un carré ou un triangle. moi il peut être quelconque.

La méthode de tracer une demie droite depuis mon point et de regarder combien de fois elle coupe mon poygone (1 nombre pair et je suis à l'extérieur et un nombre impair à l'intérieur) ne me convient guère. En effet cela pose des problème au niveau des coins de mon polygones. En effet si je suis à l'interieur et que je passe par un coin(provenant d'un angle obtu) puis que je sors, cela me fait 2 intersections...

Quelqu'un connait une méthode élégante pour résoudre mon problème ?

Voici une idée :

Soit M le point dont on veut savoir s'il est à l'intérieur du polygone.

Pour chaque côté du polygone, déterminer sa normale intérieure au polygone (par produit vectoriel avec un vecteur qui est normal au polygone). Puis par produit scalaire entre ce vecteur normal et celui constitué par M et le milieu du côté testé, on détermine si M est situé vers l'intérieur ou l'extérieur. En recommençant pour chaque côté, on trouvera si M est à l'intérieur du polygone.

Par contre, cette méthode risque de ne pas fonctionner si le polygone présente des concavités.

Au fait, le polygone peut-il être concave ?

Car dans ce cas, on peut toujours imaginer une triangulation du polygone et determiner si le point M est à l'intérieur de chaque triangle. C'est un peu lourd, mais j'ai l'impression que toute autre méthode risque de ne pas fonctionner en cas de concavité !

Sinon, en ce qui concerne la méthode qui consiste à determiner la parité du nombre d'intersection entre un rayon partant du point M et avec le polygone, on peut tout de même l'utiliser en prenant quelques précautions. Il suffit de tester que chaque point du polygone n'appartient pas à la demi-droite, et dans le cas contraire, prendre une autre demi-droite.

Voir aussi cette page :

http://astronomy.swin.edu.au/~pbourk...ry/insidepoly/

Bonjour,

Pour faciliter l'implémentation de la méthode de la parité, on peut :
1) utiliser une demi-droite parallèle aux axes de coordonnées (axe X ou Y).
2) lorsqu'un sommet est sur la demi-droite (exemple, même X que le point testé) , on le décale d'epsilon.

Citation:

---

Envoyé par Mandarine

La méthode de tracer une demie droite depuis mon point et de regarder combien de fois elle coupe mon poygone (1 nombre pair et je suis à l'extérieur et un nombre impair à l'intérieur) ne me convient guère. En effet cela pose des problème au niveau des coins de mon polygones. En effet si je suis à l'interieur et que je passe par un coin(provenant d'un angle obtu) puis que je sors, cela me fait 2 intersections...

---

Cas particulier facilement résolu la dernière fois il me semble... si les points précédant et suivant le point d'intersection sont du même côté de la demi-droite, compter deux intersections, et si ils sont un de chaque côté, en compter une seule.

Citation:

---

Envoyé par Graffito

2) lorsqu'un sommet est sur la demi-droite (exemple, même X que le point testé) , on le décale d'epsilon.

---

Roooooh! Trop beau ça!!! Je me le note...

bien le bonjour,

Une solution très facile à mettre en oeuvre et très rapide à exécuter consiste à calculer la somme des angles orientés de sommet le point à analyser et passant par chacun des sommets du polygone, dans l'ordre.

Donc pour un polygone à n côtés, ça ne coute que n additions.
Si la somme est 360, le point est dans le polygone, sinon la somme vaut 0 et le point est en dehors. Concave ou convexe, ça fonctionne.

Citation:

---

Envoyé par khayyam90

Donc pour un polygone à n côtés, ça ne coute que n additions.

---

Euh... oui... enfin... faut pas oublier de rajouter le calcul des n angles avant... :mouarf:

Eh bé ça fait deux méthodes ça, on devrait voir apparaitre un "résolu" bientôt, non?

Merci bien,

Le résolu arrive du temps de récupérer de mes 7h de décallage horaire pour me rendre aux USA et de lire vos réponses.

J'avais penser à changer de droite lorsque je rencontrer un coin mais ce n'est pas très hestétiques.
Par contre j'adore les 2 solutions: celle pour résoudre le problème de l'intersection et celle qui consiste à regarder les angles :D

Le problème maintenant c'est laquelle choisir ? :mouarf:

Merci et bonne fin de Weekend