Discussion :

[Rodrigue]

Bonjour,

Pour un de mes développements, je dois savoir si un point se trouve à l'intérieur d'un polygone fermé ...
Je possède la liste des n points du polygone: p0, p1, ... pn-1.
Comme il s'agit d'un polygone fermé: p0 = pn <=> (x0,y0) = (xn, yn).

Je me sers donc de n + 1 points mais l'utilisateur n'en fournit que n.

Quelqu'un pourrait m'aider svp? Je suis câlé...

@+,
Rod

[Rodrigue]

Je pense p-e avoir un début de piste.
Lorsqu'un point est à l'intérieur d'un polygone, la somme des angles entre ce point et les points constituants le polygone est égale à 360°.

Est-ce que c'est correct?

[souviron34]

Je pense p-e avoir un début de piste.
Lorsqu'un point est à l'intérieur d'un polygone, la somme des angles entre ce point et les points constituants le polygone est égale à 360°.

Est-ce que c'est correct?

non..

C'est juste si le polygone est convexe..


http://www.faqs.org/faqs/graphics/algorithms-faq/

sujet 2.03

[jabbounet]

Se ramener a un cas que tu sais calculer facilement le triangle.

Si tu sais décomposer ton polygone en triangles, alors il te suffit de calculer si le point est dans l'un des triangles.

http://www.siggraph.org/education/ma...s/polygon1.htm

http://fr.wikipedia.org/wiki/Triangu...39;un_polygone

mais elle est moins efficace que celle de souviron je pense.

[souviron34]

Se ramener a un cas que tu sais calculer facilement le triangle.

Si tu sais décomposer ton polygone en triangles, alors il te suffit de calculer si le point est dans l'un des triangles.

pourquoi se compliquer la vie ??

http://www.siggraph.org/education/ma...s/polygon1.htm

Regarde la complexité des calculs...

http://fr.wikipedia.org/wiki/Triangu...39;un_polygone

Cet algorithme a une complexité en O(n log n).

L'algo cité est en O(N), avec une complexité simple.




NB: la triangulation peut être une très bonne méthode pour plein de choses, mais la meilleure méthode à mon sens est celle de Delaunay (les triangles les plus équilatéraux (ou isocèles) possibles et les plus "égaux").. Mais pour ce genre de problème c'est un peu prendre un marteau pour écraser une mouche..

Quant au problème de découper en triangles un polygone, le poids tient au fait que chque sommet participe pour 3 fois aux calculs : 2 fois à chaque extrémité de la base et 1 fois en tant que sommet du triangle..

[jabbounet]

pourquoi se compliquer la vie ??
Regarde la complexité des calculs...
L'algo cité est en O(N), avec une complexité simple.

NB: la triangulation peut être une très bonne méthode pour plein de choses, mais la meilleure méthode à mon sens est celle de Delaunay (les triangles les plus équilatéraux (ou isocèles) possibles et les plus "égaux").. Mais pour ce genre de problème c'est un peu prendre un marteau pour écraser une mouche..

Quant au problème de découper en triangles un polygone, le poids tient au fait que chque sommet participe pour 3 fois aux calculs : 2 fois à chaque extrémité de la base et 1 fois en tant que sommet du triangle..

C'etait juste pour signaler son existence, tu as oublié de reprendre le

mais elle est moins efficace que celle de souviron je pense.

[Nemerle]

Si O est le point & P1...Pn le polygone, sommer les angles consécutifs PiOPi+1. Si congru à 2pi, c'est dedans.

[pseudocode]

Si O est le point & P1...Pn le polygone, sommer les angles consécutifs PiOPi+1. Si congru à 2pi, c'est dedans.

Ca m'a l'air bien robuste aux erreurs d'arrondi ca.

Sinon je propose (encore et toujours) mon ami le Winding Number.

[Jean Dumoncel]

Salut!

Si O est le point & P1...Pn le polygone, sommer les angles consécutifs PiOPi+1. Si congru à 2pi, c'est dedans.

C'était la première idée de Rodrigue, et comme l'a dit souviron34, ça ne fonctionne que sur des polygones convexes (enfin en tout cas sur des polygones un peu tordu, ça ne marche plus)... mais bon ça dépend aussi des besoin de Rodrigue, si ça se trouve on cherche compliqué alors que ces polygones sont peut-être des polygones réguliers...

Sinon je propose (encore et toujours) mon ami le Winding Number.

Juste pour info, tu l'appliquerais comment dans le cas présent?
J'ai rapidement lu ce que c'était sur Wikipedia et apparemment, il faut connaître une équation paramétrique de la courbe, donc ici ce serait quoi l'idée? paramétrer tous les segments qui forment le polygone pour pouvoir ensuite appliquer l'algo tranquillement?

[pseudocode]

Juste pour info, tu l'appliquerais comment dans le cas présent?
J'ai rapidement lu ce que c'était sur Wikipedia et apparemment, il faut connaître une équation paramétrique de la courbe, donc ici ce serait quoi l'idée? paramétrer tous les segments qui forment le polygone pour pouvoir ensuite appliquer l'algo tranquillement?

Ah quel dommage. T'as pris le 1er lien dans Google, et ta réponse était dans le second : winding number

[Jean Dumoncel]

Ah quel dommage. T'as pris le 1er lien dans Google, et ta réponse était dans le second : winding number

Ca m'apprendra à être fainéant...

du coup c'est out de suite plus simple à implémenter, elle me plaît bien cette méthode!

[Nemerle]

C'était la première idée de Rodrigue, et comme l'a dit souviron34, ça ne fonctionne que sur des polygones convexes (enfin en tout cas sur des polygones un peu tordu, ça ne marche plus)...

Pas vrai, cela fonctionne avec n'mporte quel polygone! Petit oubli de ma part, la somme des angles doit être de la forme 2*k*pi avec k IMPAIR.

Pseudocode, le problème des arrondis ne doit effectivement pas être sous-estimé

[Jean Dumoncel]

Pas vrai, cela fonctionne avec n'mporte quel polygone! Petit oubli de ma part, la somme des angles doit être de la forme 2*k*pi avec k IMPAIR.

Oui j'ai parlé un peu vite, c'est juste (surtout avec le rajout)...

[souviron34]

C'etait juste pour signaler son existence, tu as oublié de reprendre le

j'avais pas oublié, j'avais mis des smileys

Ah quel dommage. T'as pris le 1er lien dans Google, et ta réponse était dans le second : winding number

ce qui revient à l'algo cité, qui compte le nombre de traversées..

[pseudocode]

ce qui revient à l'algo cité, qui compte le nombre de traversées..

Oui et Non.

Non, car le nombre de traversées (Crossing Number) ne tient pas compte du sens (trigo/horaire) du coté traversé. Ce qui pose un problème dans le cas de polygone croisé.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 _______________
|    _____      |
|   |     |     |
|   |  X  |     |
|   |_____|_____|
|_________|

[souviron34]

Oui et Non.

Non, car le nombre de traversées (Crossing Number) ne tient pas compte du sens (trigo/horaire) du coté traversé. Ce qui pose un problème dans le cas de polygone croisé.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 _______________
|    _____      |
|   |     |     |
|   |  X  |     |
|   |_____|_____|
|_________|

c'est exact, mais j'avais "approximé" l'algo..

Si tu le regardes de près, tu vois qu'il en tient compte (à cause des inégalités) ..