직사각형은 일반적으로 두 개의 좌표, 즉 왼쪽 위 꼭짓점(top-left)과 오른쪽 아래 꼭짓점(bottom-right)만으로 표현할 수 있습니다. 이번 글에서는 두 개의 직사각형이 주어졌을 때, 이들이 서로 겹치는지(overlap) 판별하는 방법을 알아보겠습니다.
문제 정의
두 직사각형은 각각 두 개의 좌표 쌍 (l1, r1)과 (l2, r2)로 주어집니다.
- l1: 첫 번째 직사각형의 왼쪽 위 꼭짓점
- r1: 첫 번째 직사각형의 오른쪽 아래 꼭짓점
- l2: 두 번째 직사각형의 왼쪽 위 꼭짓점
- r2: 두 번째 직사각형의 오른쪽 아래 꼭짓점
여기서는 모든 직사각형이 좌표축에 평행하다고 가정합니다.
해결 접근 방법
두 직사각형이 겹치지 않는 경우는 다음 두 가지뿐입니다. 따라서 이 조건들을 검사하여 겹침 여부를 판별할 수 있습니다.
- 한 직사각형이 다른 직사각형의 위쪽 변보다 위에 있는 경우
- 한 직사각형이 다른 직사각형의 왼쪽 변보다 왼쪽에 있는 경우
즉, 첫 번째 직사각형이 두 번째 직사각형의 왼쪽에 완전히 벗어나 있거나(l1.x > r2.x), 두 번째 직사각형이 첫 번째 직사각형의 왼쪽에 완전히 벗어나 있으면(l2.x > r1.x) 겹치지 않습니다. 마찬가지로 y 좌표를 기준으로 한 직사각형이 다른 직사각형보다 위쪽에 완전히 벗어나 있어도 겹치지 않습니다. 이 두 조건에 해당하지 않으면 두 직사각형은 반드시 겹칩니다.
예제 코드
#include<iostream>
using namespace std;
class Point {
public:
int x, y;
};
bool isOverlapping(Point l1, Point r1, Point l2, Point r2) {
if (l1.x > r2.x || l2.x > r1.x)
return false;
if (l1.y < r2.y || l2.y < r1.y)
return false;
return true;
}
int main() {
Point l1 = {0, 10}, r1 = {10, 0};
Point l2 = {5, 5}, r2 = {15, 0};
if (isOverlapping(l1, r1, l2, r2))
cout << "Rectangles are Overlapping";
else
cout << "Rectangles are not Overlapping";
}실행 결과
Rectangles are Overlapping
코드 설명
위 예제에서 첫 번째 직사각형은 (0, 10)부터 (10, 0)까지의 영역을 차지하고, 두 번째 직사각형은 (5, 5)부터 (15, 0)까지의 영역을 차지합니다. 두 직사각형은 x 구간 [5, 10]과 y 구간 [0, 5]에서 서로 겹치므로, 함수는 true를 반환하고 "Rectangles are Overlapping"이 출력됩니다.
이 알고리즘은 단순한 조건 비교만 수행하므로 시간 복잡도는 O(1)이며, 충돌 감지(collision detection), 게임 물리 엔진, 화면 영역 계산 등 다양한 분야에서 활용될 수 있습니다.