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

Denken Sie nicht an Koordinaten, die angeben, wo sich die Pixel befinden. Betrachten Sie sie als zwischen den Pixeln liegend. Auf diese Weise sollte die Fläche eines 2x2-Rechtecks 4 und nicht 9 sein.

bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
               && (A.Bottom >= B.Top || B.Bottom >= A.Top));

Answer 2

Wenn sich die Rechtecke überschneiden, ist der Überlappungsbereich größer als Null. Lassen Sie uns nun die Überlappungsfläche ermitteln:

Wenn sie sich überschneiden, ist die linke Kante von overlap-rect die max(r1.x1, r2.x1) und der rechte Rand wird min(r1.x2, r2.x2) . Die Länge der Überlappung beträgt also min(r1.x2, r2.x2) - max(r1.x1, r2.x1)

So wird das Gebiet sein:

area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))

Si area = 0 dann überschneiden sie sich nicht.

Ganz einfach, oder?

Answer 3

Nehmen wir an, die beiden Rechtecke seien Rechteck A und Rechteck B. Ihre Mittelpunkte seien A1 und B1 (die Koordinaten von A1 und B1 lassen sich leicht herausfinden), die Höhen seien Ha und Hb, die Breiten seien Wa und Wb, dx sei der Abstand der Breite (x) zwischen A1 und B1 und dy der Abstand der Höhe (y) zwischen A1 und B1.

Jetzt können wir sagen, dass sich A und B überschneiden: wenn

if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true

Answer 4

Der einfachste Weg ist

/**
 * Check if two rectangles collide
 * x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
 * x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
 */
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
  return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}

Zunächst einmal sollten Sie sich vergegenwärtigen, dass das Koordinatensystem in Computern auf dem Kopf steht. Die x-Achse ist dieselbe wie in der Mathematik, aber die y-Achse steigt nach unten und fällt nach oben. wenn ein Rechteck von der Mitte aus gezeichnet wird. Wenn die Koordinaten von x1 größer sind als x2 plus die Hälfte der Breite, dann bedeutet das, dass sie sich berühren, wenn sie die Hälfte der Breite einnehmen, und auf die gleiche Weise, wenn sie nach unten + die Hälfte der Höhe einnehmen, stoßen sie zusammen.

Answer 5

Für diejenigen unter Ihnen, die Mittelpunkte und halbe Größen für ihre Rechteckdaten verwenden, anstelle der typischen x,y,w,h oder x0,y0,x1,x1, hier ist die Vorgehensweise:

#include <cmath> // for fabsf(float)

struct Rectangle
{
    float centerX, centerY, halfWidth, halfHeight;
};

bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
    return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
           (fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight)); 
}