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

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

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

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

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

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

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

Этот ответ должен быть верхним:

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

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

Все просто?