Point dans un polygone

[kerinel]

Bonjour,
j'ai pu voir que le moyen le plus utilisé pour déterminer si un point appartient à un polygone est de déterminer le nombre de fois où on intersecte un coté du polygone pour rejoindre un point extérieur.
Mais il semble aussi que cette méthode n'est pas forcément très rapide car très généraliste sachant qu'il faut avant tout s'assurer que on n'est pas sur un des cotés, que on ne va pas à un moment ou un autre se superposer à un coté (donc vérifier la pente avant)...

Ma question est donc y -a-t-il moyen de
-soit rendre le traitement plus efficace en faisant des précalculs
-soit d'appliquer un autre algorithme

Sachant que (c'est important):
- Mon polygone sera toujours le même (c'est le point qui change), (donc je peux par exemple calculer a l'avance toutes les pentes de toutes les arrêtes du polygone mais y-a-t-il d'autre truc que je peux précalculer ?)
- mon polygone est quelconque (convexe ou concave) mais non croisé.

Une fois que l'utilisateur aura dessiné son polygone, il ne changera pas pour le restant de l'application, par contre il sera souvent demandé si un point est ou non à l'intérieur, je peux donc utiliser un peu de temps juste après la création pour faire beaucoup de calcul si cela permet d'avoir une réponse plus rapide après.

N'y-a-t-il pas par exemple intérêt à découper le polygone au préalable ?

merci pour votre aide,

Bon code,
kerinel

[Kangourou]

Salut,

pour les differentes methodes, la page suivante est pas mal :
http://local.wasp.uwa.edu.au/~pbourk...ry/insidepoly/

Perso j'ai une preference pour la solution basée sur le calcul de la somme des angles entre le point et chaque sommet (solution 2 sur le lien), que je trouve plus generale et qui evite les tests de cas particuliers.

Sinon si ton polygone est bien defini au depart, tu peux utiliser le rectangle englobant, qui te permet de savoir rapidement si un point eloigne n'est pas dans le polygone.

A+

[kerinel]

Bonjour et merci pour la réponse rapide.
Oui j'ai vu cette page très intéressante.
effectivement la méthode par les angles est peut être plus rapide (surtout qu'il doit bien y avoir un truc facile pour les angles en JAVA ).
Pour le rectangle englobant ben que la surface de dessin est juste assez grande pour le polygone, il a peu de chance d'être loin, à moins d'être dans une belle découpe. Du coup, je pense que je vais perdre du temps si je ne me limite que à cela.
Par contre je me dois de préciser qu'il y a beaucoup de chance que le polygone (qui représente en fait un réseau de train) puisse être découpé en beaux rectangles avec seulement quelques triangles en prime.
Du coup est-ce que je n'ai pas intérêt à prédécouper le réseau puis faire des tests successifs genre :

Code :

1
2
3
4
si x<a testPartieGauche
sinon si x > b testPartieDroite
sinon testePartieCentre

avec testPartiexxx construite sur le même modèle avec y et en final ou je me retrouve dans un rectangle (soit dehors, soit dedans), ou je me retrouve dans un triangle et je ne dois faire le test que pour 3 cotés.
Sachant que les si sinon si sinon sont peut être plus gourmand en temps ? Et qu'en plus je devrais faire méthode bien corsé pour découper correctement mon polygone...

Merci pour vos avis,

bon code,
kerinel

[pseudocode]

Comme je l'ai déja dit dans un autre post, je prefere le winding number.

C'est une variante du "nombre de cotés traversés", qui est plus robuste dans les cas tordus (sur/près des cotés) et qui permet de n'utiliser que des entiers si on est dans le cas discret (pixels).

[Kangourou]

Envoyé par pseudocode

Comme je l'ai déja dit dans un autre post, je prefere le winding number.

On est bien d'accord ! Le calcul des angles correspond au Winding number...
Cela dit le code que tu donnes calcule uniquement le signe du determinant, ce qui est plus rapide que le calcul d'angle par atan.

[kerinel]

Bonjour et merci pour vos avis éclairés.
Je viens de trouver ceci :
http://java.sun.com/javase/6/docs/ap...geom/Area.html

ça devrait répondre encore plus facilement que je ne le pensais à mon problème.

Bon code,
kerinel