point à l'interieur d'un polygone(3D-équations paramétriques

Version imprimable

09/12/2005, 11h27
chonos

point à l'interieur d'un polygone(3D-équations paramétriques

bonjour a tous,

je chercherai a savoir si un point est a l'interieur d'un polygone definit par une liste de sommets dans un espace 3D mais pour cela je ne dois pas utiliser la méthode des angles mais plutot des équations paramétriques
du genre
x(t) = x1 + t * (x2 -x1)
y(t) = y1 + t * (y2 -y1)
z(t) = z1 + t * (z2 -z1)

merci
09/12/2005, 16h35
chonos

personne pour m'aider??

vous comprenez pas ce qu'il faut faire ou vous ne savez pas le faire?
09/12/2005, 16h55
plegat

Salut,

Citation:

Envoyé par chonos

vous comprenez pas ce qu'il faut faire

Moi je ne comprends pas trop...

Citation:

Envoyé par chonos

x(t) = x1 + t * (x2 -x1)
y(t) = y1 + t * (y2 -y1)
z(t) = z1 + t * (z2 -z1)

C'est l'équation d'une droite ça... ça va être chaud pour trouver ton point... elle correspond à quoi ta droite? Que sont les points 1 et 2?

Ton polygone, c'est un polygone plan ou non-plan? (vu qu'on est en 3D...)
10/12/2005, 03h12
j.p.mignot

Il me semble - sous toutes reserves - que on peut
1- tres facilement calculer l'aire algébrique du polygone à n sommets
2- calculer l'aire algébrique du polygone à n+1 sommets constitué des n sommets + le point à tester
3- vérifier le sens de variation de la surface.
10/12/2005, 12h49
chonos

Moi je pensé qu'il fallait déterminer un point p1, tracer la demi-droite partant du point que l'on teste p2 passant par p1, calculer le nombre d'intersection avec les faces : si c'est impair le point est dans le polygone, si c'est pair il est à l'exterieur.

c'est la théorie en pratique je ne vois pas comment calculer le nombre d'intersection avec les faces du polygone meme si je peux savoir si deux droites se coupent en 3D.
je me demande si il n'y a pas une histoire de colinéarité de vecteurs mais c un domaine que je ne maitrise pas du tout.

nb : g mis l'equation d'une droite paramétrique juste pour rappel
10/12/2005, 13h24
plegat

Citation:

Envoyé par chonos

Moi je pensé qu'il fallait déterminer un point p1, tracer la demi-droite partant du point que l'on teste p2 passant par p1, calculer le nombre d'intersection avec les faces : si c'est impair le point est dans le polygone, si c'est pair il est à l'exterieur.

C'est une idée...

Citation:

Envoyé par chonos

c'est la théorie en pratique je ne vois pas comment calculer le nombre d'intersection avec les faces du polygone meme si je peux savoir si deux droites se coupent en 3D.

Il faudrait clarifier les choses... ton polygone est formé de quoi? D'une suite de segment ou de faces? Si c'est des faces (auquel cas je ne sais plus trop si on peut encore appeler ça un "polygone"...), ta droite va intersecter un plan, et pas une droite. Il te faut donc rechercher le point d'intersection entre ta droite p1p2, et le plan formé par les points de ta face de polygon (en passant, quel type de face? triangle? quadrangle?)

Tu écris les équations de ton plan et de ta droite sous forme paramétrique (en ne prenant pas le même paramètres pour les deux, tant qu'à faire...), tu poses les égalité pour le points d'intersection (genre x_plan=x_droite, etc etc), et là tu te retrouves avec un système de trois équations à deux inconnues. Trois possibilités, soit une solution unique (intersection), soit pas de solution (droite parallèle au plan), soit une infinité de solutions (droite confondues dans le plan). En cas d'intersection, il faut encore vérifier que le point est à l'intérieur de la face (par exemple en décomposant les coordonnées du point d'intersection dans la base formée par deux des côtés des faces en cas de faces triangulaires)
Il ne te reste plus qu'à faire la manipulation pour toutes tes faces, et à compter les intersections.

En passant, pense à prendre ton point p1 à l'extérieur du polygone (par exemple, prends un des sommets de la boite englobante de ton polygone)
10/12/2005, 13h45
chonos

autant pour moi je vais etre plus précis.
il faut que je détermine si le point appartient a l'interieur d'un contour (qui est une liste de points).
donc on oublie les faces si g bien tout compris.

mais je comprends pas tout et je me demande comment un point qui est à l'intérieur du contour puisse couper obligatoirement une arete??
il peut passer a coté non?
alors que si on parle de face il est obligé de la couper.

SI LES POINTS SONT COPLANAIRES
( si non il faurait définir ce que signifie 'à l'intérieur'
On change de repère si necessaire pour mettre les points dans le pans XOY

Ce petit code devrait répondre au problème ( en tout cas si le polynome de départ n'est pas croisé ce qui n'est pas testé ici.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
 
#define sqr(x) ((x)*(x))
#define Maxs(a, b)                              (((a) > (b)) ? (a) : (b))
#define Mins(a, b)                              (((a) < (b)) ? (a) : (b))
bool Inside (Double X[], Double Y[], short n) // X,Y coordonnées des n sommets 0.. n-1
   {                                          // X[n] et Y[] coordonn(e du point à tester
   Double A = 0, A1=0, Xp = X[n], Yp = Y[n];
   for (short i=0; i < n; i++ ) A += (Y[(i+1) % n] - Y[i])* ( X[(i+1)%n]+X[i]) /2;
   short j1 = -1, j2;
   double D = 1e300;
   // recherche du sommet le + pret
   for (short i=0; i< n; i++ )
      {
      double d = sqr(Xp-X[i]) + sqr(Yp-Y[i]);
      if ( d < D)
         {
         D=d;
         j1=i;
         }
      }
   double D_prev = sqr(Xp-X[(j1-1+n) % n]) + sqr(Yp-Y[(j1-1+n)%n]);
   double D_next = sqr(Xp-X[(j1+1) % n]) + sqr(Yp-Y[(j1+1)%n]);
   if (D_next < D_prev )  j2 = (j1+1) % n;
   else                  j2 = (j1-1+n) % n;
   short k= Maxs(j1, j2);
   j1 = Mins(j1,j2);
   j2 = k;
   if ((j2-j1) == 1)
      {
      for (short i=n-1; i >=j2; i--)
         {
         X[i+1]=X[i];
         Y[i+1]=Y[i];
         }
      X[j2] = Xp;
      Y[j2] = Yp;
      }
   n++;
   for (short i=0; i < n; i++ ) A1 += (Y[(i+1) % n ] - Y[i])* ( X[(i+1)%n]+X[i]) /2;
   return fabs(A) > fabs(A1);   // true si IN
   }

Je n'ai pas vérifié tous les cas mais il devrait fonctionner sur tout polygone non croisé.
Dans le cas contraoire, il serait mis en défaut et il ne teste pas cette situation.

10/12/2005, 17h37
plegat

Citation:

Envoyé par chonos

autant pour moi je vais etre plus précis.
il faut que je détermine si le point appartient a l'interieur d'un contour (qui est une liste de points).
donc on oublie les faces si g bien tout compris.

Ben ça serait plutôt à toi de nous dire si tu travailles avec des faces ou avec des segments!!!
Tu nous as parlé de faces, de droite, d'intersection.... franchement, plus ça va, moi je sais sur quoi tu travailles! :D

Citation:

Envoyé par chonos

mais je comprends pas tout et je me demande comment un point qui est à l'intérieur du contour puisse couper obligatoirement une arete??
il peut passer a coté non?
alors que si on parle de face il est obligé de la couper.

Ben un point, ça ne coupe rien... c'est un point... point!
Après, si tu ne sais pas si il est à l'intérieur ou à l'extérieur, il peut éventuellement se trouver également SUR le contour. C'est une possibilité à envisager pour ton algo, sinon le jour où il rencontrera ce cas de figure, il plantera (ou donnera une réponse fausse).

Tu n'as pas répondu à ma question d'hier... vu qu'apparemment on est revenu sur un polygone formé de segments, peux-tu nous dire si ton polygone est plan ou non?
Si oui, tu peux te ramener à un problème en 2D. En utilisant la même méthode que ce que je t'ai donné précédemment, en travaillant dans le plan du polygone, et en travaillant sur des intersection droite-segment.
Si non, je ne vois même pas comment on va pouvoir définir l'intérieur d'un polygone non-plan, déjà, pour commencer...
10/12/2005, 18h44
maamar

http://www.iag.asso.fr/articles/intersection.htm
10/12/2005, 19h24
chonos

Ben ça serait plutôt à toi de nous dire si tu travailles avec des faces ou avec des segments!!!

>>> j'ai une liste de points. Je peux donc travailler avec les deux.

Tu nous as parlé de faces, de droite, d'intersection.... franchement, plus ça va, moi je sais sur quoi tu travailles!

>>> moi aussi je m'y perd un peu :lol:

Ben un point, ça ne coupe rien... c'est un point... point!
>>> je voulais dire la demi-droite partant de ce point. Sorry

Tu n'as pas répondu à ma question d'hier... vu qu'apparemment on est revenu sur un polygone formé de segments, peux-tu nous dire si ton polygone est plan ou non?

>>> franchement je dois faire une fonction et ca né pas du tout précisé.
>>> c'est surtout pour ca que je ne comprennais pas et que je voulais
>>> utiliser des faces ne comprenant pas trop coment faire avec un
>>> polygone non-plan et des segments
>>> plan. mais je pense k'il s'agit en fait d'un polygone plan.

Si oui, tu peux te ramener à un problème en 2D. En utilisant la même méthode que ce que je t'ai donné précédemment, en travaillant dans le plan du polygone, et en travaillant sur des intersection droite-segment.
Si non, je ne vois même pas comment on va pouvoir définir l'intérieur d'un polygone non-plan, déjà, pour commencer...

>>> je crois bien qu'on touche précisément le problème. mais grace a toi
>>> j'en deduis k'il faille travailler sur un polygone plan et la tout s'éclaire.
>>> je suis désolé mé je pensé k'il fallait travailler sur des polygones
>>> non-plan et des segments d'où mon incapacité a traiter le pb.