Determine se dois retângulos se sobrepõem?

337

Eu estou tentando escrever um programa C ++ que leva as seguintes entradas do usuário para construir retângulos (entre 2 e 5): altura, largura, x-pos, y-pos. Todos esses retângulos existirão paralelos aos eixos xe y, ou seja, todas as suas arestas terão inclinações de 0 ou infinito.

Eu tentei implementar o que é mencionado nesta pergunta, mas não estou tendo muita sorte.

Minha implementação atual faz o seguinte:

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

No entanto, não tenho certeza se (a) implementei o algoritmo ao qual vinculei corretamente, ou se fiz exatamente como interpretar isso?

Alguma sugestão?

Rob Burke
fonte
3
Eu acho que a solução para o seu problema não envolve qualquer multiplicação.
23118 Scott Evernden

Respostas:

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

ou, usando coordenadas cartesianas

(Com X1 sendo coordenado à esquerda, X2 sendo coordenado à direita , aumentando da esquerda para a direita e Y1 sendo a coordenação superior e Y2 sendo a coordenação inferior, aumentando de baixo para cima - se não é assim que seu sistema de coordenadas [por exemplo, a maioria dos computadores tem o Direção Y invertida], troque as comparações abaixo ) ...

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

Digamos que você tenha o Reto A e o Reto B. A prova é por contradição. Qualquer uma das quatro condições garante que nenhuma sobreposição possa existir :

  • Cond1. Se a borda esquerda de A estiver à direita da borda direita de B, - então A estará totalmente à direita de B
  • Cond2. Se a borda direita de A estiver à esquerda da borda esquerda de B, - então A estará totalmente à esquerda de B
  • Cond3. Se a borda superior de A estiver abaixo da borda inferior de B, - então A estará totalmente abaixo de B
  • Cond4. Se a borda inferior de A estiver acima da borda superior de B, - então A estará totalmente acima de B

Portanto, a condição para não sobreposição é

NÃO Sobreposição => Cond1 ou Cond2 ou Cond3 ou Cond4

Portanto, uma condição suficiente para Sobreposição é o oposto.

Sobreposição => NÃO (Cond1 ou Cond2 ou Cond3 ou Cond4)

A lei de De Morgan diz que
Not (A or B or C or D)é o mesmo que Not A And Not B And Not C And Not D
usar De Morgan, temos

Não Cond1 e não Cond2 e não Cond3 e não Cond4

Isso é equivalente a:

  • Borda esquerda de A à esquerda da borda direita de B, [ RectA.Left < RectB.Right] e
  • A borda direita de A para a direita da borda esquerda de B, [ RectA.Right > RectB.Left] e
  • O topo de A acima do fundo de B, [ RectA.Top > RectB.Bottom] e
  • Parte inferior de A abaixo da parte superior de B [ RectA.Bottom < RectB.Top]

Nota 1 : É bastante óbvio que esse mesmo princípio pode ser estendido a qualquer número de dimensões.
Nota 2 : também deve ser bastante óbvio contar sobreposições de apenas um pixel, alterar o <e / ou o >limite desse para a <=ou a >=.
Nota 3 : Essa resposta, ao utilizar coordenadas cartesianas (X, Y), é baseada em coordenadas cartesianas algébricas padrão (x aumenta da esquerda para a direita e Y aumenta de baixo para cima). Obviamente, onde um sistema de computador pode mecanizar as coordenadas da tela de maneira diferente (por exemplo, aumentando Y de cima para baixo ou X Da direita para a esquerda), a sintaxe precisará ser ajustada de acordo /

Charles Bretana
fonte
489
Se você está tendo dificuldades para visualizar por que isso funciona, criei uma página de exemplo em silentmatt.com/intersection.html, onde você pode arrastar retângulos e ver as comparações.
Matthew Crumley
4
você não acha que está usando as restrições rígidas? e se os dois retângulos se sobrepuserem exatamente na borda? você não deveria considerar <=,> = ??
Nawshad Farruque
6
@MatthewCrumley para A.Y1 <B.Y2 e A.Y2> B.Y1 no seu link, os sinais gt & lt não devem ser revertidos?
NikT
15
Eu tive que trocar <e> nas últimas duas comparações para fazer o trabalho
DataGreed
17
Não, a resposta está correta conforme indicado. É baseado no uso de coordenadas cartesianas padrão. Se você estiver usando um sistema diferente (Y aumentando de cima para baixo), faça os ajustes apropriados.
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
fonte
15
Resposta mais simples e limpa.
Ldog 06/07/19
11
@ e.James Eu acho que a última B.heightdeve serA.height
mat_boy
'min' e 'max' são palavras-chave reservadas em <windows.h>. você pode corrigi-lo fazendo #undef mine #undef max, ou usando nomes de parâmetros diferentes.
Mchiasson
Se você usar extensivamente, você pode trocar valueInRange para um#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
Ratata Tata
@Nemo Na verdade, a verificação xOverlapestá em uma dimensão; rectOverlapé bidimensional. Pode ser estendido para N dimensões usando um loop.
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
fonte
Agradável! A aplicação da lei de De Morgans obtém: r1.x1 <= r2.x2 && r2.x1 <= r1.x2 && r1.y1 <= r2.y2 && r2.y1 <= r1.y2.
Borzh 23/09/14
23

É mais fácil verificar se um retângulo está completamente fora do outro, portanto, se é

à esquerda...

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

ou à direita ...

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

ou por cima ...

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

ou no fundo ...

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

do segundo retângulo, ele não pode colidir com ele. Portanto, para ter uma função que retorna um ditado booleano quando os retângulos colidem, simplesmente combinamos as condições por ORs lógicos e negamos o resultado:

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

Para já receber um resultado positivo ao tocar apenas, podemos alterar o "<" e ">" por "<=" e "> =".

Björn Kechel
fonte
3
E aplique a lei de de Morgan a ela.
Borzh
6

Faça a si mesmo a pergunta oposta: como posso determinar se dois retângulos não se cruzam? Obviamente, um retângulo A completamente à esquerda do retângulo B não se cruza. Além disso, se A estiver completamente à direita. E da mesma forma, se A estiver completamente acima de B ou completamente abaixo de B. Em qualquer outro caso, A e B se cruzam.

O que se segue pode ter erros, mas estou bastante confiante sobre o algoritmo:

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);
}
coriano
fonte
6

Suponha que você definiu as posições e tamanhos dos retângulos assim:

insira a descrição da imagem aqui

Minha implementação em C ++ é assim:

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

Um exemplo de chamada de função de acordo com a figura fornecida acima:

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

As comparações dentro do ifbloco serão parecidas abaixo:

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
fonte
3

Veja como isso é feito na 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
fonte
Observe que, em C ++, esses testes para excesso não funcionarão, porque o excesso inteiro assinado é indefinido.
Ben Voigt
2

Na pergunta, você vincula a matemática para quando os retângulos estão em ângulos arbitrários de rotação. Se eu entendo um pouco sobre os ângulos da pergunta, interpreto que todos os retângulos são perpendiculares um ao outro.

Um conhecimento geral da área da fórmula de sobreposição é:

Usando o exemplo:

   1 2 3 4 5 6

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

1) colete todas as coordenadas x (esquerda e direita) em uma lista, classifique-a e remova duplicatas

1 3 4 5 6

2) colete todas as coordenadas y (superior e inferior) em uma lista, classifique-a e remova as duplicatas

1 2 3 4 6

3) crie uma matriz 2D pelo número de intervalos entre as coordenadas x únicas * número de intervalos entre as coordenadas y exclusivas.

4 * 4

4) pinte todos os retângulos nessa grade, incrementando a contagem de cada célula em que ocorre:

   1 3 4 5 6

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

5) Ao pintar os retângulos, é fácil interceptar as sobreposições.

Vai
fonte
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
fonte
1

Não pense nas coordenadas como indicando onde os pixels estão. Pense neles como estando entre os pixels. Dessa forma, a área de um retângulo 2x2 deve ser 4, não 9.

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

A maneira mais fácil é

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

Antes de tudo, lembre-se de que, nos computadores, o sistema de coordenadas está de cabeça para baixo. o eixo x é igual ao da matemática, mas o eixo y aumenta para baixo e diminui ao subir .. se o retângulo for desenhado do centro. se as coordenadas x1 forem maiores que x2 mais sua metade da largura. então significa que metade deles se tocarão. e da mesma maneira descendo + metade da sua altura. vai colidir ..

Zar E Ahmer
fonte
1

Digamos que os dois retângulos sejam retângulo A e retângulo B. Deixe seus centros serem A1 e B1 (as coordenadas de A1 e B1 podem ser facilmente encontradas), deixe as alturas Ha e Hb, largura seja Wa e Wb, seja dx o largura (x) distância entre A1 e B1 e dy é a altura (y) da distância entre A1 e B1.

Agora podemos dizer que podemos dizer que A e B se sobrepõem: quando

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

Eu implementei uma versão C #, ela é facilmente convertida em 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
fonte
2
Para os olhos treinados, é claro que você queria que isso fosse uma classe de extensão para o Retângulo, mas você não forneceu nenhum código ou limite para realmente fazer isso. Seria bom se você tivesse feito isso ou explicado que é assim que seu método deve ser usado, e pontos de bônus se suas variáveis ​​realmente tiverem nomes descritivos o suficiente para que qualquer pessoa o acompanhe para entender seu propósito / intenção.
precisa saber é
0

Eu tenho uma solução muito fácil

sejam x1, y1 x2, y2, l1, b1, l2, sejam cordinados e comprimentos e larguras deles respectivamente

considere a condição ((x2

Agora, a única maneira de sobrepor esse retângulo é se o ponto diagonal de x1, y1 estiver dentro do outro retângulo ou, da mesma forma, o ponto diagonal de x2, y2 estiver dentro do outro retângulo. que é exatamente a condição acima implica.

himanshu
fonte
0

A e B são dois retângulos. C seja seu retângulo de cobertura.

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) 

Ele cuida de todos os casos possíveis.

Anwit
fonte
0

Isso é do exercício 3.28 do livro Introduction to Java Programming- Comprehensive Edition. O código testa se os dois retângulos são idênticos, se um está dentro do outro e se um está fora do outro. Se nenhuma dessas condições for atendida, as duas se sobrepõem.

** 3,28 (Geometria: dois retângulos) Escreva um programa que solicite ao usuário que insira as coordenadas x, y, largura e altura centrais de dois retângulos e determine se o segundo retângulo está dentro do primeiro ou se sobrepõe ao primeiro, como mostra a Figura 3.9. Teste seu programa para cobrir todos os casos. Aqui estão os exemplos de execuções:

Digite as coordenadas x, y, largura e altura do centro de r1: 2,5 4 2,5 43 Digite as coordenadas x, y, largura e altura do centro de r2: 1,5 5 0,5 3 r2 está dentro de r1

Digite o centro de r1 - coordenadas x, y, largura e altura: 1 2 3 5.5 Digite o centro de r2 - coordenadas x, largura e altura: 3 4 4.5 5 r2 sobrepõe r1

Digite o centro de r1 - coordenadas x, y, largura e altura: 1 2 3 3 Digite o centro de r1 - coordenadas x, largura e altura: 40 45 3 2 r2 não se sobrepõe a 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
fonte
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
fonte
0

Para aqueles que usam pontos centrais e meios tamanhos para seus dados retangulares, em vez dos x, y, w, h ou x0, y0, x1, x1 típicos, veja como fazê-lo:

#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
fonte
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
fonte
0

Se os retângulos se sobrepuserem, a área de sobreposição será maior que zero. Agora vamos encontrar a área de sobreposição:

Se eles se sobrepuserem, a borda esquerda de overlap-rect será a max(r1.x1, r2.x1)borda direita e serámin(r1.x2, r2.x2) . Portanto, o comprimento da sobreposição serámin(r1.x2, r2.x2) - max(r1.x1, r2.x1)

Então a área será:

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

Se area = 0então eles não se sobrepõem.

Simples, não é?

anonia
fonte
3
Isso funciona para sobreposição (que é a questão), mas não funciona para interseção, pois não funcionará se eles se cruzarem exatamente em um canto.
Lance Roberts
Eu tentei esse código e ele não funciona. Estou apenas obtendo números positivos, mesmo quando eles não se sobrepõem.
Brett
@Brett: Sim, porque o produto de dois números negativos é positivo.
Ben Voigt
@ BenVoigt, o problema era que a função não retornava 0 quando não havia sobreposição. Não fiquei muito claro com o meu comentário, mas sim, apenas recebi a área> 0 dessa função.
Brett
Se você estiver trabalhando com números de ponto flutuante, geralmente é uma péssima idéia usar subtrações e outras coisas aritméticas antes de qualquer comparação de número. Especialmente se você precisar comparar com um valor exato - neste caso, zero. Funciona na teoria, mas não na prática.
Maja
-1

Código Java para descobrir se os retângulos estão em contato ou se sobrepõem

...

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
fonte