Determinar si dos rectángulos se superponen unos a otros?
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy tratando de escribir un programa de C++ que tiene las siguientes entradas del usuario para la construcción de rectángulos (entre 2 y 5):la altura, el ancho, x-pos, y-pos.Todos estos rectángulos existirá paralelo a la x y el eje y, esto es, todos sus bordes se han pendientes de 0 o infinito.
He tratado de poner en práctica lo que se menciona en este pregunta, pero yo no soy de tener mucha suerte.
Mi aplicació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 he enlazado correctamente, o si hice exactamente cómo interpretar esto?
Alguna sugerencia?
Solución
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
o, utilizando coordenadas Cartesianas
(Con X1 ser de izquierda coord, X2 derecho de ser coord, aumenta de izquierda a derecha y Y1 ser Superior coord, y Y2 ser Inferior coord, aumenta de abajo a arriba) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
NOTA:A TODOS, ASÍ QUE LOS USUARIOS EDITAR AUTORIDAD.POR FAVOR, DEJAR DE TOCAR EL VIOLÍN CON ESTO.
Dicen que usted tiene Un Rect, y Rect B.Es la prueba por contradicción.Cualquiera de las cuatro condiciones garantiza que no puede existir solapamiento:
- Cond1.Si el borde izquierdo está a la derecha de la B a la derecha, - entonces es Totalmente a la derecha De B
- Cond2.Si el borde de la derecha está a la izquierda de la B del borde izquierdo, - entonces es Totalmente a la izquierda De B
- Cond3.Si el borde superior está por debajo de B, el borde inferior del - entonces es Totalmente inferior a B
- Cond4.Si el borde inferior está por encima de B del borde superior, - entonces está Totalmente por encima de B
Así, la condición para que No se superponga
Cond1 Or Cond2 Or Cond3 Or Cond4
Por lo tanto, una condición suficiente para la Superposición es la opuesta.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
De Morgan, la ley dice
Not (A or B or C or D) es el mismo Not A And Not B And Not C And Not D
así que el uso de De Morgan, tenemos
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
Esto es equivalente a:
- Un Borde Izquierdo a la izquierda de B en el borde derecho, [
RectA.Left < RectB.Right], y - Un derecho del borde a la derecha de B del borde izquierdo, [
RectA.Right > RectB.Left], y - Una de la parte superior por encima de B en la parte inferior, [
RectA.Top > RectB.Bottom], y - Una de la parte inferior por debajo de B de la parte Superior [
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 para contar la superposición de sólo un píxel, cambiar el < y/o la > en la frontera a un <= o un >=.
Nota 3:Esta respuesta, cuando la utilización de coordenadas Cartesianas (X, Y) está basado en el estándar algebraicas coordenadas Cartesianas (x aumenta de izquierda a derecha, y el eje Y de abajo a arriba).Obviamente, donde un equipo de sistema de mecanización de la pantalla de coordenadas de manera diferente, (por ejemplo, aumento Y de arriba a abajo, X o De derecha a izquierda), la sintaxis tendrá que ser ajustado/
Otros consejos
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, así que si está bien
a la izquierda ...
(r1.x + r1.width < r2.x)
o a la derecha ...
(r1.x > r2.x + r2.width)
o encima ...
(r1.y + r1.height < r2.y)
o en la parte inferior ...
(r1.y > r2.y + r2.height)
del segundo rectángulo, no puede colisionar con él. Entonces, para tener una función que devuelva un refrán booleano mientras los rectángulos colisionan, simplemente combinamos las condiciones mediante OR 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);
}
Para recibir un resultado positivo al tocar solo, podemos cambiar " < " y " > " por " < = " y " > = " ;.
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 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 (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);
}
Suponga que ha definido las posiciones y los 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 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 ))
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));
}
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 un poco sobre los ángulos en la pregunta, interpreto que todos los rectángulos son perpendiculares entre sí.
Un conocimiento general del á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 los duplicados
1 3 4 5 6
2) recopile todas las coordenadas y (tanto superior como inferior) en una lista, luego ordénelo y elimine los 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) pinta todos los rectángulos 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 rectángulos, es fácil interceptar las superposiciones.
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;
}
No piense que las coordenadas indican dónde están los píxeles. Piense en ellos como si estuvieran 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));
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, recuerde 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 ir a la mitad se tocarán. y de la misma manera bajando + la mitad de su altura. chocará ...
Digamos que los dos rectángulos son el rectángulo A y el rectángulo B. Deje que los centros sean A1 y B1 (las coordenadas de A1 y B1 se pueden encontrar fácilmente), deje que las alturas sean Ha y Hb, el ancho sea Wa y Wb, deje 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)) returns true
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;
}
Tengo una solución muy fácil
que x1, y1 x2, y2, l1, b1, l2, sean cordinates y longitudes y anchuras 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 se ubicará dentro del otro rectángulo o, de manera similar, el punto diagonal a x2, y2 se ubicará dentro del otro rectángulo. que es exactamente lo que implica la condición anterior.
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)
Se encarga de todos los casos posibles.
Esto es del ejercicio 3.28 del libro Introducción a la programación Java - Edición completa. El código prueba si los dos rectángulos son idénticos, 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 rectángulos) Escriba un programa que solicite al usuario que ingrese centra las coordenadas x, y, el ancho y la altura de dos rectángulos y determina si el segundo rectángulo está dentro del primero o se superpone con el primero, como se muestra en la Figura & nbsp; 3.9. Pruebe su programa para cubrir todos los casos. Aquí están las ejecuciones de muestra:
Ingrese las coordenadas x, y, centro, ancho y alto del centro de r1: 2.5 4 2.5 43 Ingrese las coordenadas x, y, centro, ancho y alto del centro de r2: 1.5 5 0.5 3 r2 está dentro de r1
Ingrese las coordenadas x, y, centro, ancho y alto del centro de r1: 1 2 3 5.5 Ingrese las coordenadas x, y, centro, ancho y alto del centro de r2: 3 4 4.5 5 r2 se superpone a r1
Ingrese las coordenadas x, y, centro, ancho y alto del centro de r1: 1 2 3 3 Ingrese las coordenadas x, y, centro, ancho y alto del centro de r2: 40 45 3 2 r2 no se superpone 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 aquellos de ustedes que están usando puntos centrales y medios tamaños para sus datos de rectángulo, 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));
}
Esta respuesta debería ser la respuesta:
Si los rectángulos se superponen, a continuación, el área de solapamiento será mayor que cero.Ahora vamos a buscar la zona de solapamiento:
Si se superponen, a continuación, el borde izquierdo de la superposición-rect será el max(r1.x1, r2.x1) y el borde derecho se min(r1.x2, r2.x2).La longitud de la superposición será min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
De manera 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 luego que no se superpongan.
Sencillo ¿no?
Una mirada al asunto desde un sitio diferente.
El caso resulta que es bastante simple si miramos el problema (algoritmo) desde el otro lado .
Significa que en lugar de responder la pregunta: " ¿Se solapan los rectángulos? " ;, responderemos la pregunta: " ¿Los rectángulos no son superposición? " ;.
Al final, ambas preguntas resuelven el mismo problema, pero la respuesta a la segunda pregunta es más sencilla de implementar porque los rectángulos no se superponen solo cuando uno está debajo del otro o cuando uno está más a la izquierda del otro (es suficiente que ocurra uno de estos casos, pero, por supuesto, puede suceder que ambos sucedan simultáneamente; aquí hay una buena comprensión de la condición lógica " o " es importante). Esto reduce muchos casos que deben considerarse en la primera pregunta.
Todo el asunto también se simplifica mediante el uso de nombres de variables apropiados :
#include<bits/stdc++.h>
struct Rectangle
{
// Coordinates of the top left corner of the rectangle and width and height
float x, y, width, height;
};
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
// Declaration and initialization of local variables
// if x and y are the top left corner of the rectangle
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
// The main part of the algorithm
// The first rectangle is under the second or vice versa
if (top1 < bottom2 || top2 < bottom1)
{
return false;
}
// The first rectangle is to the left of the second or vice versa
if (right1 < left2 || right2 < left1)
{
return false;
}
// Rectangles overlap
return true;
}
Incluso si tenemos una representación diferente de un rectángulo, es fácil adaptarle la función anterior modificando solo la sección donde se definen los cambios de las variables. La parte adicional de la función permanece sin cambios (por supuesto, los comentarios no son realmente necesarios aquí, pero los agregué para que todos puedan entender rápidamente este algoritmo simple).
Un equivalente pero tal vez una forma menos legible de la función anterior pueda verse así:
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
return !(top1 < bottom2 || top2 < bottom1 || right1 < left2 || right2 < left1);
}
" Si realiza sustracción 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 que " (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
Código Java para determinar si los rectángulos se contactan 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;
}
}
}
}
...
