Discussion :

[adiiii]

Bonjour,
Je dois développer un code qui teste la présence d'un point dans un polygône quelconque. Le point étant représenté par ses coordonnées (x,y) : on travaille dans un plan. Le polygône est représenté par une liste ordonnée de points qui permet sa construction : si les points sont P1,P2,P3,P4,P5, on relie d'abord P1 à P2, puis P2à P3... et enfin P5à P1.
Tout ça doit être fait en C, mais si vous avez la moindre idée, ...
Je vous remercie !

[Ange_blond]

ce n'est pas tellement difficile

Voilà une méthode :
Tu aura besoin d'une fonction qui teste l'intersection de 2 segments.
(genre tu utilise les equations de droite pr détecter l'intersection... tu as meme pas besoin de savoir le point exact dans ce cas là)

Ensuite tu défini un nouveau segment depuis ton point jusqu'a n'importe quel point tres loin (en dehors du polygone) (genre un nouveau point vers les infini)

Ensuite tu teste l'intersection de ce nouveau segment avec chacun des segments de ton polygone (P1P2, puis P2P3....)

Si il y a intersection (ET UNE SEULE) alors tu es à l'intérieur. (donc faut les compter toutes pour etre sur car un nbre pair d'intersections sginifie que tu es en dehors)



Autre méthode tu fait la somme des angles de ton point vers chaque point du polygone... si = 360 tu es dedans (enfin je crois)

[babar63]

Voilà une méthode :
Tu aura besoin d'une fonction qui teste l'intersection de 2 segments.
(genre tu utilise les equations de droite pr détecter l'intersection... tu as meme pas besoin de savoir le point exact dans ce cas là)

Ensuite tu défini un nouveau segment depuis ton point jusqu'a n'importe quel point tres loin (en dehors du polygone) (genre un nouveau point vers les infini)

Ensuite tu teste l'intersection de ce nouveau segment avec chacun des segments de ton polygone (P1P2, puis P2P3....)

A préciser quand même que ce n'est pas pour un polygone quelconque mais convexe... Pour la deuxième méthode je ne sais pas (je suppose que c'est pareil non?). Sinon une autre méthode (plus rapide?), pour chaque arêtes : Soit P le point à tester, N la normale de l'arête, et A un point de l'arête, alors si le produit scalaire : N.AP >= 0 (Tout ce beau monde doit être normalisé), tu es à l'intérieur(de l'arête courante).

[Ange_blond]

le test par intersection fonctionne pour n'importe quel type de polygone si je ne me trompe pas...

[babar63]

le test par intersection fonctionne pour n'importe quel type de polygone si je ne me trompe pas...

Euh c'est que j'ai du mal comprendre lorsque tu disais :

Si il y a intersection (ET UNE SEULE) alors tu es à l'intérieur. (donc faut les compter toutes pour etre sur car un nbre pair d'intersections sginifie que tu es en dehors)

Si le nombre d'intersections est impair alors en effet ca fonctionne pour n'importe quel type de polygone, en revanche si l'on s'arrête à "UNE SEULE" intersection alors ça ne fonctionne que pour les polygones convexes

[babar63]

Ensuite tu défini un nouveau segment depuis ton point jusqu'a n'importe quel point tres loin (en dehors du polygone) (genre un nouveau point vers les infini)

Il me semble que dans ce cas il serait préférable de considérer l'intersection entre une droite horizontal (pourquoi s'embêter avec des points "très loin"...) et l'arête en question, ça devrait également facilité le calcul d'intersection