Point dans region (geometrie) [Résolu]

Signaler
Messages postés
233
Date d'inscription
jeudi 4 juillet 2002
Statut
Membre
Dernière intervention
5 juillet 2008
-
Messages postés
59
Date d'inscription
lundi 21 août 2006
Statut
Membre
Dernière intervention
17 juillet 2009
-
Bonjour.

J'ai un petit probleme pour trouver un algo qui fonctionne bien. Voilà le probleme : 
j'ai un point de coordonnées x et y // point(x,y)
J'ai mon plan qui est découpé en un ensemble de polygones qui peuvent avoir un nombre de cotés différents. Exemple : des rectangles, des losanges, ... Pour chaque polygome je connais tout les points. Les polygomes ne se chevauchent pas. En gros le point ne peut etre que dans un seul polygone à la fois

Comment trouver à partir du x et y du point dans quel polygome est mon point ?

Merci pour toute suggestion

++
24K

8 réponses

Messages postés
966
Date d'inscription
samedi 3 avril 2004
Statut
Membre
Dernière intervention
4 mars 2010
4
Salut
C'est pas évident, surtout si tes polygones sont un peu complexes; quelques suggestions tout de même si ton maillage est fixe:
tu peux découper (une fois pour toutes en début de prog) chaque polygone en triangles élémentaires beaucoup plus simples à tester; également tu peux faire un deuxième découpage (en plus, toujours début de prog) du plan en carrés ou rectangles qui te donnera un tableau où tu stockeras les indices des polygones qui sont en contact avec le carré, ce qui te permettra plus tard, en fonction de la résolution, de tester beaucoup moins de polygones.
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
5
C'est pas si compliqué...

Donc pour chaque polygon, tu vas tester si ton point est dedans. Donc je viens d'imaginer un test pour gérer n'importe quelle forme, il me semble de marcher, mais faudrait y réfléchir un peu plus.

En fait si tes polygones sont convexes, c'est simple, et je détails meme pas (voir produit scalaire).
Si tes polygones sont qcq, l'idée est de tracer un segment qui part de ton point avec chaque point du polygone en cours de test.
Si ce segment intersecte un nombre impaire de segments du polygon, alors il est à l'intérieur, sinon il est a l'extérieur.
Messages postés
966
Date d'inscription
samedi 3 avril 2004
Statut
Membre
Dernière intervention
4 mars 2010
4
Par 'pas évident' j'entendais coûteux en temps d'exécution. Luthor, ton test marche très bien mais il risque d'être un peu long s'il y a beaucoup de polygones...cependant il aura l'avantage de marcher même si le pavage évolue au cours du temps, contrairement à ce que j'ai proposé.
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
5
C'est vrai que le test est un peu couteux, mais on peut optimiser l'algorithme facilement rien qu'en intégrant des boundings. On augmente considérablement et facilement les performances de l'algo. Mais bon, c'est à lui de voir apres, suivant ses besoins.
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
5
Juste une petite correction, il suffit en fait de tester qu'un seul point du polygone:
si le segment partant de ton point a tester et passant par un point de ton polygone (n'importe lequel), intersecte un nombre impaire de fois le ton polygone, alors il est à l'intérieur, sinon il est à l'extérieur.

Hypothèses:
- le polygone ne se coupe pas lui meme
- le polygone est fermé
Messages postés
233
Date d'inscription
jeudi 4 juillet 2002
Statut
Membre
Dernière intervention
5 juillet 2008

Merci pour toutes vos idées !
je vais voir ce que je peux dev dès que j'ai un peu de temps :-)
Messages postés
59
Date d'inscription
lundi 21 août 2006
Statut
Membre
Dernière intervention
17 juillet 2009

J'ai trouvé un contre exemple : le point (*) intersecte un nombre paire de segment du polygone
_______________
|        *                  |
___________       |
                      |      |
___________|      |
|        __                |
____/    \________

<hr size="2" width="100%" />*Les fautes d'orthographes jointes à la présente missive, sont la propriété exclusive de l'auteur. Toute copie illégale pourra être passive de poursuites judiciaires, et soumises à des peines et sanctions exemplaires
Messages postés
59
Date d'inscription
lundi 21 août 2006
Statut
Membre
Dernière intervention
17 juillet 2009

bon le polygone est mal passé,  les | de droite sont alignés verticalement. Le polygone ressemble à un "u" couché sur le coté avec une ouverture en forme de "^" sur le segment inférieur.

<hr size="2" width="100%" />*Les fautes d'orthographes jointes à la présente missive, sont la propriété exclusive de l'auteur. Toute copie illégale pourra être passive de poursuites judiciaires, et soumises à des peines et sanctions exemplaires