높이, 너비, x-pos, y-pos와 같이 직사각형을 구성하기 위해 사용자의 다음 입력을 사용하는 C ++ 프로그램을 작성하려고합니다. 이 모든 직사각형은 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가 최하위 좌표가 되고 아래에서 위로 증가 합니다. 좌표계가 아닌 경우 (예 : 대부분의 컴퓨터는 Y 방향이 바]], 아래 비교를 교환하십시오 ) …
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) Rect A와 Rect B가 있다고 가정하십시오. 증거는 모순입니다. 네 가지 조건 중 하나에 해당 하면 겹침이 존재하지 않습니다 .
- 조건 1. A의 왼쪽 가장자리가 B의 오른쪽 가장자리 오른쪽에 있으면-A는 완전히 B의 오른쪽입니다
- Cond2. A의 오른쪽 가장자리가 B의 왼쪽 가장자리 왼쪽에 있으면-A는 B의 왼쪽에 완전히 있습니다
- Cond3. A의 상단 가장자리가 B의 하단 가장자리 아래에 있으면-A는 완전히 B 아래에 있습니다
- Cond4. A의 아래쪽 가장자리가 B의 위쪽 가장자리 위에 있으면-A는 완전히 B 위에 있습니다
겹치지 않는 조건은
비-중첩 => Cond1 또는 Cond2 또는 Cond3 또는 Cond4
따라서 오버랩에 대한 충분한 조건은 반대입니다.
오버랩 => NOT (Cond1 또는 Cond2 또는 Cond3 또는 Cond4)
De Morgan의 법칙에 따르면
De Morgan을 사용
Not (A or B or C or D)하는 것과 동일합니다.Not A And Not B And Not C And Not D
Cond1 및 Cond2 및 Cond3 및 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 <=또는 a로 변경하는 것도 분명해야 합니다 >=.
참고 3 :이 답변은 직교 좌표 (X, Y)를 사용할 때 표준 대수 직교 좌표를 기반으로합니다 (x는 왼쪽에서 오른쪽으로 증가하고 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)두 번째 사각형 중 하나와 충돌 할 수 없습니다. 따라서 사각형이 충돌하는 날씨를 나타내는 부울을 반환하는 함수를 가지려면 논리 OR로 조건을 결합하고 결과를 무시하면됩니다.
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));
}