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

337

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?

Rob Burke
źródło
3
Chciałbym zdaniem rozwiązanie problemu nie pociąga za sobą żadnych mnożenia.
Scott Evernden,

Odpowiedzi:

708
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ę /

Charles Bretana
źródło
489
Jeśli trudno ci sobie wyobrazić, dlaczego to działa, stworzyłem przykładową stronę na silentmatt.com/intersection.html, na której możesz przeciągać prostokąty i sprawdzać porównania.
Matthew Crumley,
4
nie uważasz, że używasz twardych ograniczeń? co jeśli dwa prostokąty zachodzą na siebie dokładnie na tej krawędzi? nie powinieneś rozważyć <=,> = ??
Nawshad Farruque
6
@MatthewCrumley dla A.Y1 <B.Y2 i A.Y2> B.Y1 na twoim łączu, czy znaki GT & lt nie powinny zostać odwrócone?
NikT
15
Musiałem zamienić <i> w ostatnich dwóch porównaniach, aby to zadziałało
DataGreed
17
Nie, odpowiedź jest poprawna, jak podano. Opiera się na użyciu standardowych współrzędnych kartezjańskich. Jeśli używasz innego systemu (Y zwiększa się z góry na dół), a następnie wprowadź odpowiednie zmiany.
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;
}
e.James
źródło
15
Najprostsza i najczystsza odpowiedź.
ldog,
1
@ e.James Myślę, że ostatni B.heightpowinien byćA.height
mat_boy
„min” i „max” są zastrzeżonymi słowami kluczowymi w <windows.h>. możesz to naprawić, wykonując #undef mini #undef max, lub używając różnych nazw parametrów.
mchiasson,
Jeśli używasz intensywnie, możesz wymieniać valueInRange na#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
Ratata Tata
@Nemo W rzeczywistości sprawdzanie xOverlapodbywa się w jednym wymiarze; rectOverlapjest dwuwymiarowy. Można go rozszerzyć do N wymiarów za pomocą pętli.
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
źródło
Niezłe! Stosując prawo De Morgansa uzyskaj: r1.x1 <= r2.x2 && r2.x1 <= r1.x2 && r1.y1 <= r2.y2 && r2.y1 <= r1.y2.
Borzh
23

Ł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 „> =”.

Björn Kechel
źródło
3
I zastosuj do tego prawo de Morgana.
Borzh
6

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);
}
Coryan
źródło
6

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

wprowadź opis zdjęcia tutaj

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    ))
hkBattousai
źródło
3

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));
}
Lyle
źródło
Zauważ, że w C ++ te testy przepełnienia nie będą działać, ponieważ przepełnienie liczb całkowitych ze znakiem jest niezdefiniowane.
Ben Voigt,
2

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.

Będzie
źródło
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
źródło
1

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));
Mike Dunlavey
źródło
1

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ę ..

Zar E Ahmer
źródło
1

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
sachinr
źródło
0

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;
}
Baretta
źródło
2
Dla wytrenowanego oka jest jasne, że miałeś na myśli, że jest to rozszerzenie klasy Rectangle, ale nie podałeś żadnego ograniczenia ani kodu, aby to zrobić. Byłoby miło, gdybyś to zrobił lub wyjaśnił, w jaki sposób ma być stosowana twoja metoda, i punkty bonusowe, jeśli twoje zmienne faktycznie miały wystarczająco opisowe nazwy dla każdego, kto podążyłby za nimi, aby zrozumieć ich cel / zamiar.
tpartee
0

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.

himanshu
źródło
0

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.

Anwit
źródło
0

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

}
}
anchan42
źródło
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 How Teh
źródło
0

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)); 
}
mchiasson
źródło
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
źródło
0

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?

anony
źródło
3
Działa to w przypadku nakładania się (co jest pytaniem), ale nie działa w przypadku przecięcia, ponieważ nie zadziała, jeśli dokładnie przecinają się w rogu.
Lance Roberts
Wypróbowałem ten kod i w ogóle nie działa. Dostaję liczby dodatnie, nawet jeśli w ogóle się nie pokrywają.
Brett,
@Brett: Tak, ponieważ iloczyn dwóch liczb ujemnych jest dodatni.
Ben Voigt,
@BenVoigt, problem polegał na tym, że funkcja nie zwróciła 0, gdy nie było nakładania się. Mój komentarz był bardzo niejasny, ale tak, zawsze otrzymywałem tylko obszar> 0 z tej funkcji.
Brett,
Jeśli pracujesz z liczbami zmiennoprzecinkowymi, generalnie bardzo złym pomysłem jest stosowanie odejmowania i innych rzeczy arytmetycznych przed porównywaniem liczb. Zwłaszcza jeśli chcesz porównać z dokładną wartością - w tym przypadku zero. Działa w teorii, ale nie w praktyce.
maja
-1

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

...

Shrishakti Mishra
źródło