Überschneiden zweier Rechtecke

[TheAn00bis]

Hey,

P1x und P1y bzw. P2x und P2y seien jeweils die Koordinaten der unteren linken Ecke, ich gehe von einem normalen Koordinatensystem aus, bei welchem unten links 0 ist und nach rechts und oben die Koordinaten größer werden.

Ich versuche jetzt seit einiger Zeit festzustellen, ob sich diese Rechtecke überschneiden, doch das will mir nicht gelingen. Es gibt dafür bereits die Windows Funktion RectIntersect, doch ich möchte nicht nur Ganzzahlen verwenden können, außerdem würde ich als Parameter lieber P1x, P1y, P2x, P2y, P1sizeX, P1sizeY, P2sizeX und P2sizeY übergeben, da mein gesamtes Programm bereits darauf ausgerichtet ist.

Alle Funktionen, die ich bis jetzt geschrieben haben funktionieren nicht und geben selbst bei zwei identischen Rechtecken "false" zurück:

Delphi-Quellcode:

function RectIntersectFloat(P1x, P1y, P1sizeX, P1sizeY, P2x, P2y, P2sizeX, P2sizeY: Extended):Boolean;
begin
  result := true;
  if (P1x >= P2x+P2sizeX) or
     (P1y+P1sizeY >= P2y) or
     (P2x >= P1x+P1sizeX) or
     (P2y+P2sizeY >=  P1y) then result:=false;
end;

Außerdem habe ich hier im Forum folgende Funktion vom ehemaligen Benutzer tommie-lie gefunden:

Delphi-Quellcode:

function RectIntersect(A, B: TRect; Offset: Integer): Boolean; 
begin 
  result := not((A.Right + Offset  <= B.Left)   or 
                (A.Bottom + Offset <= B.Top)    or 
                (A.Top - Offset    >= B.Bottom) or 
                (A.Left - Offset   >= B.Right)); 
end;

Diese habe ich einfach so umgewandelt, dass sie meinen Parametern entspricht und das Offset weggelassen (da ich dies nicht brauche), aber auch hier wird selbst bei zwei identischen Rechtecken "false" zurückgegeben:

Delphi-Quellcode:

function RectIntersectFloat(P1x, P1y, P1sizeX, P1sizeY, P2x, P2y, P2sizeX, P2sizeY: Extended):Boolean;
begin
  result := not((P1x + P1sizeX  <= P2x)   or
                (P1y <= P2y+P2sizeY)    or
                (P1Y + P1sizeY >= P2y) or
                (P1x  >= P2x+P2sizeX)); 
end;

Was mache ich falsch? Oder viel wichtiger: Wie wäre es richtig?
Daran, dass ich Mathematik-LK habe darf ich gerade gar nicht denken.

[DGL-luke]

Du könntest jetzt natürlcih deine werte mit einem beliebigen faktor multiplizieren und dann runden, um auf eine bestimmte genauigkeit zu kommen, und dann die windows-funktion benutzen. ansonsten hilft es oft, in Kanten zu denken und zu prüfen, ob diese sich schneiden. so ähnlich sagt das zumindest marabu immer

[Hawkeye219]

Hallo,

jetzt grabe ich mal einen Klassiker aus: klick

Das mußt du nur noch an dein Koordinatensystem anpassen.

Gruß Hawkeye

[TheAn00bis]

Das mit dem Multiplizieren wäre möglich, aber äußerst unschön, außerdem müsste ich dann immer erst TRects erstellen.

Diese Funktion liefert zumindest bei gleichen Rechtecken "true", aber ich glaube sonst nicht immer:

Delphi-Quellcode:

function RectIntersectFloat(P1x, P1y, P1sizeX, P1sizeY, P2x, P2y, P2sizeX, P2sizeY: Extended):Boolean;
begin
  result := true;
  if (P1x >= P2x+P2sizeX) or
     (P1y >= P2y+P2sizeY) or
     (P2x >= P1x+P1sizeX) or
     (P2y >= P1y+P2sizeY) then result:=false;
end;

Wobei sie nach meinen Überlegungen richtig sein müsste... ich schau mal.

_____

Cool, Hawkeye schau ich mir mal an!

Edit: Die Funktion tuts auch:

Delphi-Quellcode:

function RectIntersectFloat(P1x, P1y, P1sizeX, P1sizeY, P2x, P2y, P2sizeX, P2sizeY: Extended):Boolean;
begin
  result := true;
  if (P1x > P2x+P2sizeX) or
     (P1y > P2y+P2sizeY) or
     (P2x > P1x+P1sizeX) or
     (P2y > P1y+P2sizeY) then result:=false;
end;

Es sei denn ich habe irgendeinen speziellen Testfall übersehen! Wenn doch nicht melde ich mich nochmal! Danke!

[Sidorion]

zwei Rechtecke schneiden sich dann, wenn mindestens ein Punkt von A innerhalb B oder mindestens ein Punkt von B innerhalb A. Da diese Prüfungen suboptimal sind, empfehle ich volgense Vorgehensweise.
Du legst für Jeden Punkt in A ein Bitfeld(Länge 4 an).
Jetzt vergleichst Du mit jeder KANTE von B. liegt der Punkt links der linken kante, setzt Du Bit1 auf true, oberhalb der oberen Bit2 usw.
A schneidet nun B, wenn 1. mindestens ein Ergebnit =0x00h oder alle 4 Ergebnisse undverknüpft = 0x00h.

Jedenfalls kann man sowas nicht mit einer einfachen If-Konstruktion erschlagen.