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

Ich habe eine sehr einfache Lösung

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

betrachten Sie die Bedingung ((x2

Diese Rechtecke können sich nur dann überschneiden, wenn der Punkt diagonal zu x1,y1 innerhalb des anderen Rechtecks liegt oder der Punkt diagonal zu x2,y2 innerhalb des anderen Rechtecks liegt, was genau die obige Bedingung impliziert.

Answer 2

A und B sind zwei Rechtecke. C sei ihr überdeckendes Rechteck.

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) 

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

Answer 3

Dies ist die Übung 3.28 aus dem Buch Introduction to Java Programming - Comprehensive Edition. Der Code testet, ob die beiden Rechtecke eingerückt sind, ob eines innerhalb des anderen liegt und ob eines außerhalb des anderen liegt. Wenn keine dieser Bedingungen erfüllt ist, überschneiden sich die beiden Rechtecke.

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

Geben Sie die x- und y-Koordinaten, die Breite und die Höhe des Mittelpunkts von r1 ein: 2,5 4 2,5 43 Geben Sie den Mittelpunkt, die x- und y-Koordinaten, die Breite und die Höhe von r2 ein: 1.5 5 0.5 3 r2 liegt innerhalb von r1

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

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

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

}
}

Answer 4

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

Answer 5

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