Wie prüft man die Kollision von gedrehten Rechtecken?

[mpz]

Hallo Leute,

ich versuche gerade eine sinnvollen Algorythmus zu finden um die Kollision von gedrehten Rechtecken (nur 2D) zu überprüfen.

Bekannt sind die Eckpunkte und er Winkel der gedrehten Rechtecke. Kennt jemand eine Lösung oder einen fertigen Code (die Sprache ist egal)? Meine Idee ist derzeit die vier Eckpunkte zu nehmen und dann zu überprüfen ob diese in dem anderem Rechteck liegen. Durch den Winkel wird das aber etwas erschwert und meine derzeitige Kollision macht was sie will, nur nicht was Sie soll...

Gruß Michael

[STARGÅTE]

es ist nicht sonderlich schnell, aber das einfachste wäre n LineLine Kollision zu testen, das wären dann 16 Tests ...

hägt halt davon ab was du brauchst ... das mit den Punkt um Rechteck geht nicht, weil die rechtecke ja genau so blöd übereinander liegen können, das alle Punkt außerhalb des anderen Rechtecks liegen (beispiel zwei Quadrate um 45° gedreht)

den Test ob zwei Linein mit endlicher ausdehnung sich schneiden findest du hier sicher im Forum ...

Das hier könnte vllt auch helfen, geht ab Seite 23 richtig los ...
Kollisionserkennung

[TomS]

Unter zu Hilfenahme dieses Codes zum berechnen des Schnittpunkts zweier Linien habe ich mal ein kleines Beispiel zusammen geschustert.

Code: Alles auswählen

InitSprite()
InitKeyboard()
OpenWindow(0,0,0,600,600,"",#PB_Window_ScreenCentered|#PB_Window_SystemMenu)
OpenWindowedScreen(WindowID(0),0,0,600,600,0,0,0)

winkel.l	=0

Global spx.w
Global spy.w

Procedure GetSP(p1x,p1y,p2x,p2y,q1x,q1y,q2x,q2y)
a1=p2y-p1y
a2=q2y-q1y
b1=p1x-p2x
b2=q1x-q2x
c1=a1*p1x+b1*p1y
c2=a2*q1x+b2*q1y

bx=(a1*b2-a2*b1)
by=(a1*b2-a2*b1)
If Abs(bx)>0 And Abs(by)>0
 spx=(c1*b2-c2*b1)/bx
 spy=(a1*c2-a2*c1)/by
EndIf 
result=1
If (spy>p1y) And (spy>p2y):result=0:EndIf
If (spy>q1y) And (spy>q2y):result=0:EndIf
If (spy<p1y) And (spy<p2y):result=0:EndIf
If (spy<q1y) And (spy<q2y):result=0:EndIf
If (spx>p1x) And (spx>p2x):result=0:EndIf
If (spx>q1x) And (spx>q2x):result=0:EndIf
If (spx<p1x) And (spx<p2x):result=0:EndIf
If (spx<q1x) And (spx<q2x):result=0:EndIf
ProcedureReturn result
EndProcedure


Repeat
event=WindowEvent()
ExamineKeyboard()
ClearScreen(0)

If event=#PB_Event_CloseWindow
	End 
EndIf 
Delay(10)

winkelfloat.f=winkel/180*#PI
a=-100*Cos(winkelfloat)
b=-100*Sin(winkelfloat)

c=100*Sin(winkelfloat)
d=-100*Cos(winkelfloat)

e=100*Cos(winkelfloat)
f=100*Sin(winkelfloat)

g=-100*Sin(winkelfloat)
h=100*Cos(winkelfloat)

StartDrawing(ScreenOutput())
	FrontColor(RGB(255,255,0))
	BackColor(0)
	DrawText(10,10,"Winkel: "+Str(winkel),RGB(255,255,0))
	
	
If GetSP(200+a,200+b,200+c,200+d,290,100,290,300) Or GetSP(200+c,200+d,200+e,200+f,290,100,290,300) Or GetSP(200+e,200+f,200+g,200+h,290,100,290,300) Or GetSP(200+g,200+h,200+a,200+b,290,100,290,300)
	FrontColor(RGB(255,0,0))	
	DrawText(100,10,"KOLLISION")
Else
	FrontColor(RGB(255,255,0))	
EndIf 

	
	LineXY(200+a,200+b,200+c,200+d)
	LineXY(200+c,200+d,200+e,200+f)
	LineXY(200+e,200+f,200+g,200+h)
	LineXY(200+g,200+h,200+a,200+b)	
	
	
	LineXY(290,100,290,300)	;Angedeutets Rechteck zur Kollionsüberprüfung
	
StopDrawing()



If KeyboardPushed(#PB_Key_Up)
	winkel+1
	Delay(20)
ElseIf KeyboardPushed(#PB_Key_Down)
	winkel-1
	Delay(20)
EndIf 


FlipBuffers()
ForEver 

[mpz]

Hi TomS,

Danke für Dein Beipiel, das ist schon ein guter Ansatz...

Gruß Michael

[Kaeru Gaman]

vorher würde ich dann den BoudingCircle berechnen und den checken.
http://www.purebasic.fr/german/viewtopic.php?t=9093

das geht schneller, der ist auch immer gleich relativ zum Mittelpunkt des rechteckt, egal wie es gedreht wird.
erst wenn die beiden BoundingCircles überlappen, braucht man mehr Aufwand treiben.

[mpz]

Danke Kaeru,

das zu integrieren habe ich auch schon überlegt. Hat aber bei grossen Objekten (in diesem Fall Screenbreit um ein Scrollfeldbergrenzung darzustellen) weniger Sinn. Meine Ziel ist erst eine Rechtechprüfung durchzuführen und danach eine Pixelüberprüfung. Meine Routine für Nicht gedrehte Objekte funktioniert schon super.

Gruß Michael

[Kaeru Gaman]

oh.. verstehe
dann ist aber die Rechteckprüfung ein Overkill, wenn du danach sowieso noch eine pixelprüfung durchführen willst.
ich wurde dann gleich nur die BoundedCircle als Vorabprüfung benutzen, eben weil das gedrehte rechteck so viel aufwendiger ist.

[mpz]

Hi,
Nun bei grossen Objekten sagt die Kreis/Kreis Kollision eh das sich die Objekte treffen und müssen dann weiter geprüft werden. Ich werde aber mal ein FPS Messung machen ob der Kreis/Kreis abgleich in diesem speziellen Fall was bringt:

Gruß Michael