Determinare se due rettangoli si sovrappongono?
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto cercando di scrivere un programma C ++ che prende i seguenti input dall'utente per costruire rettangoli (tra 2 e 5): altezza, larghezza, x-pos, y-pos. Tutti questi rettangoli saranno paralleli all'asse xe all'asse y, ovvero tutti i loro bordi avranno pendenze di 0 o infinito.
Ho provato ad attuare ciò che è menzionato in questa domanda ma non ho molta fortuna.
La mia attuale implementazione procede come segue:
// 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;
Tuttavia non sono del tutto sicuro se (a) ho implementato l'algoritmo a cui ho collegato correttamente o se ho fatto esattamente come interpretarlo?
Qualche suggerimento?
Soluzione
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
oppure, usando le coordinate cartesiane
(Con X1 come coordinatore sinistro, X2 come coordinatore destro, aumentando da sinistra a destra e Y1 come coordinatore superiore, e Y2 come coordinatore inferiore, aumentando dal basso verso l'alto) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
NOTA: A TUTTI GLI UTENTI CON AUTORITÀ DI MODIFICA. PER FAVORE, FERMATI DI FIDDLING CON QUESTO.
Supponi di avere Rect A e Rect B. La prova è per contraddizione. Una delle quattro condizioni garantisce che non possa esistere sovrapposizione :
- COND1. Se il bordo sinistro di A è a destra del bordo destro di B, - allora A è Totalmente a destra di B
- COND2. Se il bordo destro di A è a sinistra del bordo sinistro di B, - allora A è Totalmente a sinistra di B
- Cond3. Se il bordo superiore di A è inferiore al bordo inferiore di B, - allora A è totalmente inferiore a B
- Cond4. Se il bordo inferiore di A è sopra il bordo superiore di B, - allora A è totalmente sopra B
Quindi la condizione per la non sovrapposizione è
Cond1 Or Cond2 Or Cond3 Or Cond4
Pertanto, una condizione sufficiente per la sovrapposizione è l'opposto.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
La legge di De Morgan dice che
Not (A or B or C or D) è uguale a Not A And Not B And Not C And Not D
quindi usando De Morgan, abbiamo
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
Ciò equivale a:
- Bordo sinistro di A a sinistra del bordo destro di B, [
RectA.Left < RectB.Right] e - Il bordo destro di A a destra del bordo sinistro di B, [
RectA.Right > RectB.Left] e - A in alto sopra B in basso, [
RectA.Top > RectB.Bottom] e - La parte inferiore di A sotto la parte superiore di B [
RectA.Bottom < RectB.Top]
Nota 1 : è abbastanza ovvio che questo stesso principio può essere esteso a qualsiasi numero di dimensioni.
Nota 2 : dovrebbe anche essere abbastanza ovvio contare le sovrapposizioni di un solo pixel, cambiare < e / o > su quel limite in <= o >=.
Nota 3 : questa risposta, quando si utilizzano le coordinate cartesiane (X, Y) si basa sulle coordinate cartesiane algebriche standard (x aumenta da sinistra a destra e Y aumenta dal basso verso l'alto). Ovviamente, laddove un sistema informatico potrebbe meccanizzare le coordinate dello schermo in modo diverso (ad esempio, aumentando Y dall'alto verso il basso o X da destra a sinistra), la sintassi dovrà essere regolata di conseguenza /
Altri suggerimenti
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;
}
È più facile controllare se un rettangolo è completamente fuori dall'altro, quindi se è
a sinistra ...
(r1.x + r1.width < r2.x)
o sulla destra ...
(r1.x > r2.x + r2.width)
o in alto ...
(r1.y + r1.height < r2.y)
o in fondo ...
(r1.y > r2.y + r2.height)
del secondo rettangolo, non può assolutamente scontrarsi con esso. Quindi per avere una funzione che restituisca un tempo booleano che dice che i rettangoli si scontrano, combiniamo semplicemente le condizioni con OR logici e neghiamo il risultato:
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);
}
Per ricevere già un risultato positivo solo toccando, possiamo cambiare " < " e " > " di " < = " e " > = " ;.
Ponetevi la domanda opposta: come posso determinare se due rettangoli non si intersecano affatto? Ovviamente, un rettangolo A completamente a sinistra del rettangolo B non si interseca. Anche se A è completamente a destra. E allo stesso modo se A è completamente sopra B o completamente sotto B. In ogni altro caso A e B si intersecano.
Quello che segue potrebbe contenere dei bug, ma sono abbastanza fiducioso dell'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);
}
Supponi di aver definito le posizioni e le dimensioni dei rettangoli in questo modo:
La mia implementazione in C ++ è così:
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 esempio di chiamata di funzione secondo la figura sopra riportata:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
I confronti all'interno del blocco if appariranno come di seguito:
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 ))
Ecco come viene eseguito nell'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));
}
Nella domanda, ti colleghi ai calcoli per quando i rettangoli si trovano ad angoli di rotazione arbitrari. Se capisco comunque la parte relativa agli angoli della domanda, interpreto che tutti i rettangoli sono perpendicolari l'uno all'altro.
Un generale che conosce l'area della formula di sovrapposizione è:
Utilizzando l'esempio:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) raccogli tutte le coordinate x (sia a destra che a sinistra) in un elenco, quindi ordinale e rimuovi i duplicati
1 3 4 5 6
2) raccogli tutte le coordinate y (sia in alto che in basso) in un elenco, quindi ordinale e rimuovi i duplicati
1 2 3 4 6
3) crea un array 2D per numero di spazi tra le coordinate x uniche * numero di spazi tra le coordinate y uniche.
4 * 4
4) dipingi tutti i rettangoli in questa griglia, aumentando il conteggio di ogni cella su cui si verifica:
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) Mentre dipingi i rettangoli, è facile intercettare le sovrapposizioni.
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;
}
Non pensare alle coordinate che indicano dove sono i pixel. Pensali come se fossero tra i pixel. In questo modo, l'area di un rettangolo 2x2 dovrebbe essere 4, non 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
Il modo più semplice è
/**
* 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);
}
prima di tutto ti viene in mente che nei computer il sistema di coordinate è sottosopra. l'asse x è lo stesso della matematica ma l'asse y aumenta verso il basso e diminuisce andando verso l'alto. se il rettangolo viene disegnato dal centro. se le coordinate x1 sono maggiori di x2 più la sua metà della larghezza. allora significa che andando a metà si toccheranno. e nello stesso modo scendendo + metà della sua altezza. si scontrerà ..
Supponiamo che i due rettangoli siano il rettangolo A e il rettangolo B. Lascia che i centri siano A1 e B1 (le coordinate di A1 e B1 possono essere facilmente individuate), che le altezze siano Ha e Hb, la larghezza sia Wa e Wb, lascia che dx è la larghezza (x) distanza tra A1 e B1 e dy l'altezza (y) distanza tra A1 e B1.
Ora possiamo dire che possiamo dire che A e B si sovrappongono: quando
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
Ho implementato una versione C #, è facilmente convertibile in 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;
}
Ho una soluzione molto semplice
lascia che x1, y1 x2, y2, l1, b1, l2 siano rispettivamente coordinate e lunghezze e ampiezze
considera la condizione ((x2
ora l'unico modo in cui questi rettangoli si sovrapporranno è se il punto diagonale a x1, y1 si troverà all'interno dell'altro rettangolo o allo stesso modo il punto diagonale a x2, y2 si troverà all'interno dell'altro rettangolo. che è esattamente la condizione sopra esposta.
A e B sono due rettangoli. C è il loro rettangolo di copertura.
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)
Si occupa di tutti i casi possibili.
Questo è tratto dall'esercizio 3.28 del libro Introduzione alla programmazione Java - Edizione completa. Il codice verifica se i due rettangoli sono indipendenti, se uno è all'interno dell'altro e se uno è all'esterno dell'altro. Se nessuna di queste condizioni è soddisfatta, le due si sovrappongono.
** 3.28 (Geometria: due rettangoli) Scrivi un programma che richiede all'utente di inserire il centra le coordinate x, y, la larghezza e l'altezza di due rettangoli e determina se il secondo rettangolo si trova all'interno del primo o si sovrappone al primo, come mostrato in Figura & nbsp; 3.9. Metti alla prova il tuo programma per coprire tutti i casi. Ecco le esecuzioni di esempio:
Inserisci le coordinate x, y, centro, larghezza e altezza di r1: 2,5 4 2,5 43 Inserisci le coordinate x, y, centro di r2, larghezza e altezza: 1,5 5 0,5 3 r2 è all'interno di r1
Inserisci le coordinate x, y, centro, larghezza e altezza di r1: 1 2 3 5.5 Inserisci le coordinate x, y, centro x di r2, larghezza e altezza: 3 4 4.5 5 r2 si sovrappone a r1
Inserisci le coordinate x, y, centro, larghezza e altezza di r1: 1 2 3 3 Inserisci le coordinate x, y, centro di r2, larghezza e altezza: 40 45 3 2 r2 non si sovrappone 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;
}
Per quelli di voi che stanno usando punti centrali e mezze dimensioni per i loro dati rettangolari, anziché i tipici x, y, w, h o x0, y0, x1, x1, ecco come è possibile farlo:
#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));
}
Questa risposta dovrebbe essere la risposta migliore:
Se i rettangoli si sovrappongono, l'area di sovrapposizione sarà maggiore di zero. Ora cerchiamo di trovare l'area di sovrapposizione:
Se si sovrappongono, il bordo sinistro della sovrapposizione sarà il max(r1.x1, r2.x1) e il bordo destro sarà min(r1.x2, r2.x2). Quindi la lunghezza della sovrapposizione sarà min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
Quindi l'area sarà:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
Se area = 0 non si sovrappongono.
Semplice non è vero?
Uno sguardo alla questione da un sito diverso.
Il caso risulta abbastanza semplice se osserviamo il problema (algoritmo) dall'altra parte .
Significa che invece di rispondere alla domanda: " I rettangoli si sovrappongono? " ;, risponderemo alla domanda: " I rettangoli non non overlap? " ;.
Alla fine, entrambe le domande risolvono lo stesso problema ma la risposta alla seconda domanda è più semplice da implementare perché i rettangoli non si sovrappongono solo quando uno è sotto l'altro o quando uno è più a sinistra dell'altro (è sufficiente che si verifichi uno di questi casi, ma ovviamente può accadere che entrambi accadranno simultaneamente - qui una buona comprensione della condizione logica " oppure " è importante). Ciò riduce molti casi che devono essere considerati nella prima domanda.
L'intera questione è anche semplificata dall'uso di nomi di variabili appropriati :
#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;
}
Anche se abbiamo una rappresentazione diversa di un rettangolo, è facile adattare la funzione sopra ad essa modificando solo la sezione in cui sono definite le modifiche alle variabili. L'ulteriore parte della funzione rimane invariato (ovviamente, i commenti non sono davvero necessari qui, ma li ho aggiunti in modo che tutti potessero capire rapidamente questo semplice algoritmo).
Un equivalente ma forse un po 'meno leggibile forma della funzione sopra potrebbe apparire così:
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);
}
" Se si eseguono sottrazioni coordinate x o y corrispondenti ai vertici dei due rivolti verso ciascun rettangolo, se i risultati sono lo stesso segno, i due rettangoli non si sovrappongono agli assi che " (mi dispiace, non sono sicuro che la mia traduzione sia corretta)
Fonte: http : //www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
Codice Java per capire se i rettangoli si stanno contattando o si sovrappongono
...
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;
}
}
}
}
...
