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

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. Если правый край A находится слева от левого края B, - тогда A находится полностью слева от B
• Cond3. Если верхний край A ниже нижнего края B, - тогда A полностью ниже B
• Cond4. Если нижний край A выше верхнего края B, - тогда A полностью выше B

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

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

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

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

Закон Де Моргана гласит:
Not (A or B or C or D) такой же, как Not A And Not B And Not C And Not D
поэтому, используя Де Моргана, мы имеем

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

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

• Левый край A слева от правого края B, [RectA.Left < RectB.Right] и
• Правый край A справа от левого края B, [RectA.Right > RectB.Left], и
• Верхняя часть A выше нижней части B, [RectA.Top > RectB.Bottom] и
• Внизу A ниже вершины B [RectA.Bottom < RectB.Top]

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

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

Я реализовал версию на 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;
}

Задайте себе противоположный вопрос: как определить, не пересекаются ли два прямоугольника вообще? Очевидно, что прямоугольник A полностью левее прямоугольника B не пересекается. Также, если A полностью вправо. И аналогично, если 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);
}

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

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

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

На примере:

   1   2   3   4   5   6

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

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

1 3 4 5 6

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

1 2 3 4 6

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

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

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

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

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

Если они перекрываются, то левый край перекрывающегося прямоугольника будет 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, то они не перекрываются.

Просто не правда ли?

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

налево...

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

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

Вот как это делается в 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));
}

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

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

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

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

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

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

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

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

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

A и B - два прямоугольника. 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) 

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

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

/**
 * 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 плюс его половина ширины. тогда это означает, что, пройдя половину, они коснутся друг друга. и таким же образом спускаемся вниз + половина его высоты. он столкнется ..

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

Моя реализация на 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    ))

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

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

Введите координаты x, y, ширину и высоту центра r1: 2,5 4 2,5 43 Введите координаты x, y, ширину и высоту центра r2: 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");
    }

}
}

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

Код 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;
            }
        }
    }
}

...

Для тех из вас, кто использует центральные точки и половинные размеры для своих данных прямоугольника вместо типичных 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)); 
}

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

Это очень быстрый способ проверить с помощью C++, перекрываются ли два прямоугольника:

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
    && std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

Он работает, вычисляя левую и правую границы пересекающегося прямоугольника, а затем сравнивая их: если правая граница равна или меньше левой границы, это означает, что пересечение пусто и, следовательно, прямоугольники не перекрываются; в противном случае он пробует еще раз с верхней и нижней границами.

В чем преимущество этого метода перед традиционной альтернативой 4 сравнений? Речь идет о том, как устроены современные процессоры. У них есть так называемое предсказание ветвления, которое хорошо работает, когда результат сравнения всегда один и тот же, но в противном случае имеет огромное снижение производительности. Однако в отсутствие инструкций ветвления ЦП работает достаточно хорошо. Вычисляя границы пересечения вместо двух отдельных проверок для каждой оси, мы сохраняем две ветви, по одной на пару.

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

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

• Если вы ожидаете, что отмеченные прямоугольники будут располагаться преимущественно слева или справа друг от друга, то описанный выше метод работает лучше всего. Это, вероятно, так, например, когда вы используете пересечение прямоугольника для проверки столкновений для игры, где игровые объекты преимущественно распределены по горизонтали (например, в игре, подобной SuperMarioBros).
• Если вы ожидаете, что отмеченные прямоугольники будут располагаться преимущественно сверху или снизу друг друга, например в игре типа «Ледяная башня» проверка сначала сверху / снизу, а затем слева / справа будет, вероятно, быстрее:

return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom)
    && std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);

• Однако, если вероятность пересечения близка к вероятности непересечения, лучше иметь альтернативу без ответвлений:

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
     & std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

(Обратите внимание на замену && на одиночный &)