Determine se dois retângulos se sobrepõem?

Eu estou tentando escrever um programa C ++ que leva as seguintes entradas do usuário para construir retângulos (entre 2 e 5): altura, largura, x-pos, y-pos. Todos esses retângulos existirão paralelos aos eixos xe y, ou seja, todas as suas arestas terão inclinações de 0 ou infinito.

Eu tentei implementar o que é mencionado nesta pergunta, mas não estou tendo muita sorte.

Minha implementação atual faz o seguinte:

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

No entanto, não tenho certeza se (a) implementei o algoritmo ao qual vinculei corretamente, ou se fiz exatamente como interpretar isso?

Alguma sugestão?

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

ou, usando coordenadas cartesianas

(Com X1 sendo coordenado à esquerda, X2 sendo coordenado à direita , aumentando da esquerda para a direita e Y1 sendo a coordenação superior e Y2 sendo a coordenação inferior, aumentando de baixo para cima - se não é assim que seu sistema de coordenadas [por exemplo, a maioria dos computadores tem o Direção Y invertida], troque as comparações abaixo ) ...

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

Digamos que você tenha o Reto A e o Reto B. A prova é por contradição. Qualquer uma das quatro condições garante que nenhuma sobreposição possa existir :

• Cond1. Se a borda esquerda de A estiver à direita da borda direita de B, - então A estará totalmente à direita de B
• Cond2. Se a borda direita de A estiver à esquerda da borda esquerda de B, - então A estará totalmente à esquerda de B
• Cond3. Se a borda superior de A estiver abaixo da borda inferior de B, - então A estará totalmente abaixo de B
• Cond4. Se a borda inferior de A estiver acima da borda superior de B, - então A estará totalmente acima de B

Portanto, a condição para não sobreposição é

NÃO Sobreposição => Cond1 ou Cond2 ou Cond3 ou Cond4

Portanto, uma condição suficiente para Sobreposição é o oposto.

Sobreposição => NÃO (Cond1 ou Cond2 ou Cond3 ou Cond4)

A lei de De Morgan diz que
Not (A or B or C or D)é o mesmo que Not A And Not B And Not C And Not D
usar De Morgan, temos

Não Cond1 e não Cond2 e não Cond3 e não Cond4

Isso é equivalente a:

• Borda esquerda de A à esquerda da borda direita de B, [ RectA.Left < RectB.Right] e
• A borda direita de A para a direita da borda esquerda de B, [ RectA.Right > RectB.Left] e
• O topo de A acima do fundo de B, [ RectA.Top > RectB.Bottom] e
• Parte inferior de A abaixo da parte superior de B [ RectA.Bottom < RectB.Top]

Nota 1 : É bastante óbvio que esse mesmo princípio pode ser estendido a qualquer número de dimensões.
Nota 2 : também deve ser bastante óbvio contar sobreposições de apenas um pixel, alterar o <e / ou o >limite desse para a <=ou a >=.
Nota 3 : Essa resposta, ao utilizar coordenadas cartesianas (X, Y), é baseada em coordenadas cartesianas algébricas padrão (x aumenta da esquerda para a direita e Y aumenta de baixo para cima). Obviamente, onde um sistema de computador pode mecanizar as coordenadas da tela de maneira diferente (por exemplo, aumentando Y de cima para baixo ou X Da direita para a esquerda), a sintaxe precisará ser ajustada de acordo /

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

É mais fácil verificar se um retângulo está completamente fora do outro, portanto, se é

à esquerda...

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

ou à direita ...

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

ou por cima ...

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

ou no fundo ...

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

do segundo retângulo, ele não pode colidir com ele. Portanto, para ter uma função que retorna um ditado booleano quando os retângulos colidem, simplesmente combinamos as condições por ORs lógicos e negamos o 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);
}

Para já receber um resultado positivo ao tocar apenas, podemos alterar o "<" e ">" por "<=" e "> =".

Faça a si mesmo a pergunta oposta: como posso determinar se dois retângulos não se cruzam? Obviamente, um retângulo A completamente à esquerda do retângulo B não se cruza. Além disso, se A estiver completamente à direita. E da mesma forma, se A estiver completamente acima de B ou completamente abaixo de B. Em qualquer outro caso, A e B se cruzam.

O que se segue pode ter erros, mas estou bastante confiante sobre o 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);
}

Suponha que você definiu as posições e tamanhos dos retângulos assim:

Minha implementação em C ++ é assim:

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

Um exemplo de chamada de função de acordo com a figura fornecida acima:

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

As comparações dentro do ifbloco serão parecidas abaixo:

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

Veja como isso é feito na API 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));
}

Na pergunta, você vincula a matemática para quando os retângulos estão em ângulos arbitrários de rotação. Se eu entendo um pouco sobre os ângulos da pergunta, interpreto que todos os retângulos são perpendiculares um ao outro.

Um conhecimento geral da área da fórmula de sobreposição é:

Usando o exemplo:

   1 2 3 4 5 6

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

1) colete todas as coordenadas x (esquerda e direita) em uma lista, classifique-a e remova duplicatas

1 3 4 5 6

2) colete todas as coordenadas y (superior e inferior) em uma lista, classifique-a e remova as duplicatas

1 2 3 4 6

3) crie uma matriz 2D pelo número de intervalos entre as coordenadas x únicas * número de intervalos entre as coordenadas y exclusivas.

4 * 4

4) pinte todos os retângulos nessa grade, incrementando a contagem de cada célula em que ocorre:

   1 3 4 5 6

1 + --- +
   | 1 | 0 0 0
2 + --- + --- + --- +
   | 1 | 1 | 1 | 0 0
3 + --- + --- + --- + --- +
   | 1 | 1 | 2 1 |
4 + --- + --- + --- + --- +
     0 0 1 | 1 |
6 + --- + --- +

5) Ao pintar os retângulos, é fácil interceptar as sobreposições.

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

Não pense nas coordenadas como indicando onde os pixels estão. Pense neles como estando entre os pixels. Dessa forma, a área de um retângulo 2x2 deve ser 4, não 9.

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

A maneira mais fácil é

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

Antes de tudo, lembre-se de que, nos computadores, o sistema de coordenadas está de cabeça para baixo. o eixo x é igual ao da matemática, mas o eixo y aumenta para baixo e diminui ao subir .. se o retângulo for desenhado do centro. se as coordenadas x1 forem maiores que x2 mais sua metade da largura. então significa que metade deles se tocarão. e da mesma maneira descendo + metade da sua altura. vai colidir ..

Digamos que os dois retângulos sejam retângulo A e retângulo B. Deixe seus centros serem A1 e B1 (as coordenadas de A1 e B1 podem ser facilmente encontradas), deixe as alturas Ha e Hb, largura seja Wa e Wb, seja dx o largura (x) distância entre A1 e B1 e dy é a altura (y) da distância entre A1 e B1.

Agora podemos dizer que podemos dizer que A e B se sobrepõem: quando

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

Eu implementei uma versão C #, ela é facilmente convertida em 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;
}

Eu tenho uma solução muito fácil

sejam x1, y1 x2, y2, l1, b1, l2, sejam cordinados e comprimentos e larguras deles respectivamente

considere a condição ((x2

Agora, a única maneira de sobrepor esse retângulo é se o ponto diagonal de x1, y1 estiver dentro do outro retângulo ou, da mesma forma, o ponto diagonal de x2, y2 estiver dentro do outro retângulo. que é exatamente a condição acima implica.

A e B são dois retângulos. C seja seu retâ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) 

Ele cuida de todos os casos possíveis.

Isso é do exercício 3.28 do livro Introduction to Java Programming- Comprehensive Edition. O código testa se os dois retângulos são idênticos, se um está dentro do outro e se um está fora do outro. Se nenhuma dessas condições for atendida, as duas se sobrepõem.

** 3,28 (Geometria: dois retângulos) Escreva um programa que solicite ao usuário que insira as coordenadas x, y, largura e altura centrais de dois retângulos e determine se o segundo retângulo está dentro do primeiro ou se sobrepõe ao primeiro, como mostra a Figura 3.9. Teste seu programa para cobrir todos os casos. Aqui estão os exemplos de execuções:

Digite as coordenadas x, y, largura e altura do centro de r1: 2,5 4 2,5 43 Digite as coordenadas x, y, largura e altura do centro de r2: 1,5 5 0,5 3 r2 está dentro de r1

Digite o centro de r1 - coordenadas x, y, largura e altura: 1 2 3 5.5 Digite o centro de r2 - coordenadas x, largura e altura: 3 4 4.5 5 r2 sobrepõe r1

Digite o centro de r1 - coordenadas x, y, largura e altura: 1 2 3 3 Digite o centro de r1 - coordenadas x, largura e altura: 40 45 3 2 r2 não se sobrepõe a 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 aqueles que usam pontos centrais e meios tamanhos para seus dados retangulares, em vez dos x, y, w, h ou x0, y0, x1, x1 típicos, veja como fazê-lo:

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

Se os retângulos se sobrepuserem, a área de sobreposição será maior que zero. Agora vamos encontrar a área de sobreposição:

Se eles se sobrepuserem, a borda esquerda de overlap-rect será a max(r1.x1, r2.x1)borda direita e serámin(r1.x2, r2.x2) . Portanto, o comprimento da sobreposição serámin(r1.x2, r2.x2) - max(r1.x1, r2.x1)

Então a área será:

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

Se area = 0então eles não se sobrepõem.

Simples, não é?

"Se você executar as subtrações x ou y coordenadas correspondentes aos vértices dos dois voltados para cada retângulo, se os resultados forem o mesmo sinal, os dois retângulos não se sobrepõem aos eixos que" (desculpe, não sei se minha tradução está correta) )

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

Código Java para descobrir se os retângulos estão em contato ou se sobrepõem

...

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

...