Déterminer si deux rectangles se chevauchent?
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'essaie d'écrire un programme C ++ qui utilise les entrées suivantes de l'utilisateur pour construire des rectangles (entre 2 et 5): height, width, x-pos, y-pos. Tous ces rectangles existeront parallèlement aux axes x et y, c’est-à-dire que tous leurs bords auront des pentes de 0 ou de l’infini.
J'ai essayé de mettre en œuvre ce qui est mentionné dans la question , mais je n'ai pas beaucoup de chance.
Mon implémentation actuelle effectue les opérations suivantes:
// 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;
Cependant, je ne suis pas tout à fait sûr si (a) j'ai correctement implémenté l'algorithme que j'ai lié, ou si je l'ai fait exactement comment interpréter cela?
Des suggestions?
La solution
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
ou, en utilisant les coordonnées cartésiennes
(avec X1 en coordonnée gauche, X2 en coordonnée droite, augmentant de gauche à droite et Y1 en coordonnée supérieure, et Y2 en coordonnée inférieure, augmentant de bas en haut) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
REMARQUE: TOUS LES UTILISATEURS DONT L’AUTORITÉ D’ÉDITATION. VEUILLEZ CESSER DE VOUS TIRER AVEC CELA.
Disons que vous avez Rect A et Rect B. La preuve est par contradiction. Chacune des quatre conditions garantit qu’aucun chevauchement ne peut exister :
- Cond1. Si le bord gauche de A se situe à droite du bord droit du B, - alors A est totalement à droite de B
- Cond2. Si le bord droit de A est à gauche du bord gauche du B, - alors A est totalement à gauche de B
- Cond3. Si le bord supérieur de A est inférieur au bord inférieur de B, - alors A est totalement inférieur à B
- Cond4. Si le bord inférieur de A est supérieur au bord supérieur de B, - alors A est totalement supérieur à B
La condition pour le non-chevauchement est donc
Cond1 Or Cond2 Or Cond3 Or Cond4
Par conséquent, une condition suffisante pour le chevauchement est le contraire.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
La loi de De Morgan dit
Not (A or B or C or D) est identique à Not A And Not B And Not C And Not D
Donc, en utilisant De Morgan, nous avons
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
Ceci est équivalent à:
- Le bord gauche de A à gauche du bord droit de B, [
RectA.Left < RectB.Right] et - Le bord droit de A à droite du bord gauche de B, [
RectA.Right > RectB.Left] et - le sommet de A au-dessus du bas de B, [
RectA.Top > RectB.Bottom] et - le bas de A en dessous de B le haut [
RectA.Bottom < RectB.Top]
Note 1 : il est assez évident que ce même principe peut être étendu à un nombre quelconque de dimensions.
Remarque 2 : il devrait également être assez évident de compter les chevauchements d'un seul pixel, de modifier le < et / ou le > sur cette limite en un <= ou un >=.
Note 3 : lorsque vous utilisez les coordonnées cartésiennes (X, Y), cette réponse est basée sur les coordonnées cartésiennes algébriques standard (x augmente de gauche à droite et Y augmente de bas en haut). Évidemment, lorsqu'un système informatique pourrait mécaniser différemment les coordonnées de l'écran (par exemple, en augmentant Y de haut en bas ou X de droite à gauche), la syntaxe devra être ajustée en conséquence /
Autres conseils
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;
}
Il est plus facile de vérifier si un rectangle est complètement en dehors de l’autre, donc s’il est soit
à gauche ...
(r1.x + r1.width < r2.x)
ou à droite ...
(r1.x > r2.x + r2.width)
ou sur le dessus ...
(r1.y + r1.height < r2.y)
ou sur le bas ...
(r1.y > r2.y + r2.height)
du deuxième rectangle, il ne peut éventuellement pas entrer en collision avec lui. Donc, pour avoir une fonction qui retourne un Booléen disant que les rectangles se rencontrent, nous combinons simplement les conditions par des OR logiques et nions le résultat:
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);
}
Pour recevoir déjà un résultat positif en touchant uniquement, nous pouvons modifier le & "; < &"; et " > " par " < = " et " > = ".
Posez-vous la question opposée: comment puis-je déterminer si deux rectangles ne se croisent pas du tout? Évidemment, un rectangle A complètement à gauche du rectangle B ne se croise pas. Aussi, si A est complètement à droite. De même, si A est complètement au-dessus de B ou complètement au-dessous de B. Dans tous les autres cas, A et B se croisent.
Ce qui suit peut contenir des bugs, mais je suis assez confiant pour l’algorithme:
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);
}
Supposons que vous ayez défini les positions et les tailles des rectangles comme suit:
Mon implémentation C ++ ressemble à ceci:
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 exemple d'appel de fonction selon la figure ci-dessus:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
Les comparaisons à l'intérieur du bloc if ressembleront à celles ci-dessous:
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 ))
Voici comment cela se passe dans l'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));
}
Dans la question, vous créez un lien vers les mathématiques lorsque les rectangles présentent des angles de rotation arbitraires. Si je comprends toutefois le problème des angles dans la question, j’interprète que tous les rectangles sont perpendiculaires les uns aux autres.
Un général connaissant la formule de la zone de chevauchement est:
Utilisation de l'exemple:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) rassemblez toutes les coordonnées x (gauche et droite) dans une liste, puis triez-la et supprimez les doublons
1 3 4 5 6
2) rassemblez toutes les coordonnées y (en haut et en bas) dans une liste, puis triez-la et éliminez les doublons
1 2 3 4 6
3) créez un tableau 2D en fonction du nombre d'espaces entre les coordonnées x uniques * et du nombre d'espaces entre les coordonnées y uniques.
4 * 4
4) peignez tous les rectangles dans cette grille, en incrémentant le nombre de chaque cellule sur laquelle elle apparaît:
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) Lorsque vous dessinez les rectangles, il est facile d’intercepter les chevauchements.
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;
}
Ne pensez pas que les coordonnées indiquent où sont les pixels. Pensez à eux comme étant entre les pixels. De cette façon, l'aire d'un rectangle 2x2 devrait être de 4, pas de 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
Le moyen le plus simple est
/**
* 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);
}
Tout d'abord, gardez à l'esprit que dans les ordinateurs, le système de coordonnées est à l'envers. L'axe des abscisses est identique à celui des mathématiques, mais l'axe des ordonnées augmente vers le bas et diminue vers le haut. si un rectangle est tracé à partir du centre. si les coordonnées x1 sont supérieures à x2 plus sa moitié de largeur. alors cela signifie aller à moitié ils vont se toucher. et de la même manière en descendant vers le bas + la moitié de sa hauteur. il va entrer en collision ..
Disons que les deux rectangles sont le rectangle A et le rectangle B. Soit A1 et B1 les centres (les coordonnées de A1 et B1 sont faciles à trouver), laissez les hauteurs Ha et Hb, les largeurs Wa et Wb, laissez dx est la largeur (x) distance entre A1 et B1 et dy est la hauteur (y) distance entre A1 et B1.
Maintenant, nous pouvons dire que nous pouvons dire un chevauchement A et B: quand
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
J'ai implémenté une version C #, elle est facilement convertie en 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;
}
J'ai une solution très simple
que x1, y1 x2, y2, l1, b1, l2, soient des coordonnées et leurs longueurs et largeurs respectives
considère la condition ((x2
maintenant, le rectangle ne se chevauchera que si le point diagonal à x1, y1 sera situé à l'intérieur de l'autre rectangle ou, de la même manière, le point diagonal à x2, y2 sera situé à l'intérieur de l'autre rectangle. ce qui est exactement la condition ci-dessus implique.
A et B deux rectangle. C soit leur rectangle de couverture.
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)
Il prend en charge tous les cas possibles.
Ceci est tiré de l'exercice 3.28 de l'ouvrage Introduction à la programmation Java - Édition complète. Le code teste si les deux rectangles sont un indenticule, si l'un est à l'intérieur de l'autre et si l'un est à l'extérieur de l'autre. Si aucune de ces conditions n'est remplie, les deux se chevauchent.
** 3.28 (Géométrie: deux rectangles) Ecrivez un programme qui invite l'utilisateur à entrer le le centre des coordonnées x, y, la largeur et la hauteur de deux rectangles et détermine si le deuxième rectangle est à l'intérieur du premier ou recouvre le premier, comme indiqué dans la figure & nbsp; 3.9. Testez votre programme pour couvrir tous les cas. Voici les exemples de tests:
Entrez le centre de x pour les coordonnées x, y, la largeur et la hauteur: 2.5 4 2.5 43 Entrez le centre des coordonnées x, y, la largeur et la hauteur de r2: 1.5 5 0.5 3 r2 est à l'intérieur de r1
Entrez le centre des coordonnées x, y, la largeur et la hauteur de r1: 1 2 3 5.5 Entrez le centre des coordonnées x, y, la largeur et la hauteur de r2: 3 4 4.5 5 r2 chevauche r1
Entrez le centre des coordonnées x, y, la largeur et la hauteur de r1: 1 2 3 3 Entrez le centre des coordonnées x, y, la largeur et la hauteur de r2: 40 45 3 2 r2 ne se chevauche pas 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;
}
Pour ceux d'entre vous qui utilisent des points centraux et des demi-tailles pour leurs données de rectangle, au lieu des valeurs typiques x, y, w, h ou x0, y0, x1, x1, voici comment procéder:
#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));
}
Cette réponse devrait être la meilleure des réponses:
Si les rectangles se chevauchent, la zone de chevauchement sera supérieure à zéro. Trouvons maintenant la zone de recouvrement:
S'ils se chevauchent, le bord gauche du chevauchement-rect sera le max(r1.x1, r2.x1) et le bord droit sera min(r1.x2, r2.x2). Donc, la longueur du chevauchement sera min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
La zone sera donc:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
Si area = 0 ils ne se chevauchent pas.
Simple n'est-ce pas?
Regard sur la question depuis un autre site.
L’affaire s'avère être assez simple si nous examinons le problème (algorithme) de l’autre côté .
Cela signifie qu'au lieu de répondre à la question: & "Les rectangles se chevauchent-ils? &" ;, nous répondrons à la question: & "Les rectangles ne sont-ils pas non chevauchement? & ";
En fin de compte, les deux questions résolvent le même problème, mais la réponse à la deuxième question est plus simple à mettre en œuvre car les rectangles ne se chevauchent pas uniquement lorsque l'un est sous l'autre ou lorsque l'un est en dessous. plus à gauche de l'autre (il suffit que l'un de ces cas se produise, mais bien sûr, il peut arriver que les deux se produisent simultanément - voici une bonne compréhension de la condition logique & ou; " est important). Cela réduit le nombre de cas à prendre en compte pour la première question.
L'ensemble est également simplifié par l'utilisation de noms de variable appropriés :
#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;
}
Même si nous avons une représentation différente d'un rectangle, il est facile d'adapter la fonction ci-dessus en modifiant uniquement la section dans laquelle les modifications de variables sont définies. Il reste l'autre partie de la fonction inchangé (bien sûr, les commentaires ne sont pas vraiment nécessaires ici, mais je les ai ajoutés pour que tout le monde puisse comprendre rapidement cet algorithme simple).
Un équivalent mais peut-être un peu moins lisible dans la fonction ci-dessus peut ressembler à ceci:
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 vous effectuez des coordonnées de soustraction x ou y correspondant aux sommets des deux côtés de chaque rectangle, si les résultats sont identiques, les deux rectangles ne chevauchent pas les axes que " (je suis désolé, je ne suis pas sûr que ma traduction est correcte)
Source: http : //www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
Code Java pour déterminer si les rectangles se touchent ou se chevauchent
...
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;
}
}
}
}
...
