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

Angenommen, Sie haben die Positionen und Größen der Rechtecke wie folgt festgelegt:

Meine C++-Implementierung sieht folgendermaßen aus:

class Vector2D
{
    public:
        Vector2D(int x, int y) : x(x), y(y) {}
        ~Vector2D(){}
        int x, y;
};

bool DoRectanglesOverlap(   const Vector2D & Pos1,
                            const Vector2D & Size1,
                            const Vector2D & Pos2,
                            const Vector2D & Size2)
{
    if ((Pos1.x < Pos2.x + Size2.x) &&
        (Pos1.y < Pos2.y + Size2.y) &&
        (Pos2.x < Pos1.x + Size1.x) &&
        (Pos2.y < Pos1.y + Size1.y))
    {
        return true;
    }
    return false;
}

Ein Beispiel für einen Funktionsaufruf gemäß der obigen Abbildung:

DoRectanglesOverlap(Vector2D(3, 7),
                    Vector2D(8, 5),
                    Vector2D(6, 4),
                    Vector2D(9, 4));

Die Vergleiche innerhalb der if Block wird wie folgt aussehen:

if ((Pos1.x < Pos2.x + Size2.x) &&
    (Pos1.y < Pos2.y + Size2.y) &&
    (Pos2.x < Pos1.x + Size1.x) &&
    (Pos2.y < Pos1.y + Size1.y))

if ((   3   <    6   +   9    ) &&
    (   7   <    4   +   4    ) &&
    (   6   <    3   +   8    ) &&
    (   4   <    7   +   5    ))

Answer 2

Stellen Sie sich die umgekehrte Frage: Wie kann ich feststellen, ob sich zwei Rechtecke überhaupt nicht schneiden? Offensichtlich schneidet sich ein Rechteck A, das ganz links von Rechteck B liegt, nicht. Ebenso, wenn A ganz rechts liegt. Und ebenso, wenn A ganz über B oder ganz unter B liegt. In jedem anderen Fall schneiden sich A und B.

Was folgt, kann Fehler haben, aber ich bin ziemlich zuversichtlich, was den Algorithmus angeht:

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

bool is_left_of(Rectangle const & a, Rectangle const & b) {
   if (a.x + a.width <= b.x) return true;
   return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
   return is_left_of(b, a);
}

bool not_intersect( Rectangle const & a, Rectangle const & b) {
   if (is_left_of(a, b)) return true;
   if (is_right_of(a, b)) return true;
   // Do the same for top/bottom...
 }

bool intersect(Rectangle const & a, Rectangle const & b) {
  return !not_intersect(a, b);
}

Answer 3

In der Frage verweisen Sie auf die Berechnungen für Rechtecke mit beliebigen Drehwinkeln. Wenn ich den Teil über die Winkel in der Frage verstehe, interpretiere ich jedoch, dass alle Rechtecke senkrecht zueinander stehen.

Die Formel für den Überlappungsbereich ist allgemein bekannt:

Anhand eines Beispiels:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1) alle x-Koordinaten (links und rechts) in einer Liste sammeln, dann sortieren und Duplikate entfernen

1 3 4 5 6

2) Sammle alle y-Koordinaten (oben und unten) in einer Liste, sortiere sie dann und entferne Duplikate

1 2 3 4 6

3) Erstellen eines 2D-Arrays nach Anzahl der Lücken zwischen den eindeutigen x-Koordinaten * Anzahl der Lücken zwischen den eindeutigen y-Koordinaten.

4 \* 4

4) Male alle Rechtecke in dieses Raster und erhöhe die Anzahl jeder Zelle, in der sie vorkommen:

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 2 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

5) Wenn Sie die Rechtecke malen, können Sie die Überlappungen leicht abfangen.

Answer 4

So wird es in der Java-API gemacht:

public boolean intersects(Rectangle r) {
    int tw = this.width;
    int th = this.height;
    int rw = r.width;
    int rh = r.height;
    if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
        return false;
    }
    int tx = this.x;
    int ty = this.y;
    int rx = r.x;
    int ry = r.y;
    rw += rx;
    rh += ry;
    tw += tx;
    th += ty;
    //      overflow || intersect
    return ((rw < rx || rw > tx) &&
            (rh < ry || rh > ty) &&
            (tw < tx || tw > rx) &&
            (th < ty || th > ry));
}

Answer 5

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;
};

//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
    return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
           r1.y1 < r2.y2 && r2.x1 < r1.y2;
}

//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
    return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
           r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}