c++ - ¿Determinar si dos rectángulos se superponen entre sí?
algorithm geometry (21)
Estoy intentando escribir un programa en C ++ que toma las siguientes entradas del usuario para construir rectángulos (entre 2 y 5): altura, anchura, x-pos, y-pos. Todos estos rectángulos existirán paralelos al eje x y al eje y, es decir, todos sus bordes tendrán pendientes de 0 o infinito.
He intentado implementar lo que se menciona en this 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 he vinculado correctamente, o si hice exactamente cómo interpretar esto.
¿Alguna sugerencia?
"Si realiza la resta de las coordenadas x o y 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 a los ejes" (lo siento, no estoy seguro de que mi traducción sea correcta) )
Fuente: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
A y B son dos rectángulos. C sea 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.
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));
}
Digamos que los dos rectángulos son el rectángulo A y el rectángulo B. Sean los centros A1 y B1 (las coordenadas de A1 y B1 se pueden encontrar fácilmente), las alturas Ha y Hb, el ancho Wa y Wb, sea dx 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 que A y B se superponen: cuando
if (! (dx> Wa + Wb) ||! (dy> Ha + Hb)) devuelve verdadero
En la pregunta, se vincula a las matemáticas para cuando los rectángulos están en ángulos de rotación arbitrarios. Sin embargo, si entiendo la parte de los ángulos de la pregunta, interpreto que todos los rectángulos son perpendiculares entre sí.
Un general que conoce 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) recopilar todas las coordenadas x (izquierda y derecha) en una lista, luego ordenarlas y eliminar duplicados
1 3 4 5 6
2) recopilar todas las coordenadas y (tanto arriba como abajo) en una lista, luego ordenarlas y eliminar 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, incrementando el conteo de cada celda en la que aparece:
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 rectángulos, es fácil interceptar las superposiciones.
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 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, no puede chocar con él. Entonces, para tener una función que devuelva un dicho booleano mientras los rectángulos colisionan, simplemente combinamos las condiciones mediante 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 "<" y ">" por "<=" y "> =".
Esta respuesta debe ser la respuesta principal:
si los rectángulos se superponen, el área de superposición será mayor que cero. Ahora encontremos el área de superposición:
si se superponen, el borde izquierdo de superposición será el máximo (r1.x1, r2.x1) y el borde derecho será mínimo (r1.x2, r2.x2). por lo tanto, la longitud del solapamiento 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 es?
Esto es del ejercicio 3.28 del libro Introduction to Java Programming- Comprehensive Edition. El código comprueba si los dos rectángulos son autenticados, si uno está dentro del otro y si uno está fuera del otro. Si ninguna de estas condiciones se cumple, los dos se superponen.
** 3.28 (Geometría: dos rectángulos) Escriba un programa que indique al usuario que ingrese las coordenadas x, y del centro, el ancho y la altura de los dos rectángulos y que determine si el segundo rectángulo está dentro del primero o se superpone al primero, como se muestra en la Figura 3.9. Pon a prueba tu programa para cubrir todos los casos. Aquí están las ejecuciones de la muestra:
Ingrese las coordenadas x, centro de r1, anchura y altura: 2.5 4 2.5 43 Ingrese las coordenadas x, centro de r2, anchura y altura: 1.5 5 0.5 3 r2 está dentro de r1
Ingrese las coordenadas x, centro de r1, ancho y altura: 1 2 3 5.5 Ingrese las coordenadas x, y de centro de r2, ancho y altura: 3 4 4.5 5 r2 superpone r1
Ingrese las coordenadas x, centro de r1, anchura y altura: 1 2 3 3 Ingrese las coordenadas x, centro de r2, anchura y altura: 40 45 3 2 r2 no se superponen 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");
}
}
}
Hágase la pregunta opuesta: ¿Cómo puedo determinar si dos rectángulos no se intersecan en absoluto? Obviamente, un rectángulo A completamente a la izquierda del rectángulo B no se interseca. 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 acerca 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);
}
He implementado una versión de 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;
}
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 el mismo que en matemáticas, pero el eje y aumenta hacia abajo y disminuye al ir hacia arriba ... si el rectángulo se dibuja desde el centro. si las coordenadas x1 son mayores que x2 más su mitad de ancho. entonces significa que al ir a la mitad se tocarán. y de la misma manera bajando + la mitad de su altura. se chocará ..
No pienses que las coordenadas indican dónde están los píxeles. Piense en ellos como entre los píxeles. De esa manera, el área de un rectángulo de 2x2 debe ser 4, no 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
Para aquellos de ustedes que usan puntos centrales y medias tallas para sus datos rectangulares, en lugar de los típicos x, y, w, h, o x0, y0, x1, x1, aquí le explicamos cómo puede 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));
}
Supongamos que ha definido las posiciones y tamaños de los rectángulos de la siguiente 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;
}
Un ejemplo de llamada a la función de acuerdo con la figura anterior:
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 ))
Tengo una solución muy fácil.
sean x1, y1 x2, y2, l1, b1, l2, sean coordenadas y longitudes y anchuras de ellas respectivamente
considerar la condición ((x2
ahora la única forma en que este rectángulo se superpondrá 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.
Código Java para averiguar si los rectángulos se están contactando o superponiendo 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;
}
}
}
}
...
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;
}
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
o, utilizando coordenadas cartesianas.
(Con X1 siendo la coordenada a la izquierda, X2 siendo la coordenada a la derecha, aumentando de izquierda a derecha y Y1 siendo la coordenada superior, y Y2 siendo la coordenada inferior, aumentando de abajo a arriba)
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
NOTA: A TODOS LOS USUARIOS CON AUTORIDAD DE EDICIÓN. POR FAVOR, DEJEN DE PODER CON ESTO.
Digamos que tienes Rect A, y Rect B. La prueba es por contradicción. Cualquiera de las cuatro condiciones garantiza que no puede existir superposición :
- Cond1. Si el borde izquierdo de A está a la derecha del borde derecho de B, - A es totalmente a la derecha de B
- Cond2. Si el borde derecho de A está a la izquierda del borde izquierdo de B, - A es 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
Por lo tanto, la condición para la no superposición es
Cond1 Or Cond2 Or Cond3 Or Cond4
Por lo tanto, una condición suficiente para la superposición es lo contrario.
Not (Cond1 Or Cond2 Or Cond3 Or 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
así que usando De Morgan, tenemos
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
Esto es equivalente a:
- El borde izquierdo de A a la izquierda del borde derecho de B, [
RectA.Left < RectB.Right], y - El borde derecho de A a la derecha del borde izquierdo de B, [
RectA.Right > RectB.Left], y - La parte superior de A sobre la parte inferior de B, [
RectA.Top > RectB.Bottom], y - Parte inferior de A debajo de la parte superior de B [
RectA.Bottom < RectB.Top]
Nota 1 : Es bastante obvio que este mismo principio puede extenderse a cualquier número de dimensiones.
Nota 2 : También debería ser bastante obvio contar las superposiciones de solo un píxel, cambiar < y / o > en ese límite a un <= 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 a arriba). Obviamente, cuando un sistema informático puede mecanizar las coordenadas de la pantalla de manera diferente (por ejemplo, aumentar la Y de arriba a abajo o X de derecha a izquierda), la sintaxis deberá ajustarse en consecuencia /
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
{
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;
}
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;
}