Bestimmen Sie, ob sich zwei Rechtecke überlappen?

337

Ich versuche, ein C ++ - Programm zu schreiben, das die folgenden Eingaben vom Benutzer verwendet, um Rechtecke (zwischen 2 und 5) zu erstellen: Höhe, Breite, x-pos, y-pos. Alle diese Rechtecke existieren parallel zur x- und zur y-Achse, dh alle ihre Kanten haben Steigungen von 0 oder unendlich.

Ich habe versucht, das umzusetzen, was in dieser Frage erwähnt wird, aber ich habe nicht viel Glück.

Meine aktuelle Implementierung führt Folgendes aus:

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

Ich bin mir jedoch nicht ganz sicher, ob (a) ich den Algorithmus, mit dem ich verknüpft habe, korrekt implementiert habe oder ob ich genau weiß, wie ich das interpretieren soll?

Irgendwelche Vorschläge?

Rob Burke
quelle
3
Ich würde denken, dass die Lösung Ihres Problems keine Multiplikation beinhaltet.
Scott Evernden

Antworten:

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

oder unter Verwendung kartesischer Koordinaten

(Wenn X1 die linke Koordinate ist, X2 die rechte Koordinate ist und von links nach rechts zunimmt und Y1 die obere Koordinate ist und Y2 die untere Koordinate ist , die von unten nach oben zunimmt - wenn dies nicht Ihr Koordinatensystem ist [z. B. haben die meisten Computer das Y-Richtung umgekehrt], tauschen Sie die Vergleiche unten aus ) ...

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

Angenommen, Sie haben Rect A und Rect B. Der Beweis ist ein Widerspruch. Eine der vier Bedingungen garantiert, dass keine Überlappung bestehen kann :

  • Cond1. Wenn der linke Rand von A rechts vom rechten Rand von B liegt, dann ist A ganz rechts von B.
  • Cond2. Wenn der rechte Rand von A links vom linken Rand von B liegt, - ist A ganz links von B.
  • Cond3. Wenn die Oberkante von A unter der Unterkante von B liegt, - liegt A vollständig unter B.
  • Cond4. Wenn die Unterkante von A über der Oberkante von B liegt, - liegt A vollständig über B.

Bedingung für Nichtüberlappung ist also

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

Daher ist eine ausreichende Bedingung für Überlappung das Gegenteil.

Überlappung => NICHT (Cond1 oder Cond2 oder Cond3 oder Cond4)

De Morgans Gesetz besagt, dass
Not (A or B or C or D)es dasselbe ist, wie Not A And Not B And Not C And Not D
wir es mit De Morgan getan haben

Nicht Cond1 und nicht Cond2 und nicht Cond3 und nicht Cond4

Dies entspricht:

  • Die linke Kante von A links von der rechten Kante von B, [RectA.Left < RectB.Right ] und
  • A's rechter Rand rechts von B's linkem Rand, [RectA.Right > RectB.Left ] und
  • A ist oben über B unten, [RectA.Top > RectB.Bottom ] und
  • A unten unter B oben [ RectA.Bottom < RectB.Top]

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

Charles Bretana
quelle
489
Wenn Sie Schwierigkeiten haben, sich vorzustellen, warum es funktioniert, habe ich unter Silentmatt.com/intersection.html eine Beispielseite erstellt, auf der Sie Rechtecke ziehen und die Vergleiche anzeigen können.
Matthew Crumley
4
Glaubst du nicht, dass du die harten Zwänge benutzt? Was ist, wenn sich die beiden Rechtecke genau an der Kante überlappen? sollten Sie nicht <=,> = berücksichtigen?
Nawshad Farruque
6
@MatthewCrumley für A.Y1 <B.Y2 und A.Y2> B.Y1 auf Ihrem Link, sollten die Zeichen gt & lt nicht umgekehrt werden?
NikT
15
Ich musste <und> in den letzten beiden Vergleichen tauschen, damit es funktioniert
DataGreed
17
Nein, die Antwort ist wie angegeben korrekt. Es basiert auf der Verwendung von kartesischen Standardkoordinaten. Wenn Sie ein anderes System verwenden (Y von oben nach unten erhöht), nehmen Sie die entsprechenden Anpassungen vor.
Charles Bretana
115
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;
}
James
quelle
15
Einfachste und sauberste Antwort.
ldog
1
@ e.James Ich denke, der letzte B.heightsollte seinA.height
mat_boy
'min' und 'max' sind reservierte Schlüsselwörter in <windows.h>. Sie können das Problem beheben, indem Sie #undef minund #undef maxoder verschiedene Parameternamen verwenden.
Mchiasson
Wenn Sie ausgiebig verwenden, können Sie valueInRange gegen eine#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
Ratata Tata
@Nemo Tatsächlich ist die Überprüfung xOverlapeindimensional. rectOverlapist zweidimensional. Sie kann mit einer Schleife auf N Dimensionen erweitert werden.
Justme0
27
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;
}
David Norman
quelle
Schön! Unter Anwendung des De-Morgans-Gesetzes erhalten Sie: r1.x1 <= r2.x2 && r2.x1 <= r1.x2 && r1.y1 <= r2.y2 && r2.y1 <= r1.y2.
Borzh
23

Es ist einfacher zu überprüfen, ob sich ein Rechteck vollständig außerhalb des anderen befindet

links...

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

oder rechts ...

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

oder oben ...

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

oder unten ...

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

des zweiten Rechtecks ​​kann es unmöglich damit kollidieren. Um eine Funktion zu haben, die ein boolesches Sprichwort zurückgibt, wenn die Rechtecke kollidieren, kombinieren wir die Bedingungen einfach 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 beim Berühren ein positives Ergebnis zu erhalten, können wir "<" und ">" durch "<=" und "> =" ändern.

Björn Kechel
quelle
3
Und wende das Gesetz von de Morgan darauf an.
Borzh
6

Stellen Sie sich die entgegengesetzte Frage: Wie kann ich feststellen, ob sich zwei Rechtecke überhaupt nicht schneiden? Offensichtlich schneidet sich ein Rechteck A vollständig links von Rechteck B nicht. Auch wenn A ganz rechts ist. Und ähnlich, wenn A vollständig über B oder vollständig unter B liegt. In jedem anderen Fall schneiden sich A und B.

Was folgt, kann Fehler haben, aber ich bin ziemlich sicher über den Algorithmus:

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);
}
Coryan
quelle
6

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

Geben Sie hier die Bildbeschreibung ein

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 des ifBlocks sehen wie folgt aus:

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    ))
hkBattousai
quelle
3

So geht's in der Java-API:

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));
}
Lyle
quelle
Beachten Sie, dass diese Tests auf Überlauf in C ++ nicht funktionieren, da der vorzeichenbehaftete Ganzzahlüberlauf undefiniert ist.
Ben Voigt
2

In der Frage verknüpfen Sie die Mathematik, wenn sich Rechtecke in beliebigen Drehwinkeln befinden. Wenn ich jedoch das Bit über Winkel in der Frage verstehe, interpretiere ich, dass alle Rechtecke senkrecht zueinander stehen.

Ein allgemeines Wissen über den Bereich der Überlappungsformel lautet:

Am Beispiel:

   1 2 3 4 5 6

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

1) Sammeln Sie alle x-Koordinaten (links und rechts) in einer Liste, sortieren Sie sie und entfernen Sie Duplikate

1 3 4 5 6

2) Sammeln Sie alle y-Koordinaten (oben und unten) in einer Liste, sortieren Sie sie und entfernen Sie Duplikate

1 2 3 4 6

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

4 * 4

4) Malen Sie alle Rechtecke in dieses Raster und erhöhen Sie die Anzahl der Zellen, über die es auftritt:

   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.

Wille
quelle
2
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;
}
Adam Tegen
quelle
1

Stellen Sie sich Koordinaten nicht als Hinweis darauf vor, wo sich Pixel befinden. Stellen Sie sich diese zwischen den Pixeln vor. 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));
Mike Dunlavey
quelle
1

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

Denken Sie zunächst daran, dass das Koordinatensystem in Computern auf dem Kopf steht. Die x-Achse ist dieselbe wie in der Mathematik, aber die y-Achse nimmt nach unten zu und ab, wenn sie nach oben geht. Wenn Rechtecke von der Mitte gezeichnet werden. Wenn x1-Koordinaten größer als x2 plus die Hälfte der Breite sind. dann bedeutet es, dass sie sich zur Hälfte berühren. und auf die gleiche Weise nach unten + die Hälfte seiner Höhe. es wird kollidieren ..

Zar E Ahmer
quelle
1

Nehmen wir an, die beiden Rechtecke sind Rechteck A und Rechteck B. Ihre Zentren seien A1 und B1 (die Koordinaten von A1 und B1 können leicht ermittelt werden), die Höhen seien Ha und Hb, die Breite sei Wa und Wb, sei dx die Breite (x) Abstand zwischen A1 und B1 und dy ist der Abstand Höhe (y) zwischen A1 und B1.

Jetzt können wir sagen, wir können sagen, A und B überlappen sich: wann

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

Ich habe eine C # -Version implementiert, die leicht in C ++ konvertiert werden kann.

public bool Intersects ( Rectangle rect )
{
  float ulx = Math.Max ( x, rect.x );
  float uly = Math.Max ( y, rect.y );
  float lrx = Math.Min ( x + width, rect.x + rect.width );
  float lry = Math.Min ( y + height, rect.y + rect.height );

  return ulx <= lrx && uly <= lry;
}
Baretta
quelle
2
Für das geschulte Auge ist klar, dass Sie gemeint haben, dass dies eine Erweiterungsklasse für Rectangle ist, aber Sie haben keine Begrenzung oder keinen Code angegeben, um dies tatsächlich zu tun. Es wäre schön, wenn Sie dies getan oder erklärt hätten, wie Ihre Methode verwendet werden soll, und Bonuspunkte, wenn Ihre Variablen tatsächlich genügend beschreibende Namen hätten, damit jeder, der ihnen folgt, ihren Zweck / ihre Absicht verstehen kann.
tpartee
0

Ich habe eine sehr einfache Lösung

x1, y1 x2, y2, l1, b1, l2 seien Koordinaten und Längen bzw. Breiten von ihnen

Betrachten Sie die Bedingung ((x2

Jetzt überlappen sich diese Rechtecke nur noch, wenn die Punktdiagonale zu x1, y1 innerhalb des anderen Rechtecks ​​oder ähnlich die Punktdiagonale zu x2, y2 innerhalb des anderen Rechtecks ​​liegt. was genau die obige Bedingung impliziert.

Himanshu
quelle
0

A und B sind zwei Rechtecke. C ist ihr Deckrechteck.

four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)

A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);

C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);

A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height) 

Es kümmert sich um alle möglichen Fälle.

Anwit
quelle
0

Dies stammt aus Übung 3.28 aus dem Buch Einführung in die Java-Programmierung - Umfassende Ausgabe. Der Code prüft, ob die beiden Rechtecke ein Einzug sind, ob sich eines innerhalb des anderen befindet und ob sich eines außerhalb des anderen befindet. Wenn keine dieser Bedingungen erfüllt ist, überlappen sich die beiden.

** 3.28 (Geometrie: zwei Rechtecke) Schreiben Sie ein Programm, das den Benutzer auffordert, die mittleren x-, y-Koordinaten, die Breite und die Höhe von zwei Rechtecken einzugeben, und bestimmt, ob sich das zweite Rechteck innerhalb des ersten befindet oder sich mit dem ersten überlappt. wie in Abbildung 3.9 gezeigt. Testen Sie Ihr Programm, um alle Fälle abzudecken. Hier sind die Probeläufe:

Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r1 ein: 2,5 4 2,5 43 Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r2 ein: 1,5 5 0,5 3 r2 befindet sich innerhalb von r1

Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r1 ein: 1 2 3 5.5 Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r2 ein: 3 4 4.5 5 r2 überlappt r1

Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r1 ein: 1 2 3 3 Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r2 ein: 40 45 3 2 r2 überlappt r1 nicht

import java.util.Scanner;

public class ProgrammingEx3_28 {
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    System.out
            .print("Enter r1's center x-, y-coordinates, width, and height:");
    double x1 = input.nextDouble();
    double y1 = input.nextDouble();
    double w1 = input.nextDouble();
    double h1 = input.nextDouble();
    w1 = w1 / 2;
    h1 = h1 / 2;
    System.out
            .print("Enter r2's center x-, y-coordinates, width, and height:");
    double x2 = input.nextDouble();
    double y2 = input.nextDouble();
    double w2 = input.nextDouble();
    double h2 = input.nextDouble();
    w2 = w2 / 2;
    h2 = h2 / 2;

    // Calculating range of r1 and r2
    double x1max = x1 + w1;
    double y1max = y1 + h1;
    double x1min = x1 - w1;
    double y1min = y1 - h1;
    double x2max = x2 + w2;
    double y2max = y2 + h2;
    double x2min = x2 - w2;
    double y2min = y2 - h2;

    if (x1max == x2max && x1min == x2min && y1max == y2max
            && y1min == y2min) {
        // Check if the two are identicle
        System.out.print("r1 and r2 are indentical");

    } else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
            && y1min >= y2min) {
        // Check if r1 is in r2
        System.out.print("r1 is inside r2");
    } else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
            && y2min >= y1min) {
        // Check if r2 is in r1
        System.out.print("r2 is inside r1");
    } else if (x1max < x2min || x1min > x2max || y1max < y2min
            || y2min > y1max) {
        // Check if the two overlap
        System.out.print("r2 does not overlaps r1");
    } else {
        System.out.print("r2 overlaps r1");
    }

}
}
anchan42
quelle
0
bool Square::IsOverlappig(Square &other)
{
    bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
    bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
    bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
    bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
    return result1 | result2 | result3 | result4;
}
Kok Wie die
quelle
0

Für diejenigen unter Ihnen, die Mittelpunkte und halbe Größen für ihre Rechteckdaten anstelle der typischen x, y, w, h oder x0, y0, x1, x1 verwenden, gehen Sie wie folgt vor:

#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)); 
}
mchiasson
quelle
0
struct point { int x, y; };

struct rect { point tl, br; }; // top left and bottom right points

// return true if rectangles overlap
bool overlap(const rect &a, const rect &b)
{
    return a.tl.x <= b.br.x && a.br.x >= b.tl.x && 
           a.tl.y >= b.br.y && a.br.y <= b.tl.y;
}
Edward Karak
quelle
0

Wenn sich die Rechtecke überlappen, ist der Überlappungsbereich größer als Null. Lassen Sie uns nun den Überlappungsbereich finden:

Wenn sie sich überlappen, ist die linke Kante von Overlap-Rect die max(r1.x1, r2.x1)rechte Kante und die rechte Kantemin(r1.x2, r2.x2) . Die Länge der Überlappung wird also seinmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)

Das Gebiet wird also sein:

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

Wenn area = 0dann, überlappen sie sich nicht.

Einfach, nicht wahr?

anony
quelle
3
Dies funktioniert für Überlappungen (was die Frage ist), funktioniert jedoch nicht für Schnittpunkte, da es nicht funktioniert, wenn sie sich genau an einer Ecke schneiden.
Lance Roberts
Ich habe diesen Code ausprobiert und er funktioniert überhaupt nicht. Ich bekomme nur positive Zahlen, auch wenn sie sich überhaupt nicht überschneiden.
Brett
@Brett: Ja, weil das Produkt zweier negativer Zahlen positiv ist.
Ben Voigt
@ BenVoigt, das Problem war, dass die Funktion keine 0 zurückgab, wenn es keine Überlappung gab. Ich war mit meinem Kommentar sehr unklar, aber ja, ich habe von dieser Funktion immer nur einen Bereich> 0 erhalten.
Brett
Wenn Sie mit Gleitkommazahlen arbeiten, ist es im Allgemeinen eine sehr schlechte Idee, vor Zahlenvergleichen Subtraktionen und andere arithmetische Elemente zu verwenden. Vor allem, wenn Sie mit einem genauen Wert vergleichen müssen - in diesem Fall Null. Es funktioniert theoretisch, aber nicht in der Praxis.
Maja
-1

Java-Code, um herauszufinden, ob sich Rechtecke berühren oder überlappen

...

for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
        if ( i != j ) {
            Rectangle rectangle1 = rectangles.get(i);
            Rectangle rectangle2 = rectangles.get(j);

            int l1 = rectangle1.l; //left
            int r1 = rectangle1.r; //right
            int b1 = rectangle1.b; //bottom
            int t1 = rectangle1.t; //top

            int l2 = rectangle2.l;
            int r2 = rectangle2.r;
            int b2 = rectangle2.b;
            int t2 = rectangle2.t;

            boolean topOnBottom = t2 == b1;
            boolean bottomOnTop = b2 == t1;
            boolean topOrBottomContact = topOnBottom || bottomOnTop;

            boolean rightOnLeft = r2 == l1;
            boolean leftOnRight = l2 == r1;
            boolean rightOrLeftContact = leftOnRight || rightOnLeft;

            boolean leftPoll = l2 <= l1 && r2 >= l1;
            boolean rightPoll = l2 <= r1 && r2 >= r1;
            boolean leftRightInside = l2 >= l1 && r2 <= r1;
            boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside;

            boolean bottomPoll = t2 >= b1 && b2 <= b1;
            boolean topPoll = b2 <= b1 && t2 >= b1;
            boolean topBottomInside = b2 >= b1 && t2 <= t1;
            boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside;


            boolean topInBetween = t2 > b1 && t2 < t1;
            boolean bottomInBetween = b2 > b1 && b2 < t1;
            boolean topBottomInBetween = topInBetween || bottomInBetween;

            boolean leftInBetween = l2 > l1 && l2 < r1;
            boolean rightInBetween = r2 > l1 && r2 < r1;
            boolean leftRightInBetween = leftInBetween || rightInBetween;

            if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) {
                path[i][j] = true;
            }
        }
    }
}

...

Shrishakti Mishra
quelle