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

Question

Я пытаюсь написать программу на 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;  

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

Есть предложения?

Answer 1

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

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

(X1 - координата слева, X2 - координата справа, увеличивается слева направо, Y1 - координата сверху, Y2 - координата снизу, увеличивается снизу вверх) ...

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

ПРИМЕЧАНИЕ: ДЛЯ ВСЕХ ТАК ПОЛЬЗОВАТЕЛЕЙ С РЕДАКТОРСКОЙ СИСТЕМОЙ. ПОЖАЛУЙСТА, Хватит возиться с этим.

Скажем, у вас есть Рект А и Рект Б. Доказательство от противного. Любое из четырех условий гарантирует, что перекрытие не может существовать :

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

Итак, условие для Non-Overlap:

Cond1 Or Cond2 Or Cond3 Or Cond4

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

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

слева ...

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

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

Answer 5

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

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

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

Answer 10

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

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