Определить, перекрывают ли два прямоугольника друг друга?

337

Я пытаюсь написать программу на C ++, которая использует следующие входные данные от пользователя для построения прямоугольников (между 2 и 5): высота, ширина, x-pos, y-pos. Все эти прямоугольники будут существовать параллельно осям x и y, то есть все их ребра будут иметь наклон 0 или бесконечность.

Я пытался реализовать то, что упоминается в этом вопросе, но мне не очень повезло.

Моя текущая реализация делает следующее:

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

Однако я не совсем уверен, что (а) я правильно реализовал алгоритм, на который я ссылался, или я сделал именно так, как это интерпретировать?

Какие-либо предложения?

Роб Берк
источник
3
я думаю , что решение вашей проблемы не связаны с какой - либо умножение.
Скотт Эверден

Ответы:

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

или, используя декартовы координаты

(Если X1 - это левая координата, X2 - правая координата, увеличивается слева направо, а Y1 - верхняя координата, а Y2 - нижняя координата, увеличивается снизу вверх - если это не так, как ваша система координат [например, большинство компьютеров имеют Обратное направление Y], поменяйте местами сравнения ниже ) ...

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

Скажем, у вас есть Rect A и Rect B. Доказательство противоречит. Любое из четырех условий гарантирует, что перекрытия не может быть :

  • COND1. Если левый край A находится справа от правого края B, - тогда A находится полностью справа от B
  • Cond2. Если правый край А находится слева от левого края В, то А находится полностью слева от В
  • Cond3. Если верхний край A находится ниже нижнего края B, - тогда A полностью ниже B
  • Cond4. Если нижний край А находится над верхним краем В, - тогда А полностью над В

Таким образом, условие не перекрытия

NON-Overlap => Cond1 или Cond2 или Cond3 или Cond4

Следовательно, достаточным условием перекрытия является обратное.

Перекрытие => НЕ (Cond1 или Cond2 или Cond3 или Cond4)

Закон де Моргана гласит
Not (A or B or C or D), что так же, как Not A And Not B And Not C And Not D
и при использовании де Моргана, мы имеем

Не Cond1 и не Cond2 и не Cond3 и не Cond4

Это эквивалентно:

  • Левый край А слева от правого края В, [ RectA.Left < RectB.Right] и
  • Правый край А справа от левого края В, [ RectA.Right > RectB.Left] и
  • Верх А над низом В, [ RectA.Top > RectB.Bottom] и
  • А снизу под В сверху [ RectA.Bottom < RectB.Top]

Примечание 1 : Совершенно очевидно, что этот же принцип можно распространить на любое количество измерений.
Примечание 2 : Также должно быть достаточно очевидно подсчитывать перекрытия только одного пикселя, изменять <и / или значение >на этой границе на a <=или a >=.
Примечание 3 : Этот ответ при использовании декартовых координат (X, Y) основан на стандартных алгебраических декартовых координатах (x увеличивается слева направо, а Y увеличивается снизу вверх). Очевидно, что если компьютерная система может механизировать координаты экрана по-разному (например, увеличивая Y сверху вниз или X справа налево), синтаксис необходимо будет соответствующим образом скорректировать /

Чарльз Бретана
источник
489
Если вам трудно представить себе, почему это работает, я сделал пример страницы по адресу silentmatt.com/intersection.html, где вы можете перетаскивать прямоугольники и видеть сравнения.
Мэтью Крамли
4
Вы не думаете, что используете жесткие ограничения? Что делать, если два прямоугольника перекрывают друг друга точно по краю? не должны ли вы рассмотреть <=,> = ??
Навшад Фаррук
6
@MatthewCrumley для A.Y1 <B.Y2 и A.Y2> B.Y1 в вашей ссылке, не следует ли поменять знаки gt & lt?
NikT
15
Мне пришлось поменять местами <и> в двух последних сравнениях, чтобы заставить его работать
DataGreed
17
Нет, ответ правильный, как указано. Он основан на использовании стандартных декартовых координат. Если вы используете другую систему (увеличивая Y сверху вниз), сделайте соответствующие настройки.
Чарльз Бретана
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
источник
15
Самый простой и чистый ответ.
ldog
1
@ e.James Я думаю, что последнее B.heightдолжно бытьA.height
mat_boy
'min' и 'max' являются зарезервированными ключевыми словами в <windows.h>. Вы можете исправить это, выполнив #undef minи #undef max, или используя другие имена параметров.
mchiasson
Если вы интенсивно используете, вы можете обменять valueInRange на#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
Ratata Tata
@Nemo На самом деле проверка xOverlapвыполняется в одном измерении; rectOverlapявляется двухмерным. Его можно расширить до N размеров с помощью цикла.
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;
}
Дэвид Норман
источник
Хороший! Применяя закон де Моргана, получим: r1.x1 <= r2.x2 && r2.x1 <= r1.x2 && r1.y1 <= r2.y2 && r2.y1 <= r1.y2.
Борж,
23

Проще проверить, находится ли прямоугольник полностью вне другого, поэтому, если он

налево...

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

или справа ...

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

или сверху ...

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

или на дне ...

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

второго прямоугольника, он не может столкнуться с ним. Таким образом, чтобы получить функцию, которая возвращает логическое значение, говорящее о столкновении прямоугольников, мы просто объединяем условия с помощью логических ИЛИ и отменяем результат:

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

Чтобы уже получить положительный результат только при касании, мы можем изменить «<» и «>» на «<=» и «> =».

Бьорн Кехель
источник
3
И применить к нему закон де Моргана.
Борж
6

Задайте себе противоположный вопрос: как я могу определить, не пересекаются ли два прямоугольника вообще? Очевидно, прямоугольник A полностью слева от прямоугольника B не пересекается. Кроме того, если А полностью вправо. И точно так же, если A полностью выше B или полностью ниже B. В любом другом случае A и B пересекаются.

В последующем могут быть ошибки, но я довольно уверен в алгоритме:

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
источник
6

Предположим, что вы определили позиции и размеры прямоугольников следующим образом:

введите описание изображения здесь

Моя реализация C ++ выглядит так:

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

Пример вызова функции согласно приведенному выше рисунку:

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

Сравнения внутри ifблока будут выглядеть так:

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
источник
3

Вот как это делается в 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
источник
Обратите внимание, что в C ++ эти тесты на переполнение не будут работать, поскольку целочисленное переполнение со знаком не определено.
Бен Фойгт
2

В этом вопросе вы ссылаетесь на математику, когда прямоугольники находятся под произвольными углами поворота. Однако, если я понимаю немного об углах в вопросе, я понимаю, что все прямоугольники перпендикулярны друг другу.

Общее знание формулы области перекрытия:

Используя пример:

   1 2 3 4 5 6

1 + --- + --- +
   | |   
2 + A + --- + --- +
   | | Б |
3 + + + --- + --- +
   | | | | |
4 + --- + --- + --- + --- + +
               | |
5 + С +
               | |
6 + --- + --- +

1) собрать все координаты х (как левые, так и правые) в список, затем отсортировать и удалить дубликаты

1 3 4 5 6

2) собрать все координаты y (как верхнюю, так и нижнюю) в список, затем отсортировать и удалить дубликаты

1 2 3 4 6

3) создать двумерный массив по количеству промежутков между уникальными координатами x * числу промежутков между уникальными координатами y.

4 * 4

4) закрасить все прямоугольники в эту сетку, увеличивая количество каждой ячейки, в которой она встречается:

   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) Когда вы рисуете прямоугольники, легко перехватывать перекрытия.

Будет
источник
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;
}
Адам Теген
источник
1

Не думайте, что координаты указывают, где находятся пиксели. Думайте о них как о пикселях. Таким образом, площадь прямоугольника 2х2 должна быть 4, а не 9.

bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
               && (A.Bottom >= B.Top || B.Bottom >= A.Top));
Майк Данлавей
источник
1

Самый простой способ

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

Прежде всего, подумайте, что в компьютерах система координат перевернута. Ось X такая же, как в математике, но ось Y увеличивается вниз и уменьшается при движении вверх .. если прямоугольник нарисован из центра. если координаты x1 больше, чем x2 плюс его половина видимости. тогда это означает, что половину они коснутся друг друга. и таким же образом идет вниз + половина его высоты. это столкнется ..

Zar E Ahmer
источник
1

Допустим, два прямоугольника - это прямоугольник A и прямоугольник B. Пусть их центры - это A1 и B1 (координаты A1 и B1 можно легко определить), пусть высоты - это Ha и Hb, ширина - это Wa и Wb, пусть dx - это width (x) расстояние между A1 и B1, а dy - расстояние по высоте (y) между A1 и B1.

Теперь мы можем сказать, что можем сказать, что А и В перекрываются: когда

if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
sachinr
источник
0

Я реализовал версию C #, она легко конвертируется в 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
источник
2
Опытным глазам ясно, что вы имели в виду, что это класс расширения для Rectangle, но вы не предоставили никаких ограничений или кода для этого. Было бы неплохо, если бы вы сделали это или объяснили, что именно так должен использоваться ваш метод, и получите бонусные баллы, если ваши переменные на самом деле имеют достаточно описательные имена для того, чтобы кто-то следовал дальше, чтобы понять их цель / намерение.
tpartee
0

У меня очень простое решение

пусть x1, y1 x2, y2, l1, b1, l2, будут кординаты и их длины и ширины соответственно

рассмотреть условие ((x2

теперь единственный способ перекрытия этих прямоугольников - это если точка, диагональная x1, y1, будет лежать внутри другого прямоугольника или аналогично точке, диагональной x2, y2, будет лежать внутри другого прямоугольника. что именно из вышеприведенного условия подразумевает.

Himanshu
источник
0

А и В два прямоугольника. C быть их покрывающим прямоугольником.

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) 

Он заботится обо всех возможных случаях.

Anwit
источник
0

Это из упражнения 3.28 из книги Введение в программирование на Java - полное издание. Код проверяет, являются ли два прямоугольника одинаковыми, находится ли один внутри другого и находится ли он снаружи другого. Если ни одно из этих условий не выполнено, то два перекрываются.

** 3.28 (Геометрия: два прямоугольника) Напишите программу, которая предлагает пользователю ввести координаты центра x, y, ширину и высоту двух прямоугольников и определяет, находится ли второй прямоугольник внутри первого или перекрывается с первым, как показано на рисунке 3.9. Протестируйте свою программу, чтобы охватить все случаи. Вот примеры прогонов:

Введите x-, y-координаты, ширину и высоту центра r1: 2.5 4 2.5 43 Введите x-, y-координаты, ширину и высоту центра r1: 1,5 5 0,5 3 r2 находится внутри r1

Введите x-, y-координаты, ширину и высоту центра r1: 1 2 3 5.5 Введите x-, y-координаты, ширину и высоту центра r2: 3 4 4.5 5 r2 перекрывает r1

Введите x-, y-координаты, ширину и высоту центра r1: 1 2 3 3 Введите x-, y-координаты, ширину и высоту центра r2: 40 45 3 2 r2 не перекрывает 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
источник
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
источник
0

Для тех из вас, кто использует центральные точки и половинные размеры для своих данных прямоугольника вместо типичных x, y, w, h или x0, y0, x1, x1, вот как вы можете это сделать:

#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
источник
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;
}
Эдвард Карак
источник
0

Если прямоугольники перекрываются, то область перекрытия будет больше нуля. Теперь давайте найдем область перекрытия:

Если они перекрываются, то левый край прямоугольника перекрытия будет max(r1.x1, r2.x1) и правый край будет min(r1.x2, r2.x2). Таким образом, длина наложения будетmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)

Так что площадь будет:

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

Если area = 0тогда они не перекрываются.

Просто не так ли?

Anony
источник
3
Это работает для перекрытия (что является вопросом), но не будет работать для пересечения, так как это не будет работать, если они точно пересекаются в углу.
Ланс Робертс
Я попробовал этот код, и он не работает вообще. Я просто получаю положительные числа, даже если они совсем не пересекаются.
Бретт
@ Бретт: Да, потому что произведение двух отрицательных чисел положительно.
Бен Фойгт
@ BenVoigt, проблема заключалась в том, что функция не возвращала 0, когда не было перекрытия. Мне было очень непонятно с моим комментарием, но да, я только когда-либо получал область> 0 от этой функции.
Бретт
Если вы работаете с числами с плавающей запятой, обычно очень плохая идея использовать вычитания и другие арифметические вещи перед любым сравнением чисел. Особенно если вам нужно сравнить с точным значением - в этом случае ноль. Это работает в теории, но не на практике.
Maja
-1

«Если вы выполняете вычитание координат x или y, соответствующих вершинам двух, стоящих перед каждым прямоугольником, если результаты имеют одинаковый знак, два прямоугольника не перекрывают оси, которые» (извините, я не уверен, что мой перевод правильный )

введите описание изображения здесь

Источник: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html

Мистер джерри
источник
-1

Java-код, чтобы выяснить, соприкасаются ли прямоугольники или перекрывают друг друга

...

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

...

Шришакти Мишра
источник