결정하는 경우에 두 사각형이 서로 겹치는 다른?
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
내가 하려고 쓰는 C++프로그램에는 다음 입력에서 사용자 구성 직사각형(2-5):높이,너비,x-pos,y pos.이러한 모든 사각형이 존재하는 평행한 x 와 y 축의 모든 것 그들의 가장자리가 슬로프가 0 또는습니다.
해봤을 구현하이 무엇에서 설명 이 질문 하지만 나는 매우 행운입니다.
나는 현재 구현하는 다음과 같은 작업을 수행합니다.
// 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;
그러나 나는 아주 확실하지 않는 경우에는(a)내가 구현되었는지 알고리즘 제가 연결되어 올바르게한 경우,또는 나는 정확하게 해석하는 방법 이?
어떤 방법이 있나요?
해결책
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
또는 직교 좌표를 사용합니다
(X1이 왼쪽 코디, X2는 오른쪽 코디, 왼쪽에서 오른쪽으로 증가하고 Y1은 상단 코드이며 Y2는 하단 코드로, 하단에서 상단으로 증가합니다) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
참고 : 편집 권한을 가진 모든 사용자에게. 이 문제를 멈추지 마십시오.
rect a, 그리고 퇴근 B가 있다고 말하면 B. 증거는 모순에 의한 것입니다. 네 가지 조건 중 하나는이를 보장합니다 오버랩은 존재할 수 없습니다:
- cond1. A의 왼쪽 가장자리가 B의 오른쪽 가장자리의 오른쪽에 있으면 A가 B의 오른쪽에 있습니다.
- cond2. A의 오른쪽 가장자리가 B의 왼쪽 가장자리의 왼쪽에 있으면 A가 B의 왼쪽에 있습니다.
- cond3. A의 상단 가장자리가 B의 하단 가장자리 아래에 있으면 A는 완전히 B 미만입니다.
- Cond4. A의 하단 모서리가 B의 상단 가장자리 위에 있다면 A는 완전히 B 위에 있습니다.
따라서 비 탑승자의 상태는입니다
Cond1 Or Cond2 Or Cond3 Or Cond4
따라서, 겹침을위한 충분한 조건이 반대입니다.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
드 모건의 법칙은 말한다
Not (A or B or C or D) 와 같다 Not A And Not B And Not C And Not D
De Morgan을 사용하여 우리는 가지고 있습니다
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
이것은 다음과 같습니다.
- A의 왼쪽 가장자리에서 B의 오른쪽 가장자리에서 [
RectA.Left < RectB.Right], 그리고 - A의 오른쪽 가장자리에서 B의 왼쪽 가장자리의 오른쪽에서 [
RectA.Right > RectB.Left], 그리고 - A의 상단 B의 하단, [
RectA.Top > RectB.Bottom], 그리고 - A의 맨 아래 B의 상단 [
RectA.Bottom < RectB.Top]
참고 1:이 같은 원칙이 여러 차원으로 확장 될 수 있다는 것은 상당히 명백합니다.
노트 2: 단 하나의 픽셀의 겹침을 계산하는 것도 상당히 분명해야합니다. < 및/또는 > 그 경계에서 <= 또는 a >=.
노트 3:이 답변은 직교 좌표 (x, y)를 활용할 때 표준 대수직 직교 좌표를 기반으로합니다 (X는 왼쪽에서 오른쪽으로 증가하고 Y는 바닥에서 상단으로 증가합니다). 분명히 컴퓨터 시스템이 화면 좌표를 다르게 기계화 할 수있는 경우 (예 : y는 위에서 아래로 y를 증가 시키거나, 오른쪽에서 왼쪽으로 x) 구문을 그에 따라 조정해야합니다.
다른 팁
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;
}
사각형이 다른 것 외부에 있는지 확인하는 것이 더 쉽습니다.
왼쪽에...
(r1.x + r1.width < r2.x)
또는 오른쪽에 ...
(r1.x > r2.x + r2.width)
아니면 위에 ...
(r1.y + r1.height < r2.y)
또는 바닥에 ...
(r1.y > r2.y + r2.height)
두 번째 사각형의 경우 충돌 할 수 없습니다. 따라서 사각형이 충돌하는 날씨에 부울을 반환하는 함수를 갖기 위해서는 논리적 ors의 조건을 결합하고 결과를 부정합니다.
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);
}
만질 때만 긍정적 인 결과를 얻으려면 "<"및 ">"를 "<="및 "> ="으로 변경할 수 있습니다.
반대의 질문을 스스로에게 물어보십시오. 두 직사각형이 전혀 교차하지 않는지 어떻게 결정할 수 있습니까? 분명히, 사각형 B의 왼쪽에있는 사각형 A는 교차하지 않습니다. 또한 A가 완전히 오른쪽에 있다면. 그리고 유사하게 A가 B 위 또는 B보다 미만인 경우 다른 경우 A와 B가 교차합니다.
다음은 버그가있을 수 있지만 알고리즘에 대해 확신합니다.
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);
}
다음과 같이 직사각형의 위치와 크기를 정의했다고 가정 해 봅시다.
내 C ++ 구현은 다음과 같습니다.
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;
}
위의 주어진 그림에 따라 예제 함수 호출 :
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
내부의 비교 if 블록은 다음과 같습니다.
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 ))
Java API에서 수행 된 방법은 다음과 같습니다.
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));
}
질문에,당신은 링크를 할 수학한 경우 사각형은 임의의 회전각.만약 이 비트에 대한 각 질문에서 그러나 나는 해석하는 모든 사각형 수직으로 한다.
일반적인 영역을 알고있는 중첩의 공식입니다:
를 사용하여 예를 들어:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1)수집하는 모든 x 좌표(왼쪽과 오른쪽)으로 목록은,그 다음 그것을 분류하고 중복을 제거
1 3 4 5 6
2)수집하는 모든 y 좌표로(상단과 하단)으로 목록은,그 다음 그것을 분류하고 중복을 제거
1 2 3 4 6
3)2 차원 배열에 의해 번호 사이의 간격의 독특한의 x 좌표*번호 사이의 간격의 독특한다.
4 * 4
4)모든 사각형으로 이 격자 증가 횟수 세포 그것을 통해 발생합:
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)당신은 페인트 사각형,그것의 쉬운을 차단하기 위해 중복.
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;
}
의 생각하지 않는 좌표를 나타내는 픽셀이 있다.그들의 생각되는 것으로 간의 픽셀이 있습니다.는 방법으로,이 지역의 2x2 직사각형이어야 4,지 않 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
가장 쉬운 방법입니다
/**
* 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);
}
우선 컴퓨터에서 좌표 시스템이 거꾸로되어 있음을 생각합니다. x 축은 수학에서와 동일하지만 y 축은 아래쪽으로 증가하고 위로 올라가면 감소합니다. X1 좌표가 X2보다 크면 Widht의 절반이됩니다. 그러면 반쪽으로가는 것이 서로를 만지는 것을 의미합니다. 그리고 같은 방식으로 높이의 절반을 하향 하향 조정합니다. 충돌 할 것입니다 ..
두 개의 사각형이 사각형 A와 사각형 B라고 가정 해 봅시다. 중심이 A1과 B1이되도록하자 (A1과 B1의 좌표가 쉽게 찾을 수 있음) 높이를 HA 및 HB로, 너비는 WA 및 WB가됩니다. DX가 A1과 B1 사이의 폭 (x) 거리는 A1과 B1 사이의 높이 (y) 거리입니다.
이제 우리는 A와 B 중첩을 말할 수 있다고 말할 수 있습니다.
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
C# 버전을 구현했으며 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;
}
매우 쉬운 해결책이 있습니다
x1, y1 x2, y2, l1, b1, l2를 각각 코디네이트와 길이와 폭으로 두십시오.
조건을 고려하십시오 ((x2
이제 이러한 사각형이 겹치는 유일한 방법은 x1에 대한 포인트 대각선이 다른 사각형 내부에 있거나 유사하게 x2와의 대각선이 다른 사각형 안에 있습니다. 위의 조건은 정확히 의미합니다.
a와 b는 두 개의 사각형입니다. c 덮개 사각형이 되십시오.
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)
가능한 모든 사례를 관리합니다.
이것은 Java Programming- 포괄적 인 에디션을 소개 한 책 3.28의 연습에서 나온 것입니다. 코드는 두 사각형이 인두통인지, 하나는 다른 내부에 있는지, 그리고 하나는 다른 것 외부에 있는지 테스트합니다. 이 조건 중 어느 것도 충족되지 않으면 두 개의 겹침.
** 3.28 (Geometry : 2 개의 직사각형) 사용자가 두 개의 직사각형의 중심 X-, y 코디네이트, 너비 및 높이를 입력하도록 촉구하고 두 번째 사각형이 첫 번째 또는 첫 번째와 오버랩에 있는지 여부를 결정하는 프로그램을 작성합니다. 그림 3.9와 같이. 모든 사례를 다루기 위해 프로그램을 테스트하십시오. 샘플 실행은 다음과 같습니다.
R1 's Center X-, y 코디네이트, 너비 및 높이를 입력하십시오 : 2.5 4 2.5 43 R2의 중심 X-, y 코디네이트, 너비 및 높이를 입력하십시오 : 1.5 5 0.5 3 R2는 R1 내부에 있습니다.
R1 's Center X-, Y 코디네이트, 너비 및 높이를 입력하십시오 : 1 2 3 5.5 R2의 중심 X-, Y 코디네이트, 너비 및 높이를 입력하십시오 : 3 4 4.5 5 R2 오버 랩 R1
R1 's Center X-, Y 코디네이트, 너비 및 높이를 입력하십시오 : 1 2 3 3 R2의 중심 X-, Y 코디네이트, 너비 및 높이를 입력하십시오 : 40 45 3 2 R2는 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;
}
전형적인 x, y, w, h 또는 x0, y0, x1, x1 대신 사각형 데이터에 중심 지점과 반 크기를 사용하는 사람들을 위해 다음은 다음과 같습니다.
#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));
}
이 답변은 최고의 답변이어야합니다.
직사각형이 겹치면 오버랩 영역이 0보다 클 것입니다. 이제 중첩 영역을 찾으십시오.
그들이 겹치면 오버 랩 강의의 왼쪽 가장자리는 max(r1.x1, r2.x1) 그리고 오른쪽 가장자리가 될 것입니다 min(r1.x2, r2.x2). 겹침의 길이는 있습니다 min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
그래서 지역은 다음과 같습니다.
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
만약에 area = 0 그러면 그들은 겹치지 않습니다.
단순하지 않습니까?
다른 사이트의 문제를 살펴보십시오.
사건이 밝혀졌습니다 다른 쪽에서 문제 (알고리즘)를 보면 아주 간단하게.
그것은 "직사각형이 겹치는가?"라는 질문에 대답하는 대신, 우리는 다음과 같은 질문에 대답 할 것임을 의미합니다. ~ 아니다 오버랩? ".
결국 두 질문 모두 동일한 문제를 해결하지만 두 번째 질문에 대한 답은 구현하기가 더 간단합니다. 왜냐하면 사각형은 하나가 다른 사람 아래에 있거나 하나가 다른 왼쪽에있을 때만 겹치지 않습니다. (이러한 사례 중 하나가 발생하기에 충분하지만 물론 둘 다 동시에 발생할 수 있습니다. 여기서 논리적 조건을 잘 이해하는 것이 중요합니다 "또는"중요합니다. " 이것은 첫 번째 질문에서 고려해야 할 많은 사례를 줄입니다.
전체 문제도 있습니다 적절한 변수 이름을 사용하여 단순화합니다:
#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;
}
조차 사각형의 다른 표현이있는 경우 변수 변경이 정의되는 섹션 만 수정하여 위의 기능을 쉽게 조정할 수 있습니다. 함수의 추가 부분은 변경되지 않은 상태로 남아 있습니다 (물론 의견은 실제로 필요하지 않지만 모든 사람들 이이 간단한 알고리즘을 빠르게 이해할 수 있도록 추가했습니다).
an 동등한 그러나 아마도 읽기 쉬운 것일 수도 있습니다 위의 기능의 형태 다음과 같이 보일 수 있습니다.
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);
}
"각 사각형을 향한 두 개의 정점에 해당하는 뺄셈 X 또는 Y 좌표를 수행하는 경우 결과가 동일한 부호 인 경우 두 사각형이 축을 겹치지 않습니다."(죄송합니다. 내 번역이 올바른지 확실하지 않습니다. )
원천: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
사각형이 서로 접촉하거나 겹치는 지 파악하기위한 Java 코드
...
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;
}
}
}
}
...
