Point dans region (geometrie)Résolu

Question

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

cs_juju12 · Accepted Answer

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.

luhtor · Answer

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.

cs_juju12 · Answer

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é.

luhtor · Answer

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.

luhtor · Answer

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é

24Karas · Answer

Merci pour toutes vos idées !
je vais voir ce que je peux dev dès que j'ai un peu de temps :-)

Zakata · Answer

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

Zakata · Answer

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

Point dans region (geometrie)

8 réponses

Votre réponse

Discussions similaires