Question (simple) de maths

kelebrindae · Message par **kelebrindae** » lun. 15/déc./2008 10:02

Bonjour à tous,

Voici une petite question, assez simple je pense, mais comme je n'ai pas assez dormi et que je suis une brèle d'ampleur cosmique en maths, je sèche un peu...

Comment déterminer rapidement qu'un segment de droite (orienté selon un angle quelconque) traverse un rectangle (lui aussi orienté selon un angle quelconque) ?

Je me suis dit que l'approche la plus simple consistait déterminer si au moins une des arêtes du rectangle croise le segment. La question est donc: Comment fait-on pour calculer si ces deux segments se croisent?

(oui, je sais, c'est des maths niveau collège; mais je manque vrai... vraiment... de som... meil.... ZZZZ ronfl...)

Anonyme · Message par **Anonyme** » lun. 15/déc./2008 11:03

T'es pas sorti de l'auberge

http://www.purebasic.fr/french/viewtopi ... E9parateur

GUELLIL · Message par **GUELLIL** » lun. 15/déc./2008 11:22

T'es pas sorti de l'auberge

Il ne faut pas le décourager. C'est facile.
C'est ce que je viens de faire massivement dans l'applique suivante (voir à partir de la deuxième page du fichier) que j'ai indiquée dans le fil de discussion sur le tracé des courbes.
http://tokei.ifrance.com/GenFly_Cutter.pdf*

Il faut néanmoins préciser ce qu'on entend par "traverser le rectangle": juste y pénétrer ou bien traverser de part en part.

@+

Anonyme · Message par **Anonyme** » lun. 15/déc./2008 11:48

Je suis dans le même bateau que lui avec les maths

GUELLIL , Super sympa ton document ! merci

tmyke · Message par **tmyke** » lun. 15/déc./2008 12:26

Question simple kelebrindae ? Pas si simple. On aborde ici les base des collisions et de leur
gestions. Mais bon, voici un petit code, pas trop compliqué au regard de la tache à effectuer:
La fonction IntersectPlane se charge de verifier donc une intersection possible
entre un plan (définis par 3 vecteurs) et une ligne (définit par une origine et une direction)
Si le résultat est 0, alors pas d'intersection. Sinon, on à la distance, à savoir que l'on
peut aussi récupérer les coordonnées de collision par les valeurs U/V dans la procedure...

Code : Tout sélectionner

#EPSILON = 0.0000001
;=================================================================================
;=========== QUELQUES  FONCTION DE BASES SUR LES VECTEURS 3D
;=================================================================================
Structure VECTOR3
  x.f
  y.f
  z.f
EndStructure

Macro VECTOR3_(dest,v1,v2,v3)
  dest\x = v1
  dest\y = v2
  dest\z = v3
EndMacro

Procedure AddVector3(*res.VECTOR3, *vec1.VECTOR3, *vec2.VECTOR3)
  *res\x = *vec1\x + *vec2\x
  *res\y = *vec1\y + *vec2\y
  *res\z = *vec1\z + *vec2\z
EndProcedure

Procedure SubVector3(*res.VECTOR3, *vec1.VECTOR3, *vec2.VECTOR3)
  *res\x = *vec1\x - *vec2\x
  *res\y = *vec1\y - *vec2\y
  *res\z = *vec1\z - *vec2\z
EndProcedure

Procedure CrossProduct(*res.VECTOR3, *vec1.VECTOR3, *vec2.VECTOR3)
  *res\x = (*vec1\y * *vec2\z) - (*vec1\z * *vec2\y)
  *res\y = (*vec1\z * *vec2\x) - (*vec1\x * *vec2\z)
  *res\z = (*vec1\x * *vec2\y) - (*vec1\y * *vec2\x)
EndProcedure

Procedure.f DotProduct(*vec1.VECTOR3, *vec2.VECTOR3)
  l.f = *vec1\x * *vec2\x + *vec1\y * *vec2\y + *vec1\z * *vec2\z
  ProcedureReturn l
EndProcedure

;=================================================================================
;========= DEFINITION D'UN PLAN ET FONCTION D'INTERSECTION
;=================================================================================
Structure PLAN
  p0.VECTOR3
  p1.VECTOR3
  p2.VECTOR3
EndStructure

Macro PLAN_(plan, pt0, pt1, pt2)
  VECTOR3_(plan\p0 , pt0\x, pt0\y, pt0\z)
  VECTOR3_(plan\p1 , pt1\x, pt1\y, pt1\z)
  VECTOR3_(plan\p2 , pt2\x, pt2\y, pt2\z)
EndMacro

Procedure.f IntersectPlane(*plan.PLAN, *orig.VECTOR3, *dir.VECTOR3)
   Protected tmpv1.VECTOR3, tmpv2.VECTOR3
   Protected pvec.VECTOR3, tvec.VECTOR3, qvec.VECTOR3

  SubVector3(@tmpv1, @*plan\p1, @*plan\p0)
  SubVector3(@tmpv2, @*plan\p2, @*plan\p0)
   
  CrossProduct(@pvec, *dir, @tmpv2)
  
  det.f = DotProduct(@tmpv1,@pvec)
  
  
  If( det>-#EPSILON And det<#EPSILON)
    ProcedureReturn 0 
  EndIf

 
  inv_det.f = 1.0/det
  
  SubVector3(@tvec, *orig, @*plan\p0)
  
  U.f = DotProduct(@tvec,@pvec) * inv_det

  
  If(U<0.0) Or (U>1.0)
    ProcedureReturn 0 
  EndIf
  
  
 CrossProduct(@qvec, @tvec, @tmpv1)
 V.f = DotProduct(*dir,@qvec) * inv_det
  If(V<0.0) Or ((U+V)>1.0)
    ProcedureReturn 0   
  EndIf
  
  ;Debug U
  ;Debug V
  
  T.f = DotProduct(@tmpv2,@qvec)  * inv_det
  
  ProcedureReturn  T
  
EndProcedure

;=================================================================================
;============= Test 
;=================================================================================
vec0.VECTOR3
vec1.VECTOR3
vec2.VECTOR3
origine.VECTOR3
direction.VECTOR3
myPlan.PLAN
; definition des points représentant le plan
VECTOR3_(vec0, 0,0,0)
VECTOR3_(vec1, 10.0,0,0)
VECTOR3_(vec2, 5.0,10.0,0)
; creation du plan
PLAN_(myPlan, vec0, vec1, vec2)
; définition de la ligne à tester
VECTOR3_(origine, 9.5, 0.5  ,5.0)
VECTOR3_(direction, 0, 0  ,-1.0)

; si 0 renvoyé, alors pas d'intersection
Debug "distance:"
Debug IntersectPlane(@myPlan, @origine, @direction)

GUELLIL · Message par **GUELLIL** » lun. 15/déc./2008 12:56

Kelebrindae,
Tu as posé une question simple:

La question est donc: Comment fait-on pour calculer si ces deux segments se croisent?

En nous t'avons tous apporté une réponse compliquée.
Pour savoir si deux segments se coupent et récupérer les coordonnées de l'intersection il faut:
1- Ecrire l'équation de la droite qui porte le premier segment (très simple, je pourrais de la donner). Il faut l'écrire sur un papier, pas dans le programme.
2- Ecrire l'équation de la droite qui porte le deuxième segment, la aussi sur un papier.
3- Trouver, toujours sur papier, les équations des coordonnées du point d'intersection en fonction des coordonnées des quatre points qui définissent les deux segments (dès que j'aurais un peu de temps je pourrai te les donner).

Ce sont seulement ces deux équations qu'il faut rentrer dans le programme. Cela fait trois fois rien comme travail. Le programme calcule donc simplement et directement les coordonnées du point d'intersection.
4- Ensuite il faut écrire un If Else Endif pour voir si l'abcisse du point d'intersection est comprise entre les abcisses des points qui définissent le premier segment, afin de vérifier si le point d'intersection appartient bien au segment. Si oui: on met une variable logique à 1.
5- On écrit un 2eme If Else Endif pour voir si l'abcisse du point d'intersection est comprise entre les abcisses des points qui définissent le deuxième segment. Si oui: on met une deuxième variable logique à 1.

Résultat: si les deux variables logiques sont à 1 il y a intersection des deux segments.

Si tu ne t'en sors pas je te donnerai les quelques lignes de code qui font cela.
@+

comtois · Message par **comtois** » lun. 15/déc./2008 13:48

pour l'intersection de deux segments j'avais fait ça
Et sur le forum anglais psychofanta avait proposé quelques codes intéressants, je ne sais plus pour quel type de collision, mais c'est toujours intéressant d'y jeter un oeil.

Je testerai la solution de Tmyke ce soir, ça me parait pas mal aussi.

Code : Tout sélectionner

;Comtois 16/02/05
;Détection collision d'un segment avec un autre segment

;-Initialisation
Global ScreenHeight.l,ScreenWidth.l
Declare Erreur(Message$)
If ExamineDesktops()
  ScreenWidth = DesktopWidth(0)
  ScreenHeight = DesktopHeight(0)
Else
  Erreur("Euh ?")
EndIf
If InitSprite() = 0 Or InitMouse() = 0 Or InitKeyboard()=0
  Erreur("Impossible d'initialiser DirectX 7 Ou plus")
ElseIf OpenWindow(0,0,0,ScreenWidth,ScreenHeight,"Collision",#PB_Window_BorderLess) = 0
  Erreur("Impossible de créer la fenêtre")
EndIf
;{/ouvre un écran
If OpenWindowedScreen( WindowID(0), 0, 0, ScreenWidth , ScreenHeight, 0, 0, 0 ) = 0
  Erreur("Impossible d'ouvrir l'écran ")
EndIf 

Structure Segment
  P1.point
  P2.point
EndStructure

Global Box1.Segment,Box2.Segment

Procedure Erreur(Message$)
  MessageRequester( "Erreur" , Message$ , 0 )
  End
EndProcedure
Procedure.l Signe(a.l)
  If a>0
    ProcedureReturn 1
  ElseIf a=0
    ProcedureReturn 0
  Else
    ProcedureReturn -1
  EndIf
EndProcedure
Procedure.l Min(a.l,b.l)
  If a<b
    ProcedureReturn a
  Else
    ProcedureReturn b
  EndIf
EndProcedure
Procedure.l Max(a.l,b.l)
  If a>b
    ProcedureReturn a
  Else
    ProcedureReturn b
  EndIf
EndProcedure
Procedure Encadrement(*S1.Segment,*S2.Segment)
  ;Box Segment1
  Box1\P1\x=Min(*S1\P1\x,*S1\P2\x)
  Box1\P1\y=Min(*S1\P1\y,*S1\P2\y)
  Box1\P2\x=Max(*S1\P1\x,*S1\P2\x)
  Box1\P2\y=Max(*S1\P1\y,*S1\P2\y) 
  ;Box Segment2
  Box2\P1\x=Min(*S2\P1\x,*S2\P2\x)
  Box2\P1\y=Min(*S2\P1\y,*S2\P2\y)
  Box2\P2\x=Max(*S2\P1\x,*S2\P2\x)
  Box2\P2\y=Max(*S2\P1\y,*S2\P2\y)
EndProcedure

Procedure CollisionSegmentSegment(*S1.Segment,*S2.Segment)
  ;Test Collision encadrement
  If Box1\P2\x >= Box2\P1\x And Box1\P1\x <= Box2\P2\x And Box1\P2\y >= Box2\P1\y And Box1\P1\y <= Box2\P2\y
    ;Test chevauchement segments
    R1.f=((*S2\P1\x-*S1\P1\x)*(*S1\P2\y-*S1\P1\y))-((*S2\P1\y-*S1\P1\y)*(*S1\P2\x-*S1\P1\x))
    R2.f=((*S2\P2\x-*S1\P1\x)*(*S1\P2\y-*S1\P1\y))-((*S2\P2\y-*S1\P1\y)*(*S1\P2\x-*S1\P1\x))
    R3.f=((*S1\P1\x-*S2\P1\x)*(*S2\P2\y-*S2\P1\y))-((*S1\P1\y-*S2\P1\y)*(*S2\P2\x-*S2\P1\x))
    R4.f=((*S1\P2\x-*S2\P1\x)*(*S2\P2\y-*S2\P1\y))-((*S1\P2\y-*S2\P1\y)*(*S2\P2\x-*S2\P1\x))
    If (Signe(R1)*Signe(R2)<=0) And (Signe(R3)*Signe(R4)<=0)
      Resultat = #True
    EndIf
  EndIf 
  ProcedureReturn Resultat
EndProcedure

Procedure AffPoints(*S1.Segment,*S2.Segment,*P.point,mem)
  CouleurBox=RGB(70,70,70)
  CouleurSegment1=RGB(255,0,0)
  CouleurSegment2=RGB(0,255,0)
  CouleurCurseur=RGB(255,255,255)
  StartDrawing(ScreenOutput())
  ;/Affiche les encadrements des segments en premier pour ne pas effacer le tracé d'un segment
  ;Segment1
  LineXY(Box1\P1\x,Box1\P1\y,Box1\P1\x,Box1\P2\y,CouleurBox)
  LineXY(Box1\P1\x,Box1\P1\y,Box1\P2\x,Box1\P1\y,CouleurBox)
  LineXY(Box1\P2\x,Box1\P1\y,Box1\P2\x,Box1\P2\y,CouleurBox)
  LineXY(Box1\P1\x,Box1\P2\y,Box1\P2\x,Box1\P2\y,CouleurBox)
  ;Segment2
  LineXY(Box2\P1\x,Box2\P1\y,Box2\P1\x,Box2\P2\y,CouleurBox)
  LineXY(Box2\P1\x,Box2\P1\y,Box2\P2\x,Box2\P1\y,CouleurBox)
  LineXY(Box2\P2\x,Box2\P1\y,Box2\P2\x,Box2\P2\y,CouleurBox)
  LineXY(Box2\P1\x,Box2\P2\y,Box2\P2\x,Box2\P2\y,CouleurBox)
  ;/Affiche le Segment1
  Circle(*S1\P1\x,*S1\P1\y,4,CouleurSegment1)
  Circle(*S1\P2\x,*S1\P2\y,4,CouleurSegment1)
  LineXY(*S1\P1\x,*S1\P1\y,*S1\P2\x,*S1\P2\y,CouleurSegment1)
  ;/Affiche le Segment2
  Circle(*S2\P1\x,*S2\P1\y,4,CouleurSegment2)
  Circle(*S2\P2\x,*S2\P2\y,4,CouleurSegment2)
  LineXY(*S2\P1\x,*S2\P1\y,*S2\P2\x,*S2\P2\y,CouleurSegment2)
  ;/Affiche le point
  If mem
    DrawingMode(4)
    Circle(*P\x,*P\y,6,CouleurCurseur)
  Else
    DrawingMode(0)
    Circle(*P\x,*P\y,4,CouleurCurseur)
  EndIf
  ;/Affiche une croix pour mieux suivre le déplacement du point
  LineXY(*P\x,0,*P\x,ScreenHeight-1,CouleurCurseur)
  LineXY(0,*P\y,ScreenWidth-1,*P\y,CouleurCurseur)
  If CollisionSegmentSegment(*S1,*S2)
    FrontColor(RGB(255,255,0))
    BackColor(RGB(255,0,0))
    texte$="  IN "
  Else
    FrontColor(RGB(255,255,255))
    BackColor(RGB(0,255,0))
    texte$=" OUT "
  EndIf
  DrawText(0,0,texte$)
  StopDrawing()
EndProcedure
Procedure TestPoint(X1,Y1,X2,Y2,d)
  If X1>X2-d And X1<X2+d And Y1>Y2-d And Y1<Y2+d
    Resultat=#True
  EndIf
  ProcedureReturn Resultat
EndProcedure

Segment1.Segment
Segment2.Segment
Point.point
;Segment1
Segment1\P1\x=50
Segment1\P1\y=50
Segment1\P2\x=110
Segment1\P2\y=250
;Segment2
Segment2\P1\x=210
Segment2\P1\y=250
Segment2\P2\x=410
Segment2\P2\y=350
;Point à tester
Point\x=340
Point\y=100
DiametreSelection=6

Repeat
  While WindowEvent():Wend
  ClearScreen(0)
  ExamineKeyboard()
  ExamineMouse()
  ;Le triangle est modifiable à la souris en cliquant sur un point
  If MouseButton(1)
    If MemPoint=1
      Segment1\P1\x=MouseX()
      Segment1\P1\y=MouseY()
    ElseIf MemPoint=2
      Segment1\P2\x=MouseX()
      Segment1\P2\y=MouseY()
    ElseIf MemPoint=3
      Segment2\P1\x=MouseX()
      Segment2\P1\y=MouseY()
    ElseIf MemPoint=4
      Segment2\P2\x=MouseX()
      Segment2\P2\y=MouseY() 
    EndIf
  Else
    MemPoint=0
  EndIf
  If TestPoint(MouseX(),MouseY(),Segment1\P1\x,Segment1\P1\y,DiametreSelection)
    MemPoint=1
  ElseIf TestPoint(MouseX(),MouseY(),Segment1\P2\x,Segment1\P2\y,DiametreSelection)
    MemPoint=2
  ElseIf TestPoint(MouseX(),MouseY(),Segment2\P1\x,Segment2\P1\y,DiametreSelection)
    MemPoint=3
  ElseIf TestPoint(MouseX(),MouseY(),Segment2\P2\x,Segment2\P2\y,DiametreSelection)
    MemPoint=4 
  EndIf
  ;Place le point à tester sous la souris
  Point\x=MouseX()
  Point\y=MouseY()
  ;Affiche le tout
  Encadrement(@Segment1,@Segment2)
  AffPoints(@Segment1,@Segment2,@Point,MemPoint)
  FlipBuffers()
  Delay(1)
Until KeyboardPushed(#PB_Key_Escape)

kelebrindae · Message par **kelebrindae** » lun. 15/déc./2008 13:59

Merci pour toutes ces réponses!

Oui, effectivement, il y a eu des réponses compliquées, mais parce que vous avez fait une déduction exacte: le but est bien de détecter une collision entre deux objets.
Mais le contexte est tel que l'on peut simplifier le problème: Il s'agit de détecter qu'une voiture (ou plutôt sa bounding-box) passe à travers d'un plan vertical symbolisant un checkpoint.
=> si la voiture et le checkpoint sont à la même hauteur, ça peut se réduire à une vue de dessus et à la recherche d'une intersection entre un rectangle (la voiture) et un segment de droite (la ligne de checkpoint).

Quoi qu'il en soit, merci à vous pour ces infos, qui vont de toutes façons me servir tôt ou tard (quand je devrais faire de la "vraie" collision; Tmyke et Comtois, je vais garder vos codes précieusement...).

Pour ma part, j'ai trouvé ce petit algo qui se rapproche de ta suggestion, Guellil, et qui a l'air de fonctionner:

Code : Tout sélectionner

; Note: je ne retourne que vrai ou faux, je n'ai pour l'instant pas besoin des coordonnées de l'intersection.
; Soit 2 segment x1,y1 - x2,y2 et x3,y3 - x4,y4
Procedure.b ComputeSegmentIntersection(x1.f,y1.f,x2.f,y2.f,x3.f,y3.f,x4.f,y4.f)

  Protected d.f
  Protected xi.f,yi.f       ; coordonnées du point d'intersection
  Protected xmin.f,xmax.f 

  d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
  If d=0
    ProcedureReturn #False
  EndIf 
  
  ; Calcul du point d'intersection des lignes
  xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d
  yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d
  
  ; Ce point est-il à l'intérieur des segments ?
  ; segment 1
  If x1 > x2
    xmax = x1
    xmin = x2
  Else
    xmax = x2
    xmin = x1
  EndIf 
  If xi < xmin Or xi > xmax
    ProcedureReturn #False
  EndIf
  
  ; Segment 2
  If x3 > x4
    xmax = x3
    xmin = x4
  Else
    xmax = x4
    xmin = x3
  EndIf 
  If xi < xmin Or xi > xmax
    ProcedureReturn #False
  EndIf
  
  ; Note: Ne faudrait-il pas ajouter le même test sur l'axe Y?
  
  ProcedureReturn #True

EndProcedure

Ce n'est pas forcément la méthode la plus rapide, remarquez bien (mais ça me paraît pas mal...)
Question subsidiaire, pour mon enrichissement personnel: ce calcul dont le résultat est placé dans la variable "d", c'est un "dot product" ?