[Algo] 2D : Comment savoir si un point se situe entre d'autre ?

2D : Comment savoir si un point se situe entre d'autre ? [Algo] - Algo - Programmation

Marsh Posté le 29-07-2002 à 15:27:20    

Il s'agit tjrs de mon projet en 3D, après avoir reussi à faire les mouvements de la camera (Rotation, Deplacement en avant/arriere et sur les cotés, merci pour l'aide ;p) je cherche maintenant à detecter les collisions.
 
Voilà le schéma du probléme : (Je précise bien qu'il s'agit d'un shéma sur X et Y, Z est exclu).
 
http://www.ifrance.com/yepslide/4pts.JPG
 
Je connais les coordonnées des points A B C D.
 
Je cherche à savoir pour un point E quelconque, si il se situe entre A B C et D (Surface en Vert) ou à l'extérieur (Surface en Marron/Rouge).
 
Jusqu'à maintenant, je n'ai pas encore trouvé de solution... (pourtant j'ai cherché 5 heures d'affilées !)
 
Merci de m'aider :)
 
 

Reply

Marsh Posté le 29-07-2002 à 15:27:20   

Reply

Marsh Posté le 29-07-2002 à 15:31:45    

Petit oublie.
Je voulais rajouté ceci : A,B,C et D sont quelconque aussi.

Reply

Marsh Posté le 29-07-2002 à 15:36:00    

Slide a écrit a écrit :

Petit oublie.
Je voulais rajouté ceci : A,B,C et D sont quelconque aussi.



Si tu considères que ta surface est l'union de 2 triangles (BCD et BAD), espaces chacun délimités par 3 equations (inégalites) tu dois pouvoir tester le point E non?

Reply

Marsh Posté le 29-07-2002 à 15:38:43    

Tel que c'est dessiné, on pourrait se laisser aller à dire qu'il faut qu'il soit dans deux triangles à la fois.
 
:heink: Je me suis fait "griller" l'idée..

Reply

Marsh Posté le 29-07-2002 à 15:40:44    

pas dans les deux à la fois : dans l'un ou l'autre...

Reply

Marsh Posté le 29-07-2002 à 15:43:53    

un truc débil mais qui peut marcher!!
 
tu connais les coord, tu colories les zone.....puis quand tu as E tu te demande quelle couleur a les pixels d'à coté ? et si ils sont vert c'est que E est sur le vert


Message édité par lamatrice le 29-07-2002 à 15:44:35
Reply

Marsh Posté le 29-07-2002 à 15:44:52    

Je ne vois pas tellement comment faire avec l'aide des triangles, vous voulez bien expliquer please :) ?

Reply

Marsh Posté le 29-07-2002 à 15:46:40    

Slide a écrit a écrit :

Je ne vois pas tellement comment faire avec l'aide des triangles, vous voulez bien expliquer please :) ?



un triangle=3 équations du type ax+b<=y
tu as les coordonnées de E donc tu peux tester s'il répond aux équations

Reply

Marsh Posté le 29-07-2002 à 15:47:12    

lamatrice a écrit a écrit :

un truc débil mais qui peut marcher!!
 
tu connais les coord, tu colories les zone.....puis quand tu as E tu te demande quelle couleur a les pixels d'à coté ? et si ils sont vert c'est que E est sur le vert




 
Je ne peux pas faire comme ca non, car, plutard, il y aura l'axe des Z. Sur X et Y, on peut, mais avec le Z, la couleur va changer, elle sera la meme qu'à l'exterieur.

Reply

Marsh Posté le 29-07-2002 à 15:55:26    

si tu veux traiter n'importe quelle surface, il faut la trianguler, puis tester si le point appartient à un des triangles issus de la triangulation.
 
http://www.faqs.org/faqs/graphics/algorithms-faq/
 

Reply

Marsh Posté le 29-07-2002 à 15:55:26   

Reply

Marsh Posté le 29-07-2002 à 15:56:44    

prettysmile a écrit a écrit :

un triangle=3 équations du type ax+b<=y
tu as les coordonnées de E donc tu peux tester s'il répond aux équations




 
Je vois ce que tu veux dire, trouver l'équation des courbes traversant les cotés, puis determiner si le point est bien du bon coté des courbes.
Je vais essayer comme ca, merci encore :)

Reply

Marsh Posté le 29-07-2002 à 15:56:52    

Le plus dur est en effet de trouver la surface définie par ABCD.
 
Dans ton dessin tu pourrais par exemple relier différement tes points (par exemple en iversant C et D)
 
Donc question: lorsque tu as tes 4 points A, B, C et D, es-tu sûr qu'ils seront reliés AB, BC, CD et DA?
 
Dans ce cas tu peux avoir un sablier, un comme sur ton schéma ou un convexe (à moins que ce ne soit concave, je confonds toujours).
 
Sinon c bcp plus compliqué, car à 4 points peuvent correspondre plusieurs aires différentes...

Reply

Marsh Posté le 29-07-2002 à 16:12:31    

Voilà ou j'en suis, je vais faire les collisions maintenant (je c, c'est pas extrement beau, mais, je m'occupe des mouvements et des colisions en 1 er).
 
http://www.ifrance.com/yepslide/Project3D.zip

Reply

Marsh Posté le 29-07-2002 à 22:19:56    

En tavaillant dans le triangle ABD et en considerant G comme le point qui ne doit pas entrer en collision.
 
(Format d'une fonction lineaire :
Y=aX+b.)
 
Si on a 2 points sur un graphique, et que l'on veut trouvé la fonction lineaire, il faut procédé ainsi (arretez moi si je me trompe) :
 
*Pour trouver le coeficient directeur a :
a1=(Ax - Bx) / (Ay - By)
a2=(Ax - Dx) / (Ay -Dy)
a3=(Bx - Dx) / (By -Dy)
 
*Et pour b :
b1=Ay - Ax * (Ax-Bx) / (Ay-By)
b2=Ay - Ax * (Ax-Dx) / (Ay-Dy)
b3=Ay - Ax * (Bx-Dx) / (By-Dy)
 
*Ce qui donne :
Y1=(Ax - Bx) / (Ay - By) * X + Ay - Ax * (Ax-Bx) / (Ay-By)
Y2=(Ax - Dx) / (Ay -Dy) * X + Ay - Ax * (Ax-Dx) / (Ay-Dy)
Y3=(Bx - Dx) / (By -Dy) * X + Ay - Ax * (Bx-Dx) / (By-Dy)
 
Ensuite, une fois que j'ai les 3 equations de mon triangle, je procéde comme ceci non ?
 
Je determine si le point G a ses coordonnées qui appartient au triangle à l'aide des fonctions lineaire que j'ai calculé.
Pour cela, je procede ainsi :
 
Si Gy>Y1 et Gy<Y2 et Gy<Y3 alors il y a collision.
 
Je voudrais que vous verifiez ces calcules, si vous plait, car, il me semble y avoir une erreur que je n'arrive pas à trouvé, merci.
 
 
prettysmile, j'espere que tu va m'aides :p, hein pls :)

Reply

Marsh Posté le 29-07-2002 à 23:02:10    

prettysmile a écrit a écrit :

un triangle=3 équations du type ax+b<=y




 
prettysmile, faut que tu revises, l'equation generale c'est plutot  
ax + by <= c
qui peut etre reduite a ta forme lorsque b!=0
mais la on ne se soucie pas de ce cas particulier.
 
C'est dommage que ta surface ne soit pas convexe, si tu te limitais a des surfaces convexes, tu pourrais faire le test
d'appartenance sur chaque demi-plan delimité par les cotés de ta surface.
C'est d'ailleurs pour ca que les tests de collisions se font
plutot sur des formes convexes (convex hull, bsp etc..)
avec rafinement le cas echeant.
 
LeGreg
 

Reply

Marsh Posté le 30-07-2002 à 01:38:26    

legreg a écrit a écrit :

 
C'est dommage que ta surface ne soit pas convexe, si tu te limitais a des surfaces convexes, tu pourrais faire le test
d'appartenance sur chaque demi-plan delimité par les cotés de ta surface.
C'est d'ailleurs pour ca que les tests de collisions se font
plutot sur des formes convexes (convex hull, bsp etc..)
avec rafinement le cas echeant.




 
Heu, c'est quoi un convexe stp, :), vous en parlez, mais je n'ai pas idée sur ce que c'est... une explication rapide stp :p
Quelque ligne quoi :)

Reply

Marsh Posté le 30-07-2002 à 01:41:41    

raaah non, finalement ... [:google2]


Message édité par youdontcare le 30-07-2002 à 01:54:53
Reply

Marsh Posté le 30-07-2002 à 08:58:28    

legreg a écrit a écrit :

 
 
prettysmile, faut que tu revises, l'equation generale c'est plutot  
ax + by <= c
qui peut etre reduite a ta forme lorsque b!=0
mais la on ne se soucie pas de ce cas particulier.
 
C'est dommage que ta surface ne soit pas convexe, si tu te limitais a des surfaces convexes, tu pourrais faire le test
d'appartenance sur chaque demi-plan delimité par les cotés de ta surface.
C'est d'ailleurs pour ca que les tests de collisions se font
plutot sur des formes convexes (convex hull, bsp etc..)
avec rafinement le cas echeant.
 
LeGreg
 
 



vraiement dsl!!! shame on me, ben bonnet d'âne et j'y retourne
http://jupiter.rtsq.qc.ca/saqca/mathpri.htm

Reply

Marsh Posté le 30-07-2002 à 10:54:52    

convexe: en gros tu prends deux points de ton convexe (au hasard) et alors le segment qui les relie est forcément inclus dans ton convexe (pas comme sur ton dessin)
 
L'avantage des triangles c'est qu'ils sont forcément convexes.
 
PS: arrêtez-moi si je dis des bêtises :D


Message édité par PatBasi le 30-07-2002 à 10:55:56
Reply

Marsh Posté le 30-07-2002 à 13:09:29    

patbasi a écrit a écrit :

convexe: en gros tu prends deux points de ton convexe (au hasard) et alors le segment qui les relie est forcément inclus dans ton convexe (pas comme sur ton dessin)
 
L'avantage des triangles c'est qu'ils sont forcément convexes.
 
PS: arrêtez-moi si je dis des bêtises :D




 
Si on divise mon quadrilatére en plusieur triangle, on peut utilisé ta technique ? :)

Reply

Marsh Posté le 30-07-2002 à 13:16:22    

Voila, un petit resumé d'algos utilisés
pour calculer une enveloppe convexe
(convex hull)
 
http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
 
LeGreg

Reply

Marsh Posté le 30-07-2002 à 13:21:38    

il faut travailler avec les équations des plans définis par tes 4 points (sachant que 3 points seulement suffisent). Une fois que tu as trouvé l'équation de ton plan (le a, b, c de ton équation de la forme ax+by+c+d=0, d=1), tu remplaces les coordonnées de ton point E dans l'équation (x,y,z).
Pour calculer a, b et c, cherche un topic sur l'algorithme du Z-Buffer.

Reply

Marsh Posté le 30-07-2002 à 14:16:35    

C'est bon j'ai reussi ;), et vue que je suis sympas, je vais vous donnez le code, ca peut vous servire aussi un jour ;p
 
Si vous avez un conseil a me donner pour que le code soit plus rapide, n'hésitez pas :), donnez le.
 
 

Code :
  1. type TSpacePoint = packed record
  2.   X: Double;
  3.   Y: Double;
  4.   Z: Double;
  5. end;
  6. function TForm1.CollisionTriangulisation(Const X,Y:Double; var point1,point2,point3:TSpacePoint):boolean;
  7. var
  8.   CoeffA1,PtsOrigineB1,Ycomp1:Double;
  9.   CoeffA2,PtsOrigineB2,Ycomp2:Double;
  10.   CoeffA3,PtsOrigineB3,Ycomp3:Double;
  11.   pointT:TSpacePoint;
  12.   begin
  13.  
  14.   If ((point1.x<point2.x)) then
  15.   begin
  16.   pointT:=point1;
  17.   point1:=point2;
  18.   point2:=pointT;
  19.   end;
  20.  
  21.   //ax+b=y  
  22.   CoeffA1:=((point1.y-point2.y)/(point1.x-point2.x));
  23.   PtsOrigineB1:=(point2.y-((point1.y-point2.y)/(point1.x-point2.x))*point2.x);
  24.  
  25.   CoeffA2:=((point2.y-point3.y)/(point2.x-point3.x));
  26.   PtsOrigineB2:=(point3.y-((point2.y-point3.y)/(point2.x-point3.x))*point3.x);
  27.  
  28.   CoeffA3:=((point3.y-point1.y)/(point3.x-point1.x));
  29.   PtsOrigineB3:=(point1.y-((point3.y-point1.y)/(point3.x-point1.x))*point1.x);
  30.  
  31.   Ycomp1:=CoeffA1*X+PtsOrigineB1;
  32.   Ycomp2:=CoeffA2*X+PtsOrigineB2;
  33.   Ycomp3:=CoeffA3*X+PtsOrigineB3;
  34.  
  35.   result:=false;
  36.   //y en haut  
  37.   If ((point3.y>point1.y) and (point3.y>point2.y)) then begin
  38.   //  + milieu  
  39.   If ((point1.x>point3.X) and (point2.x<point3.x)) then
  40.   If ((Y>Ycomp1) and (Y<Ycomp2) and (Y<Ycomp3)) then
  41.   result:=true;
  42.  
  43.   // + droite  
  44.   If (point1.x<point3.X) then
  45.   If ((Y>Ycomp1) and (Y<Ycomp2) and (Y>Ycomp3)) then
  46.   result:=true;
  47.  
  48.   // + gauche  
  49.   If (point2.x>point3.X) then
  50.   If ((Y>Ycomp1) and (Y>Ycomp2) and (Y<Ycomp3)) then
  51.   result:=true;
  52.   end
  53.  
  54.   //y en bas  
  55.   else begin
  56.     //  - milieu  
  57.   If ((point1.x>point3.X) and (point2.x<point3.x)) then
  58.   If ((Y<Ycomp1) and (Y>Ycomp2) and (Y>Ycomp3)) then
  59.   result:=true;
  60.  
  61.   // - droite  
  62.   If (point1.x<point3.X) then
  63.   If ((Y<Ycomp1) and (Y>Ycomp2) and (Y<Ycomp3)) then
  64.   result:=true;
  65.  
  66.   // - gauche  
  67.   If (point2.x>point3.X) then
  68.   If ((Y<Ycomp1) and (Y<Ycomp2) and (Y>Ycomp3)) then
  69.   result:=true;
  70.  
  71.   end;
  72.  
  73.   end;


 
Tester :)
 
Edit : Modification dernier minute :)


Message édité par Slide le 30-07-2002 à 15:02:23
Reply

Marsh Posté le 30-07-2002 à 18:50:40    

Le code du dessus bug un peu, pas grand chose, je vien de le rectifié chez moi :), collision ok pour X et Y, maintenant, faut que je le fasse pour Z, si quelqu'un le veux, qui me contact par Email ;)

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed