Überprüfung, ob sich Rechtecke schneiden

[Nikolas]

Hallo

Ich bin gerade auf der Suche nach einer schnellen Lösung für folgendes Problem:

Ich habe ein ruhendes Rechteck, dessen Kanten parallel zu den Achsen liegen. Ein anderes Rechteck liegt irgendwie gedreht im Raum. Die Frage ist jetzt, ob sie sich beühren.

Eine Möglichkeit wäre natürlich alle Kanten des einen mit allen Kanten des anderen zu schneiden und auf schnittpunkt im richtigen Bereich zu testen. Nur ist das etwas aufwändig. Später soll das ganze in einem Spiel laufen, von da her Suche ich besonders nach einer perfomanten Lösung. Weiss da jemand etwas schnelleres?

Nikolas

[Robert Marquardt]

Game mit OpenGL bzw. DirectX? Wenn ja dann sollte es da passende Funktionen geben. Vierecke sind zwei aneinanderliegende Dreiecke. Dafuer gibt es bestimmt Schnitttestfunktionen.

[Nikolas]

Nein, Game mit C++ :)

Alles reine Handarbeit :mrgreen:

[DGL-luke]

Hallo,

projiziere die Rechtecke zuerst auf eine 2-dimensionale ebene (z.B. indem du sie "von oben" ansiehst, du kannst dann einfach die z-koords untern tisch fallen lassen).

Benutze dann IntersectRect. Wenn du damit keine Kollision erkennst, gibts auch keine. Wenn doch, musst du das ganze nochmal 3-dimensional prüfen, bzw. prüfen, ob es in einer der anderen ebenen (yz und xz) auch kollisionen gibt (bei einem rechteck mit höhe = 1 bzw. 0 kannst du dann davon ausgehen, dass eine kollision genau dann stattfindet, wenn du in allen drei ebenen eine erkennst, glaube ich... :gruebel: )

[shmia]

Zitat:

Zitat von DGL-luke

Benutze dann IntersectRect.

Hier werden aber Rechtecke erwartet, die rechtwinklig zum Koordinatensystem liegen. Zumindest ein Rechteck tut dies nicht.

@Nikolas oder Admin: bitte Thema ändern nach: Überprüfung, ob Quader sich schneiden.

[DGL-luke]

...trotzdem funktioniert mein ansatz. und ich denke, Nikolas spricht von Rechtecken.

[shmia]

Zitat:

Zitat von DGL-luke

und ich denke, Nikolas spricht von Rechtecken.

> Ein anderes Rechteck liegt irgendwie gedreht im Raum
"Gedreht im Raum" deutet für mich auf 3 Dimensionen hin. Er soll sich halt erklären, ob es 2 oder 3 Dimensionen sind.

[OregonGhost]

Zitat:

Später soll das ganze in einem Spiel laufen, von da her Suche ich besonders nach einer perfomanten Lösung.

Wenn es um Performance geht, kannst du auch einfach 99% aller Fälle abfangen, indem du zunächst prüfst, ob sich die Bounding Boxes (die parallel zu den Achsen ausgerichtet sind) überschneiden, und nur in dem Fall eine genaue Prüfung vornimmst (alternativ auch Bounding Circles, das könnte bei gedrehten Rechtecken sogar besser sein). Denk daran, dass es bei dem Gedanken der Performance-Optimierung nicht unbedingt immer darum geht, einen zeitaufwändigen Vorgang etwas schneller zu machen, sondern häufiger, ihn von vornherein zu vermeiden.

[DGL-luke]

auch ein rechteck kann im raum liegen, auch "gedreht"...

[Nikolas]

Es geht um den 2-Dimensionalen Raum, in dem sich mein Spiel bewegt. Entschuldigt bitte die Ungenauigkeit. (Wobei: Wer hat schon mal in einem Spiel Rechtecke in einem 3D-Raum gesehen, die geschnitten werden müssen? Klingt etwas nach Autoscooter mit fliegenden Teppichen :) )

Das mit dem Boundingcircle hört sich gut an. Als Vorprüfung werde ich das einführen. Eine schnelle Lösung dahinter wär aber auch gut

[jfheins]

Du kannst das Problem vereinfachen: Prüfe für jeden der 8 Punkte, ob er sich im jeweils anderen Rechteck befindet. Falls das bei einem der Fall ist, schneiden sie sich. Falls das bei allen nicht der fall ist, schneiden sie sich nicht. (gibt es nicht sogar ein PtInRect Funktion?)
Ob das die performateste Lösung ist, weis ich jetzt nicht, aber nach den bounding circles dürften ja eh nicht mehr soviele berechnungen gemacht werden ;)

[DGL-luke]

oh, damit stellt sich das Problem natürlich ganz anders dar. Mit in der HInsicht gedrehten Sachen hatte ich nicht gerechnet.

[Nikolas]

Zitat:

Du kannst das Problem vereinfachen: Prüfe für jeden der 8 Punkte, ob er sich im jeweils anderen Rechteck befindet. Falls das bei einem der Fall ist, schneiden sie sich. Falls das bei allen nicht der fall ist, schneiden sie sich nicht.

Leider auch nicht. Leg mal ein langes Lineal auf ein Blatt Papier, so dass keine Ecke des Papiers bedeckt ist.

Zitat:

Mit in der HInsicht gedrehten Sachen hatte ich nicht gerechnet.

Alles andere ist trivial, da hätte ich kein Problem..

[Hawkeye219]

Hallo Nikolas,

wenn du keine rein mathematische Lösung mehr findest, kannst du auch auf die Regionen-Befehle der WinAPI ausweichen:

Delphi-Quellcode:

function RectPolygonIntersect (const R: TRect;  const P: array of TPoint): Boolean;
var
  RectRgn : HRGN;
  PolyRgn : HRGN;
begin
  RectRgn := CreateRectRgnIndirect(R);
  PolyRgn := CreatePolygonRgn(P[0], Length(P), WINDING);
  Result := (CombineRgn(RectRgn, RectRgn, PolyRgn, RGN_AND) <> NULLREGION);
  DeleteObject(PolyRgn);
  DeleteObject(RectRgn);
end;

Sollte sich diese Lösung als zu langsam erweisen, hilft vielleicht ein vorgeschalteter BoundingBox-Test, so wie es bereits in den vorigen Beiträgen vorgeschlagen wurde.

Gruß Hawkeye

[Clobber the mob]

Delphi-Quellcode:

procedure blub (...);
var
  Overlay: TRect;

begin
if IntersectRect (Overlay, Rect1.BoundsRect, Rect2.BoundsRect) then
  begin
   .
   . 
   .
  end;
end;

Wär das ne Möglichkeit=?

[Nikolas]

Ich hab heute keinen Windowsrechner, von da her kann ich zu dem Intersect Rect nichts sagen. Könnte vielleicht jemand den Quellcode oder wenigstens den HilfeEintrag hier posten.
// Ich hab die Hilfe gefunden. Die Funktion erwartet Rechtecke, deren Achsen parallel zu den Koordinatenachsen sind. Deswegen hilft mir die Funktion überhaupt nicht.


Als kleine Fiesigkeit der Tutoren darf ich mein geliebtes Pascal nicht einsetzen, sondern muss C++ schreiben, so dass ich die Funktion umschreiben müsste.

[Nikolas]

Hier mal meine Lösung:

Mit dem Drehwinkel des zweiten Rechtecks kann ich die unterste Ecke bestimmen (oder auch die untersten Ecken im Fall von z.B. winkel=0)
Wenn dann z.B. die y-Komponente der Geschwindigkeit kleiner als Null ist, schneide ich die Halbgerade, die entsteht, wenn ich den Richtungsvektor an die unterste Ecke hänge, mit der oberen Kante meines stehenden Rechtecks.

Wenn aber die y-Komponente positiv ist, schneide ich die übernachste Ecke nach der untersten mit der unteren Seite des stehenden Rechtecks.

Egal wie zweite Rechteck gedreht ist, schneide ich maximal 4 halbgeraden. (z.B. dann wenn das Rechteck nicht gedreht ist und von oben links auf das stehende prallt. Dann kann die untere linke und rechts ecke mit der oberen kante zusammenstoßen, aber auch die rechte obere und untere mit der linken Seite des Rechtecks.

Insgesamt also nicht allzu viel Aufwand.