Determine si dos rectangularjs se superponen entre sí?

Estoy intentando escribir un progtwig C ++ que toma las siguientes entradas del usuario para construir rectangularjs (entre 2 y 5): alto, ancho, x-pos, y-pos. Todos estos rectangularjs existirán paralelos a los ejes x e y, es decir, todos sus bordes tendrán pendientes de 0 o infinito.

Intenté implementar lo que se menciona en esta pregunta, pero no estoy teniendo mucha suerte.

Mi implementación actual hace lo siguiente:

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

Sin embargo, no estoy muy seguro de si (a) he implementado el algoritmo al que me he vinculado correctamente, o si hice exactamente cómo interpretar esto.

¿Alguna sugerencia?

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

o, usando coordenadas cartesianas

(Con X1 quedando coord, X2 siendo coord derecha, aumentando de izquierda a derecha e Y1 siendo Arriba coord, y Y2 siendo Coord inferior, aumentando de abajo hacia arriba) ...

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

NOTA: PARA TODOS LOS USUARIOS CON EDITAR AUTORIDAD. POR FAVOR, DEJE DE MOSTRAR CON ESTO.

Digamos que tiene Rect A, y Rect B. La prueba es por contradicción. Cualquiera de las cuatro condiciones garantiza que no puede haber superposición :

  • Cond1. Si el borde izquierdo de A está a la derecha del borde derecho de B, - entonces A es Totalmente a la derecha de B
  • Cond2. Si el borde derecho de A está a la izquierda del borde izquierdo de la B, - entonces A está totalmente a la izquierda de B
  • Cond3. Si el borde superior de A está por debajo del borde inferior de B, - entonces A está Totalmente por debajo de B
  • Cond4. Si el borde inferior de A está por encima del borde superior de B, entonces A está Totalmente por encima de B

Entonces, la condición para no superposición es

  Cond1 o Cond2 o Cond3 o Cond4 

Por lo tanto, una condición suficiente para Overlap es lo opuesto.

  Not (Cond1 o Cond2 o Cond3 o Cond4) 

La ley de De Morgan dice
Not (A or B or C or D) es lo mismo que Not A And Not B And Not C And Not D
entonces, usando De Morgan, tenemos

  No Cond1 Y No Cond2 Y No Cond3 Y No Cond4 

Esto es equivalente a:

  • A Left Edge a la izquierda del borde derecho de B, [ RectA.Left < RectB.Right ], y
  • El borde derecho de A hacia la derecha del borde izquierdo de B, [ RectA.Right > RectB.Left ], y
  • La parte superior de A arriba de la parte inferior de B, [ RectA.Top > RectB.Bottom ], y
  • La parte inferior de A debajo de la parte superior de B [ RectA.Bottom < RectB.Top ]

Nota 1 : Es bastante obvio que este mismo principio se puede extender a cualquier cantidad de dimensiones.
Nota 2 : También debería ser bastante obvio contar superposiciones de solo un píxel, cambiar < y / o > en ese límite a a <= o a >= .
Nota 3 : Esta respuesta, cuando se utilizan coordenadas cartesianas (X, Y) se basa en coordenadas cartesianas algebraicas estándar (x aumenta de izquierda a derecha e Y aumenta de abajo arriba). Obviamente, cuando un sistema de computadora pueda mecanizar coordenadas de pantalla de manera diferente (por ejemplo, boost Y de arriba a abajo, o X de derecha a izquierda), la syntax deberá ajustarse en consecuencia /

 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(Ax, Bx, Bx + B.width) || valueInRange(Bx, Ax, Ax + A.width); bool yOverlap = valueInRange(Ay, By, By + B.height) || valueInRange(By, Ay, Ay + 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 comprobar 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 en la parte superior ...

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

o en la parte inferior ...

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

del segundo rectángulo, posiblemente no puede colisionar con él. Entonces, para tener una función que devuelve un booleano que dice que los rectangularjs colisionan, simplemente combinamos las condiciones por OR lógicas 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); } 

Para recibir un resultado positivo al tocar solo, podemos cambiar el "<" y ">" por "<=" y "> =".

Hágase la pregunta opuesta: ¿cómo puedo determinar si dos rectangularjs 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 de manera similar 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 sobre el algoritmo:

 struct Rectangle { int x; int y; int width; int height; }; bool is_left_of(Rectangle const & a, Rectangle const & b) { if (ax + a.width <= bx) 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 rectangularjs de esta manera:

enter image description here

Mi implementación 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 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 = rx; int ry = ry; 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 vincula a las matemáticas para cuando los rectangularjs están en angularjs de rotación arbitrarios. Sin embargo, si entiendo un poco acerca de los angularjs en la pregunta, interpreto que todos los rectangularjs son perpendiculares entre sí.

Un general que sabe que el área de la fórmula de superposición es:

Usando el ejemplo:

  1 2 3 4 5 6

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

1) recopile todas las coordenadas x (izquierda y derecha) en una lista, luego ordénelas y elimine duplicados

  1 3 4 5 6 

2) recoger todas las coordenadas y (arriba y abajo) en una lista, luego ordenarlas y eliminar duplicados

  1 2 3 4 6 

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

  4 * 4 

4) pintar todos los rectangularjs en esta cuadrícula, incrementando el conteo de cada celda sobre la que ocurre:

    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) Al pintar los rectangularjs, es fácil interceptar las superposiciones.

Digamos que los dos rectangularjs son el rectángulo A y el rectángulo B. Deje que los centros sean A1 y B1 (las coordenadas de A1 y B1 pueden ser fácilmente descubiertas), que las alturas sean Ha y Hb, el ancho sea Wa y Wb, que dx sea el la distancia de ancho (x) entre A1 y B1 y dy es la distancia de altura (y) entre A1 y B1.
Ahora podemos decir que podemos decir superposición A y B: cuando

if (! (dx> Wa + Wb) ||! (dy> Ha + Hb)) devuelve verdadero

La manera 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); } 

antes que nada ten en cuenta que en las computadoras el sistema de coordenadas está boca abajo. El eje x es el mismo que en matemáticas, pero el eje y aumenta hacia abajo y disminuye al ir hacia arriba ... si el rectángulo se extrae del centro. si las coordenadas x1 son mayores que x2 más su mitad de ancho. entonces significa ir a la mitad, se tocarán el uno al otro. y de la misma manera yendo hacia abajo + la mitad de su altura. colisionará ...

Implementé una versión de C #, se convirtió 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 se encuentran los píxeles. Piense en ellos como entre los píxeles. De esta forma, el área de un rectángulo de 2×2 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

dejar x1, y1 x2, y2, l1, b1, l2, ser cordinates y longitudes y amplitudes de ellos respectivamente

considerar la condición ((x2

ahora la única forma en que se superpondrán estos rectangularjs es si el punto diagonal a x1, y1 estará dentro del otro rectángulo o similarmente 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 rectangularjs. 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) 

Cuida 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 rectangularjs están indenticle, si uno está dentro del otro y si uno está fuera del otro. Si no se cumple ninguna de estas condiciones, las dos se superponen.

** 3.28 (Geometría: dos rectangularjs) Escriba un progtwig que solicite al usuario ingresar el centro x-, coordenadas y, ancho y alto de dos rectangularjs y determine si el segundo rectángulo está dentro del primero o se superpone con el primero, como se muestra en la Figura 3.9. Pon a prueba tu progtwig para cubrir todos los casos. Estas son las ejecuciones de muestra:

Ingrese el centro de r1 coordenadas x, y, ancho y alto: 2.5 4 2.5 43 Ingrese el centro de r2 coordenadas x, y, ancho y alto: 1.5 5 0.5 3 r2 está dentro de r1

Ingrese las coordenadas x, y, centrales, ancho y alto de r1: 1 2 3 5.5 Ingrese las coordenadas x, y y, ancho y alto de r2: 3 4 4.5 5 r2 se superpone a r1

Ingrese el centro x las coordenadas x, y, el ancho y la altura: 1 2 3 3 Ingrese el centro de r2 x, y, coordenadas, ancho y alto: 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 utilizando puntos centrales y la mitad de tamaños para sus datos rectangulares, en lugar de los típicos x, y, w, h, o x0, y0, x1, x1, así es cómo pueden hacerlo:

 #include  // 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 la resta x o y coordenadas correspondientes a los vértices de los dos frente a cada rectángulo, si los resultados son del mismo signo, los dos rectangularjs no se superponen a los ejes que” (lo siento, no estoy seguro de que mi traducción sea correcta )

enter image description here

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

Código de Java para averiguar si los rectangularjs están contactando o superponiéndose 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 debería ser la mejor respuesta:

si los rectangularjs se superponen, el área de superposición será mayor que cero. Ahora busquemos el área de superposición:

si se superponen, entonces el borde izquierdo de la superposición-rect será el máximo (r1.x1, r2.x1) y el borde derecho será min (r1.x2, r2.x2). por lo que la longitud de la superposición será mínima (r1.x2, r2.x2) -max (r1.x1, r2.x1)

por lo que el área será: area = (max (r1.x1, r2.x1) – min (r1.x2, r2.x2)) * (max (r1.y1, r2.y1) – min (r1.y2, r2.y2))

si area = 0 entonces no se superponen. Simple, ¿no?