Determinar si dos rectángulos se superponen entre sí?

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

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

Es más fácil verificar si un rectángulo está completamente fuera del otro, por lo que si es

A la izquierda...

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

O a la derecha...

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

O arriba...

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

O en la parte inferior...

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

Del segundo rectángulo, no puede chocar con él. Así que para tener una función que devuelve un booleano diciendo que los rectángulos colisionan, simplemente combinamos las condiciones por ORS lógicos y negamos el 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);
}

A ya recibir un resultado positivo al tocar solo, podemos cambiar el " " por "=".

Hágase la pregunta opuesta: ¿Cómo puedo determinar si dos rectángulos no se cruzan en absoluto? Obviamente, un rectángulo A completamente a la izquierda del rectángulo B no se cruza. También si A está completamente a la derecha. Y del mismo modo si A está completamente por encima de B o completamente por debajo de B. En cualquier otro caso A y B se cruzan.

Lo que sigue puede tener errores, pero estoy bastante seguro del 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);
}

Supongamos que ha definido las posiciones y tamaños de los rectángulos de esta manera:

Mi implementación de C++ es así:

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

Una llamada de función de ejemplo de acuerdo con la figura dada arriba:

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

Las comparaciones dentro del bloque if se verán como a continuación:

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

Así es como se hace en la API de 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));
}

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

En la pregunta, se enlaza a las matemáticas para cuando los rectángulos están en ángulos arbitrarios de rotación. Si entiendo el pedacito sobre ángulos en la pregunta sin embargo, interpreto que todos los rectángulos son perpendiculares el uno al otro.

Una fórmula general para conocer el área de superposición es:

Usando el ejemplo:

   1   2   3   4   5   6

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

1) recoge todas las coordenadas x (tanto a la izquierda como a la derecha) en una lista, luego ordénala y elimina los duplicados

1 3 4 5 6

2) recoger todas las coordenadas y (tanto superior como inferior) en una lista, luego ordénela y elimine duplicados

1 2 3 4 6

3) cree una matriz 2D por número de espacios entre las coordenadas x únicas * número de espacios entre las coordenadas y únicas.

4 * 4

4) pinte todos los rectángulos en esta cuadrícula, aumentando el recuento de cada celda sobre la que se produce:

   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) Mientras pintas los rectángulos, es fácil interceptar las superposiciones.

Digamos que los dos rectángulos son el rectángulo A y el rectángulo B. Que los centros sean A1 y B1 (las coordenadas de A1 y B1 se pueden encontrar fácilmente), que las alturas sean Ha y Hb, que el ancho sea Wa y Wb, que dx sea la distancia de ancho(x) entre A1 y B1 y dy sea la distancia de altura(y) entre A1 y B1.
Ahora podemos decir que podemos decir que A y B se superponen: cuando

if(!(dx > Wa + Wb)//!(dy > Ha+Hb)) devuelve true

La forma más fácil es

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

En primer lugar, piense que en las computadoras el sistema de coordenadas está al revés. el eje x es igual que en matemáticas, pero el eje y aumenta hacia abajo y disminuye al ir hacia arriba.. si rectángulo se dibujan desde el centro. si x1 coordenadas es mayor que x2 más su su mitad de widht. entonces significa ir a la mitad se tocarán. y de la misma manera va hacia abajo + la mitad de su altura. chocará..

He implementado una versión en C#, se convierte fácilmente a 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;
}

No piense que las coordenadas indican dónde están los píxeles. Piensa en ellos como si estuvieran entre los píxeles. De esa manera, el área de un rectángulo 2x2 debe ser 4, no 9.

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

Tengo una solución muy fácil

Sean cordinados x1,y1 x2,y2 ,l1,b1,l2 y longitudes y panes de ellos respectivamente

Considere la condición ((x2

Ahora la única forma en que estos rectángulos se superpondrán es si el punto diagonal a x1,y1 estará dentro del otro rectángulo o de manera similar el punto diagonal a x2,y2 estará dentro del otro rectángulo. que es exactamente la condición anterior implica.

A y B son dos rectángulos. C ser su rectá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) 

Se ocupa de todos los casos posibles.

Esto es del ejercicio 3.28 del libro Introduction to Java Programming - Comprehensive Edition. El código prueba si los dos rectángulos son indentículos, si uno está dentro del otro y si uno está fuera del otro. Si no se cumple ninguna de estas condiciones, entonces las dos se superponen.

* * 3.28 (Geometría: dos rectángulos) Escriba un programa que le pida al usuario que ingrese centro x -, y-coordenadas, anchura, y altura de dos rectángulos y determina si el segundo rectángulo es dentro de la primera o se superpone con la primera, como se muestra en la Figura 3.9. Pruebe su programa para cubrir todos los casos. Aquí están las ejecuciones de ejemplo:

Ingrese las coordenadas x, y, ancho y alto del centro de r1: 2.5 4 2.5 43 Introduzca las coordenadas x, y, anchura y altura del centro de r2: 1.5 5 0.5 3 r2 está dentro de r1

Ingrese las coordenadas x, y, ancho y alto del centro de r1: 1 2 3 5.5 Introduzca las coordenadas x, y, anchura y altura del centro de r2: 3 4 4.5 5 r2 se superpone a r1

Ingrese el centro x de r1-, coordenadas y, anchura y altura: 1 2 3 3 Introduzca las coordenadas x, y, anchura y altura del centro de r2: 40 45 3 2 r2 no se superpone 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;
}

Para aquellos de ustedes que están usando puntos centrales y tamaños medios para sus datos rectangulares, en lugar de los típicos x,y,w,h, o x0,y0,x1,x1, así es como pueden hacerlo:

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

"Si realiza resta x o y coordenadas correspondientes a los vértices de los dos frente a cada rectángulo, si los resultados son el mismo signo, los dos rectángulos no se superponen ejes que" (lo siento, no estoy seguro de que mi traducción es correcta)

Fuente: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html

Código Java para averiguar si los rectángulos están en contacto o se superponen entre sí
...

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

...

Esta respuesta debe ser la respuesta principal:

Si los rectángulos se superponen entonces el área de superposición será mayor que cero. Ahora vamos a encontrar el área de superposición:

Si se superponen entonces el borde izquierdo de overlap-rect será el max(r1.x1, r2.x1) y el borde derecho será min (r1.x2, r2.x2). así que la longitud de la superposición será min (r1.x2, r2.x2) - max (r1.x1, r2.x1)

Así que el área será: área = (max(r1.x1, r2.x1) - min (r1.x2, r2.x2)) * (max (r1.y1, r2.y1) - min (r1.y2, r2.y2))

Si área = 0 entonces no se superponen. Simple, ¿no?