Bestimmen Sie, ob sich zwei Rechtecke überschneiden?

Question

Ich versuche, ein C++-Programm zu schreiben, das die folgenden Eingaben des Benutzers annimmt, um Rechtecke (zwischen 2 und 5) zu konstruieren: Höhe, Breite, x-pos, y-pos. Alle diese Rechtecke liegen parallel zur x- und y-Achse, d.h. alle ihre Kanten haben eine Steigung von 0 oder unendlich.

Ich habe versucht zu implementieren, was in ce Frage, aber ich habe nicht sehr viel Glück.

Meine derzeitige Implementierung funktioniert folgendermaßen:

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;  

Allerdings bin ich mir nicht ganz sicher, ob (a) ich den Algorithmus, auf den ich verlinkt habe, richtig implementiert habe, oder ob ich genau weiß, wie er zu interpretieren ist?

Irgendwelche Vorschläge?

Answer 1

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

oder, bei Verwendung kartesischer Koordinaten

(X1 ist die linke Koordinate, X2 ist die rechte Koordinate, aufsteigend von links nach rechts wobei Y1 die obere Koordinate und Y2 die untere Koordinate ist, von unten nach oben ansteigend -- wenn Ihr Koordinatensystem nicht auf diese Weise funktioniert [z. B. haben die meisten Computer die Y-Richtung umgekehrt], tauschen Sie die folgenden Vergleiche aus ) ...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

Angenommen, Sie haben Rechteck A und Rechteck B. Der Beweis erfolgt durch Widerspruch. Jede der vier Bedingungen garantiert, dass keine Überschneidungen bestehen können :

• Kond1. Wenn die linke Kante von A rechts von der rechten Kante von B liegt, - dann ist A völlig rechts von B
• Kond2. Wenn die rechte Kante von A links von der linken Kante von B liegt, - dann ist A völlig links von B
• Kond3. Wenn die Oberkante von A unterhalb der Unterkante von B liegt, - dann ist A vollständig unter B
• Kond4. Wenn die untere Kante von A über der oberen Kante von B liegt, - dann liegt A vollständig über B

Die Bedingung für die Nicht-Überschneidung ist also

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

Eine hinreichende Bedingung für die Überschneidung ist daher das Gegenteil.

Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

Das De-Morgan'sche Gesetz besagt
Not (A or B or C or D) ist dasselbe wie Not A And Not B And Not C And Not D
Mit Hilfe von De Morgan ergibt sich also

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

Dies ist gleichbedeutend mit:

• Die linke Kante von A liegt links von der rechten Kante von B, [ RectA.Left < RectB.Right ], und
• Die rechte Kante von A liegt rechts von der linken Kante von B, [ RectA.Right > RectB.Left ], und
• A's oben über B's unten, [ RectA.Top > RectB.Bottom ], und
• A's Unterseite unter B's Oberseite [ RectA.Bottom < RectB.Top ]

Anmerkung 1 : Es ist ziemlich offensichtlich, dass dieses Prinzip auf eine beliebige Anzahl von Dimensionen ausgedehnt werden kann.
Anmerkung 2 : Es sollte auch ziemlich offensichtlich sein, dass man Überlappungen von nur einem Pixel zählen kann, indem man die < und/oder die > an dieser Grenze zu einem <= oder eine >= .
Anmerkung 3 : Diese Antwort basiert bei Verwendung kartesischer Koordinaten (X, Y) auf algebraischen kartesischen Standardkoordinaten (x steigt von links nach rechts und Y steigt von unten nach oben). Wenn ein Computersystem die Bildschirmkoordinaten anders mechanisiert (z. B. Y von oben nach unten oder X von rechts nach links), muss die Syntax natürlich entsprechend angepasst werden.

Answer 2

struct rect
{
    int x;
    int y;
    int width;
    int height;
};

bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }

bool rectOverlap(rect A, rect B)
{
    bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
                    valueInRange(B.x, A.x, A.x + A.width);

    bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
                    valueInRange(B.y, A.y, A.y + A.height);

    return xOverlap && yOverlap;
}

Answer 3

struct Rect
{
    Rect(int x1, int x2, int y1, int y2)
    : x1(x1), x2(x2), y1(y1), y2(y2)
    {
        assert(x1 < x2);
        assert(y1 < y2);
    }

    int x1, x2, y1, y2;
};

bool
overlap(const Rect &r1, const Rect &r2)
{
    // The rectangles don't overlap if
    // one rectangle's minimum in some dimension 
    // is greater than the other's maximum in
    // that dimension.

    bool noOverlap = r1.x1 > r2.x2 ||
                     r2.x1 > r1.x2 ||
                     r1.y1 > r2.y2 ||
                     r2.y1 > r1.y2;

    return !noOverlap;
}

Answer 4

Es ist einfacher zu prüfen, ob ein Rechteck vollständig außerhalb des anderen liegt, wenn es also entweder

auf der linken Seite...

(r1.x + r1.width < r2.x)

oder auf der rechten Seite...

(r1.x > r2.x + r2.width)

oder obendrauf...

(r1.y + r1.height < r2.y)

oder auf der Unterseite...

(r1.y > r2.y + r2.height)

des zweiten Rechtecks, kann es unmöglich mit diesem kollidieren. Um also eine Funktion zu haben, die eine boolesche Aussage darüber macht, ob die Rechtecke kollidieren, kombinieren wir einfach die Bedingungen durch logische ODERs und negieren das Ergebnis:

function checkOverlap(r1, r2) : Boolean
{ 
    return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}

Um bereits bei einer reinen Berührung ein positives Ergebnis zu erhalten, können wir die "<" und ">" durch "<=" und ">=" ersetzen.

Answer 5

Dies ist eine sehr schnelle Möglichkeit, mit C++ zu prüfen, ob sich zwei Rechtecke überschneiden:

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
    && std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

Dazu werden der linke und der rechte Rand des sich schneidenden Rechtecks berechnet und dann verglichen: Ist der rechte Rand gleich oder kleiner als der linke, bedeutet dies, dass der Schnittpunkt leer ist und sich die Rechtecke daher nicht überschneiden; andernfalls wird der Versuch mit dem oberen und unteren Rand wiederholt.

Was ist der Vorteil dieser Methode gegenüber der herkömmlichen Alternative mit 4 Vergleichen? Es geht darum, wie moderne Prozessoren konstruiert sind. Sie verfügen über eine so genannte Verzweigungsvorhersage, die gut funktioniert, wenn das Ergebnis eines Vergleichs immer dasselbe ist, ansonsten aber einen enormen Leistungsverlust mit sich bringt. Wenn es jedoch keine Verzweigungsbefehle gibt, arbeitet die CPU recht gut. Indem wir die Grenzen des Schnittpunkts berechnen, anstatt zwei separate Prüfungen für jede Achse durchzuführen, sparen wir zwei Verzweigungen, eine pro Paar.

Es ist möglich, dass die Vier-Vergleiche-Methode diese Methode übertrifft, wenn der erste Vergleich mit hoher Wahrscheinlichkeit falsch ist. Das ist allerdings sehr selten, denn das bedeutet, dass sich das zweite Rechteck meistens links vom ersten Rechteck befindet und nicht rechts oder überlappend; und meistens muss man Rechtecke auf beiden Seiten des ersten überprüfen, was normalerweise die Vorteile der Zweigvorhersage zunichte macht.

Diese Methode kann je nach der erwarteten Verteilung der Rechtecke noch weiter verbessert werden:

• Wenn Sie erwarten, dass die angekreuzten Rechtecke überwiegend links oder rechts voneinander liegen, funktioniert die obige Methode am besten. Dies ist z. B. der Fall, wenn Sie den Rechteckschnittpunkt zur Kollisionsprüfung für ein Spiel verwenden, bei dem die Spielobjekte überwiegend horizontal verteilt sind (z. B. ein SuperMarioBros-ähnliches Spiel).

• Wenn Sie davon ausgehen, dass die geprüften Rechtecke überwiegend oben oder unten liegen, z. B. in einem Spiel wie "Icy Tower", dann ist die Prüfung oben/unten zuerst und links/rechts zuletzt wahrscheinlich schneller:

  return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom) && std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);

• Wenn die Wahrscheinlichkeit, dass sich die Wege kreuzen, nahe an der Wahrscheinlichkeit liegt, dass sie sich nicht kreuzen, ist es jedoch besser, eine völlig verzweigungslose Alternative zu haben:

  return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right) & std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

(Beachten Sie die Änderung der && zu einer einzigen & )