Ustal, czy dwa prostokąty nachodzą na siebie?

Próbuję napisać program C ++, który pobiera następujące dane wejściowe od użytkownika do budowy prostokątów (od 2 do 5): wysokość, szerokość, x-pos, y-pos. Wszystkie te prostokąty będą istnieć równolegle do osi xi y, to znaczy wszystkie ich krawędzie będą miały nachylenie 0 lub nieskończoność.

Próbowałem wdrożyć to, o czym mowa w tym pytaniu, ale nie mam dużo szczęścia.

Moja obecna implementacja wykonuje następujące czynności:

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

Nie jestem jednak do końca pewien, czy (a) poprawnie zaimplementowałem algorytm, z którym się łączyłem, czy też dokładnie, jak to interpretować?

Jakieś sugestie?

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

lub używając współrzędnych kartezjańskich

(X1 jest lewą współrzędną, X2 jest prawą współrzędną, zwiększa się od lewej do prawej, a Y1 jest górną współrzędną, a Y2 jest dolną współrzędną, rośnie od dołu do góry - jeśli nie w taki sposób układ współrzędnych [np. Większość komputerów ma Kierunek Y odwrócony], zamień porównania poniżej ) ...

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

Załóżmy, że masz Rect A, a Rect B. Dowód jest sprzeczny. Każdy z czterech warunków gwarantuje, że nie może zachodzić na siebie nakładanie się :

• Cond1. Jeśli lewa krawędź A znajduje się na prawo od prawej krawędzi B, - A jest całkowicie na prawo od B
• Cond2. Jeśli prawa krawędź A znajduje się na lewo od lewej krawędzi B, - A jest całkowicie na lewo od B.
• Cond3. Jeśli górna krawędź A znajduje się poniżej dolnej krawędzi B, - A jest całkowicie poniżej B
• Cond4. Jeśli dolna krawędź A znajduje się powyżej górnej krawędzi B, - wówczas A jest całkowicie powyżej B

Zatem warunkiem braku nakładania się jest

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

Dlatego wystarczający warunek nakładania się jest odwrotny.

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

Prawo De Morgana mówi, że
Not (A or B or C or D)to samo, co Not A And Not B And Not C And Not D
przy użyciu De Morgana, mamy

Nie Cond1 i nie Cond2 i nie Cond3 i nie Cond4

Jest to równoważne z:

• Lewa krawędź A na lewo od prawej krawędzi B, [ RectA.Left < RectB.Right] i
• Prawa krawędź A na prawo od lewej krawędzi B, [ RectA.Right > RectB.Left] i
• Góra A powyżej dołu B, [ RectA.Top > RectB.Bottom] i
• A na dole poniżej B na górze [ RectA.Bottom < RectB.Top]

Uwaga 1 : Jest dość oczywiste, że tę samą zasadę można rozszerzyć na dowolną liczbę wymiarów.
Uwaga 2 : Powinno być również dość oczywiste policzyć nakładanie się tylko jednego piksela, zmienić <i / lub >na tej granicy na a <=lub a >=.
Uwaga 3 : Ta odpowiedź, przy użyciu współrzędnych kartezjańskich (X, Y), oparta jest na standardowych algebraicznych współrzędnych kartezjańskich (x zwiększa się od lewej do prawej, a Y zwiększa się od dołu do góry). Oczywiście, gdy system komputerowy może inaczej mechanizować współrzędne ekranu (np. Zwiększenie Y od góry do dołu lub X od prawej do lewej), należy odpowiednio dostosować składnię /

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

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

Łatwiej jest sprawdzić, czy prostokąt jest całkowicie poza drugim, więc jeśli tak jest

po lewej...

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

lub po prawej ...

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

lub na górze ...

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

lub na dole ...

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

drugiego prostokąta nie może się z nim zderzyć. Aby więc mieć funkcję, która zwraca wartość logiczną mówiącą, że zderzają się prostokąty, po prostu łączymy warunki logicznymi ORami i negujemy wynik:

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

Aby uzyskać pozytywny wynik tylko po dotknięciu, możemy zmienić „<” i „>” za pomocą „<=” i „> =”.

Zadaj sobie odwrotne pytanie: jak ustalić, czy dwa prostokąty w ogóle się nie przecinają? Oczywiście prostokąt A całkowicie na lewo od prostokąta B nie przecina się. Także jeśli A jest całkowicie po prawej stronie. Podobnie, jeśli A jest całkowicie powyżej B lub całkowicie poniżej B. W każdym innym przypadku przecinają się A i B.

Poniższe informacje mogą zawierać błędy, ale jestem pewien algorytmu:

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

Załóżmy, że zdefiniowałeś położenia i rozmiary prostokątów w następujący sposób:

Moja implementacja C ++ wygląda następująco:

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

Przykładowe wywołanie funkcji zgodnie z powyższym rysunkiem:

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

Porównania wewnątrz ifbloku będą wyglądały jak poniżej:

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

Oto jak to się robi w API Java:

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

W pytaniu łączysz się z matematyką dotyczącą tego, kiedy prostokąty mają dowolne kąty obrotu. Jeśli jednak rozumiem fragment pytania o kątach, interpretuję, że wszystkie prostokąty są do siebie prostopadłe.

Ogólna wiedza na temat formuły nakładania się jest następująca:

Korzystając z przykładu:

   1 2 3 4 5 6

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

1) zbierz wszystkie współrzędne x (lewą i prawą) do listy, a następnie posortuj je i usuń duplikaty

1 3 4 5 6

2) zbierz wszystkie współrzędne Y (górne i dolne) na listę, a następnie posortuj je i usuń duplikaty

1 2 3 4 6

3) utwórz tablicę 2D według liczby odstępów między unikalnymi współrzędnymi x * liczba odstępów między unikalnymi współrzędnymi y.

4 * 4

4) namaluj wszystkie prostokąty na tej siatce, zwiększając liczbę każdej komórki, w której występuje:

   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) Kiedy malujesz prostokąty, łatwo jest przechwycić nakładki.

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

Nie uważaj współrzędnych za wskazujące, gdzie są piksele. Pomyśl o nich jako między pikselami. W ten sposób pole prostokąta 2x2 powinno wynosić 4, a nie 9.

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

Najłatwiej jest

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

przede wszystkim pamiętaj, że w komputerach układ współrzędnych jest odwrócony. oś x jest taka sama jak w matematyce, ale oś y zwiększa się w dół i zmniejsza wraz z poruszaniem się w górę ... jeśli prostokąt jest rysowany od środka. jeśli współrzędne x1 są większe niż x2 plus jego połowa szerokości. oznacza to, że przejście do połowy dotknie się. i w ten sam sposób schodząc w dół + połowa jego wysokości. zderzy się ..

Powiedzmy, że dwa prostokąty to prostokąt A i prostokąt B. Niech ich środkami będą A1 i B1 (współrzędne A1 i B1 można łatwo znaleźć), niech wysokości będą Ha i Hb, szerokość Wa i Wb, niech dx będzie szerokość (x) odległość między A1 a B1 i dy oznacza wysokość (y) odległość między A1 a B1.

Teraz możemy powiedzieć, że możemy powiedzieć, że A i B pokrywają się: kiedy

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

Zaimplementowałem wersję C #, łatwo ją przekonwertować na C ++.

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

Mam bardzo łatwe rozwiązanie

niech x1, y1 x2, y2, l1, b1, l2 będą odpowiednio kordynatami oraz ich długości i szerokości

rozważyć warunek ((x2

teraz jedynym sposobem, w jaki prostokąt będzie się nakładał, jest to, że punkt przekątny do x1, y1 będzie leżał wewnątrz drugiego prostokąta lub podobnie punkt przekątny do x2, y2 będzie leżał wewnątrz drugiego prostokąta. co implikuje dokładnie powyższy warunek.

A i B będą dwoma prostokątami. C będzie ich prostokątem okrywającym.

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) 

Dba o wszystkie możliwe przypadki.

Pochodzi z ćwiczenia 3.28 z książki Wprowadzenie do programowania Java - edycja kompleksowa. Kod sprawdza, czy dwa prostokąty są wcięte, czy jeden jest w drugim i czy jeden znajduje się poza drugim. Jeśli żaden z tych warunków nie jest spełniony, oba się pokrywają.

** 3,28 (Geometria: dwa prostokąty) Napisz program, który zachęci użytkownika do wprowadzenia środkowych współrzędnych x, y, szerokości i wysokości dwóch prostokątów i określi, czy drugi prostokąt znajduje się wewnątrz pierwszego, czy zachodzi na pierwszy, jak pokazano na rysunku 3.9. Przetestuj swój program na wszystkie przypadki. Oto przykładowe przebiegi:

Podaj współrzędne x1, y, szerokość i wysokość r1: 2,5 4 2,5 43 Podaj współrzędne x2, y, szerokość i wysokość r2: 1,5 5 0,5 3 r2 znajduje się wewnątrz r1

Podaj współrzędne x1, y, szerokość i wysokość r1: 1 2 3 5.5 Podaj współrzędne x2, y, szerokość i wysokość r3: 3 4 4,5 5 r2 nakłada się na r1

Wprowadź współrzędne x1, y, szerokość i wysokość r1: 1 2 3 3 Wprowadź współrzędne x2, y, szerokość i wysokość r2: 40 45 3 2 r2 nie zachodzi na 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");
    }

}
}

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

Dla tych z was, którzy używają punktów środkowych i połowy wielkości dla swoich danych prostokątnych, zamiast typowych x, y, w, h lub x0, y0, x1, x1, oto jak to zrobić:

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

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

Jeśli prostokąty nachodzą na siebie, wówczas obszar nakładania się będzie większy od zera. Teraz znajdźmy obszar nakładania się:

Jeśli nachodzą na siebie, to lewa krawędź zakładki-prostokąt będzie max(r1.x1, r2.x1)prawą krawędzią min(r1.x2, r2.x2). Tak więc długość zakładki będzie wynosićmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)

Tak więc obszar będzie:

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

Jeśli area = 0to nie pokrywają się.

Proste, prawda?

„Jeśli wykonasz odejmowanie współrzędnych x lub y odpowiadających wierzchołkom dwóch zwróconych do każdego prostokąta, jeśli wyniki są tego samego znaku, dwa prostokąty nie nachodzą na osie, które” (przepraszam, nie jestem pewien, czy moje tłumaczenie jest poprawne )

Źródło: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html

Kod Java, aby dowiedzieć się, czy prostokąty stykają się lub nakładają na siebie

...

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

...