Appartenance d'un point à un ensemble géométrique - Page 1

Bonjour tout le monde, voici mon problème.

Prenez un plan en deux dimensions aux abcisses et ordonnées respectives allant de 0 à 900 et de 0 à 500.

Prenez un point P situé en [10,10] (10 en abcisses, 10 en ordonnées).

Prenez un carré (pas tracé de côté) dont les angles vont de [5,5] à [15,15].
Pour savoir si le point est au centre de manière algorithmique, c'est simple :

Si (P[x]>=5 et P[x]<=15 et P[y]>=5 et P[x]<=15) Alors on est OK !

Vous me suivez toujours.

Pour savoir si le point est dans un cercle de rayon 10 placé en [10,10]. Ca reste simple.

Maintenant, voici où se situe mon problème.

J'aimerais tracer des zones complexes, genre des polygones. Par exemple, un polygone aux points [3,3][8,7][12,10][6,15][4,11].

Comment savoir (algorithmiquement parlant, si mon point P est situé dasn ce polygone à l'aide de ces points ?

Je vous remercie pour votre précieuse aide.


Nota Bene : L'application de cet algorithme est faite à des fins graphiques. Les unités des point sont des entiers positifs, donc il n'y aura pas de demies unités ou autres subtilités. Chaque point représentera 1 pixel. Vous me direz : "on pourrait dasn ce cas faire une représentation graphique du placement de ces points et voir s'il y a collision ou non de pixels". Que nenni ! Je voudrais savoir si vous avez/connaissez des méthodes de calcul afin de résoudre ces problèmatiques. Merci d'avance.

Pour un ensemble convexe, toute droite passant par ton point (si il est a l'intérieur) intersecte exactement deux fois des facettes "opposées pour cette direction".

Pas dans ce cas pourtant ?



On est bien dans ce que tu appelles du "convexe".

Ne parlais-tu pas d'angles aïgus ou obtus ?

si ton polygone est convexe :
ya un algo en n^3 : pour tous les triplets de points, tu regardes si le point appartient à ce triangle
sinon tu peux faire faire "Graham" en ayant tes points "dans l'ordre" : tu fais les couples de points qui sont reliés et tu regardes l'angle qui est fait avec le 3e point (le point à determiner).
ah, l'enveloppe convexe
edit:

Tient c marrant c mon sujet de centrale Supelec en MP l'année derniere
regarde la partie 1

http://centrale-supelec.scei-concours.org/CentraleSupelec/2005/MP/sujets/info.pdf

Trofor... sauf que moi je me suis arrêté au BTS et ça fait mal au cul un peu de se replonger dans le truc. Merci beaucoup en tout cas pour toutes ces explications et n'hésitez pas à en rajouter si ça vous démange.

Ah le concours centrale...

Je +1 nTOME.

3 >> nTome, je viens de lire ton MP puis t'ai remercié pour ton aide... mais en fait... j'avais pas compris... alors attends... ... près de 2 heures après j'ai compris !
Yahooooo. C'est simple comme tout en fait, merci encore.
Dans le prochain post, je pourrais vous mettre des images de ce que j'ai compris si vous le souhaitez ?

Non, en fait, voici avec la première méthode de nTome le genre d'exceptions qui ne peut fonctionner :


(le polygone est convexe ?)

Par contre, j'ai deux question supplémentaires :
- la méthode de "Graham" s'applique-t-elle pour tous types de polygones.
- toujours "graham", les trois angles doivent-ils tous être <180° (j'avoue avoir plus ou moins compris en fait cette seconde méhode).

Merci

Edit, je m'étais trompé d'image... rafraîchissez !

ben ici le polygone est convexe et ça marche parce que si tu fais comme sur le dessin que j'ai fait avant, aucune fois "ça ne tournera à droite" (j'aurais dû montrer cet exemple) donc le point est inclu dans "l'enveloppe convexe". Si ça tourne au moins une fois, c'est dehors, donc tu peux t'arrêter. Un polygone n'est pas convexe si un angle est supérieur à 180°.
et euh quels 3 angles ? (il faut continuer après, tu t'arrêtes quand t'es revenu au point de départ (tu fais "le tour" du polygone une fois) (à moins que "ça tourne à droite" avant la fin))

Donc selon que le polygone soit concave ou convexe il faut que j'applique une de ces 2 différentes méthodes et là je pourrais vérifier mes tests ?

Récapitulons :
Si le polygone est convexe (uniquement des angles convergents), j'applique la méthode "Graham".
Si le polygone est "concave" (???), on applique le "truc des triangles" ?

hum c'est pas dans le cours
non aucun des 2 ne marchent pour les polygones pas convexes et euh je sais pas comment on fait pour ceux-là

Bon, ce que je vais faire... c'est laisser quelques images en attendant que quelqu'un me file un coup de main s'il sait comment s'y prendre... prendant ce temps, je Google-ise et je me tripote la noulle en eespérant qu'une ampoule 35Watts apparaîssent au dessus de ma boîte crânienne chaude.

Cas 1 :


Cas 2 :


Cas 3 :


Cas 4 :


Naaaaaan, j'rigoooOOole, pas le 4 !

Pour le cas 3, si tu arrives à décomposer ton polygône sous la forme de triangles, c'est bon !

ex-Miles :
Pour le cas 3, si tu arrives à décomposer ton polygône sous la forme de triangles, c'est bon !

Malheureusement non... je peux te découper ça, mais ce n'est pas la solution malheureusement.

Salut,

Je m'étais aussi intéressé à ce type d'algo il y a quelques temps ( pour Edit3D )
J'ai jamais testé, mais voilà la méthode que j'avais retenue :



Tu traces une ligne horizontale ( en bleue ) passant par le point ("P") à tester. Tu considères les intersections entre cette ligne bleue et les côtés du polygone, mais seulement les intersections à gauche du point P.
Tu dénombres ces intersections, et s'il y en a un nombre pair, P est à l'extérieur du polygone, sinon il est à l'intérieur.

Ainsi pour le point "P" du haut, il y a un seul point d'intersection, le point est déclaré à l'intérieur.
Pour le point "P" du bas, il y a deux points d'intersection, le point est déclaré à l'extérieur.

Cette méthode est très générale, elle marche pour les polygones concaves, et même pour ceux avec des trous dedans
Après c'est surement pas très facile à implémenter ...

A6 est oublié sur l'image, mais est dans la commissure de la bouche du Pacman.


Par exemple, P1 et , appartiennent à A1, A3, A5 pourtant, P2 est en dehors.
De +, si je procède par la suite d'angles et que coup à coup je regarde si nous sommes dans les triangles :
Pour P1, il est dans A2,A3,A4 et aucune autre suite.
P2 quand à lui est dans la suite A5,A6,A7.

Si on procède de manière anarchique, P2 est dans un grand nombre de triangles (A8,A4,A3/A2/A1 - A7,A4,A3) ainsi que P1 (A1,A3,A8/A7/A5).

La suite de triangles n'est donc pas une solution, la méthode "anarchique" non plus. La méthode "Graham" quand à elle, ne fonctionne qu'avec les formes convexes.

15 >> Merci, je crois que je tiens le bon bout. Je vais voir comment "algorithmiser" ça. La méthode est nickel en tout cas... et une fois de + très simple.

lol, on a posté en même temps !
Au fait, juste par curiosité, pourquoi t'as besoin de cet algo ?

Ah oui, par contre, David, pour ta méthode... elle ne prend pas en compte (eheheh diabolique) que si ta droites tapes un "coin"... mais bon... programmation-programmation.

david :
lol, on a posté en même temps !
Au fait, juste par curiosité, pourquoi t'as besoin de cet algo ?

Par MP, à condition que tu le répètes pas

>elle ne prend pas en compte (eheheh diabolique) que si ta droites tapes un "coin"
très juste, mais ça peut se détecter facilement ( un coin n'appartient après tout qu'à deux droites )

>Par MP, à condition que tu le répètes pas
Pas de problème Bon courage en tout cas !

La méthode de Graham (complexité N) et celle des triangles (complexité N^3 ) donnent les mêmes résultats :
- un point hors d'une enveloppe (convexe ou non) sera bien détecté dehors
- un point dans une enveloppe convexe sera bien détecté dedans
- un point dans une enveloppe convexe pourra, selon sa 'zone de visibilité' (je ne sais pas comment appeler ça autrement, et, bizarrement, c'est un truc que j'ai vu en cours de PSI (enfin je crois)), être détecté dedans ou dehors pas glop ...

Le seul truc qui marche à coup sûr, c'est d'utiliser la version généralisée de ce que nEUrOO a dit en ./2, à savoir :
* Toute demi-droite partant du point considéré et non tangente à l'enveloppe coupera celle-ci :
- un nombre pair de fois si le point est à l'extérieur de l'enveloppe
- un nombre impair de fois si le point est à l'intérieur de l'enveloppe

L'algo (de complexité N) ressemblera donc à :
1/ choisir une direction quelconque (par exemple, verticale ascendante )
2/ vérifier qu'aucun sommet (point anguleux qui peut faire office de point tangent) de l'enveloppe ne se trouve sur la demi-droite, sinon, revenir en 1/ et choisir une autre direction (verticale descendante, horizontale gauche, horizontale droite ... ce ne serait vraiment pas de bol que ces 4 directions ne conviennent pas) (pour verticale ascendante, on boucle si Xsommet == Xpoint && Ysommet > Ypoint (si Ysommet == Ypoint, alors le point est confondu avec le sommet ... est-il à l'intérieur ou à l'extérieur ? A toi de définir ta convention))
3/ pour chacun des N segments :
a) établir l'équation de la droite correspondante
b) si la droite est parallèle (ici verticale) à la demi-droite, boucler au segment suivant (pas d'intersection)
.. sinon, déterminer le point d'intersection entre la droite et la droite (complète) portée par la demi-droite (pour être sûr d'obtenir une intersection
c) si le point d'intersection est sur la demi-droite (Yintersect > Ypoint) et à l'intérieur du segment (attention au cas particulier des segments horizontaux, on ne peux pas faire YsommetA < Yintersect < YsommetB), incrémenter le compteur d'intersection (initialisé à 0 avant le 3/ ) (si le point est sur le segment, pareil, est-il dedans ou dehors ?)
4/ regarder la parité ... tadam !!!

Et voilà !

[edit]Erf !
Je discute, je discute, le tout pendant que je tape mon post, et paf, je me fais griller ...[/edit]

Ton post est plus détaillé, le mien il a un joli dessin, on se complète parfaitement

tous !

Ouais mais là j'étais en cours d'algo, donc je me voyais mal comment justifier au prof la réalisation d'un dessin ...
Un pavé de texte, ça passe, mais le dessin ...
Et de toute façon, je n'avais pas envie de faire un dessin !
Mais c'est vrai que c'est beaucoup plus joli avec !

montreuillois :
Pas dans ce cas pourtant ?



On est bien dans ce que tu appelles du "convexe".

Ne parlais-tu pas d'angles aïgus ou obtus ?

J'ai dit toute droite...
Sinon, faudrait peut-etre tirer aléatoirement N/2 directions de droites et tester que tu as bien a chaque fois 2 intersections.