Discussion :

[Mucho]

Bonjour, bonjour,

pour trouver si un point est dans un polygone j'aimerai utilisé la méthode qui consiste a faire la somme des angles (voir ici pour explications) mais cet algorithme a pour but d'être implémenté en c++ et je me disais que calculer chaque angle doit prendre pas mal de temps pour beaucoup de polygones.

Donc, je me demandais si il est possible d'utiliser cette méthode sans calculé complètement chaque angle mais avec des outils plus adapté au calcul par ordinateur (ie en utilisant des matrices ou produits scalaires, vectoriels).

[ToTo13]

Bonjour,

cette question a déjà été posé plusieurs fois sur ce forum.

Pour ma part, regarder le signe des angles est une très bonne méthode, que j'utilise dans le calcul d'enveloppes convexes...

[larnicebafteur]

Déjà traité ici :

http://www.developpez.net/forums/sho...point+polygone

[Mucho]

Hum en fait non, le titre n'est peut être pas adapté, désolé,

comme je le disais j'ai déjà la solution je voudrais savoir si il y a des manières efficaces de la réalisée. (cf premier message)

[ToTo13]

Bonjour,

tu dois calculer autant d'angle que de points constituant le polygone. Donc tu es en O(n). C'est tout à fait correcte.

[plegat]

A la limite, tu peux limiter le nombre de polygones à tester en utilisant par exemple un octree (si tu es en 3D, sinon tu fais l'équivalent en 2D, un quadtree).
Tu testes ensuite dans quelle partie de l'octree se trouve ton point (plus facile et rapide à mon avis de tester si un point est dans un cube), et ensuite de tester uniquement les polygones de cette partie de l'octree.

Sinon, en 2D, tu peux également définir une boite englobante de ton polygone (qui sera définie en même temps que le polygone, histoire de ne pas la calculer à chaque fois), et déjà tester si ton point est à l'intérieur. Si il y est, tu fais ton test sur les angles, sinon tu passes au polygone suivant.

Et tu peux aussi coupler les deux, quadtree+boite englobante...