Überprüfung, ob sich Rechtecke schneiden

[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.