[Géométrie] Point situé dans un polygone

[yagosacquet]

Bonjour,
Je suis informaticien et dans le cadre d'un projet lié à la géographie, je doit être capable de déterminé si un point (avec des coordonnées x,y) est situé dans une zone définie par un polygone qui peut être concave ou convexe.
J'ai pensé à simplifier le polygone en plusieurs polygones simples mais j'ai quelques problèmes avec cette solution.
Est ce que quelqu'un a une idée d'une autre solution à mettre en place pour résoudre ce problème.
Merci.

[aliasjcdenton]

Bonjour,

Je souhaite également avoir une solution à ce problème.

Connaissez-vous des liens sur Internet à des cours de calcul vectoriel, polygonal pour m'aider à résoudre ce problème ?

Je pense qu'il serait possible de décomposer le polygone ne triangle comme exposé ici : http://www.siggraph.org/education/materials/HyperGraph/scanline/outprims/polygon1.htm

Puis de tester si le point est dans un des triangles...

Merci d'avance.

[Lierre Aeripz]

Voici un algorithme bien connu. Il n'est peut-être pas aussi efficace que les algorithmes les plus performant, mais ça peut être suffisant.

Il est facile de tester si un segment intersecte une demi-droite.
Voici l'algorithme : on considère une demi-droite quelconque partant du point dont on veut tester l'appartenance au polygone. On compte le nombre de fois où cette demi droite intersecte le bord du polygone, c'est-à dire le nombre de segment (parmis ceux qui forment le polygone) qui coupent la demi-droite. Si ce nombre est pair, le point est à l'extérieur. Si ce nombre est impair, le point est à l'intérieur.

[mathelot]

bjr,

cet algo n'est fiable à 100%. Il y a des exemples où ça ne marche pas.

[aliasjcdenton]

Bonjour et merci pour vos réponses,

J'ai effectué quelques recherches sur Internet et ai trouvé les choses suivantes :

- Si un point est dans un polygone, la somme des angles qu'il forme avec les sommets du polygone est égale à 2pi (360 deg) (Attention à orienter les angles !) --> calcul grâce aux nombres complexes :
- http://www.yaronet.com/posts.php?s=32513 et
- http://fr.wikipedia.org/wiki/Nombre_complexe
- Méthode de la droite (celle décrite par Lierre Aeripz) : http://en.wikipedia.org/wiki/Point_in_polygon
- Sans doute d'autres que je n'ai pas trouvées...

Et puis miracle en fouillant encore un peu ! : il existe une classe java (car c'est avec ce langage que je fais mon projet) permettant la manipulation de polygones et même une méthode permettant de tester l'appartenance d'un point à un polygone (géré grâce à des tableaux de coordonnées de points) :
http://java.sun.com/javase/6/docs/api/java/awt/Polygon.html

Merci encore pour vos réponses !