문제 개요
하나의 원이 (반지름 r, xc, yc) 형태로 표현된다고 가정해 보겠습니다. 여기서 (xc, yc)는 원의 중심 좌표입니다. 또한 축에 평행한 사각형(axis-aligned rectangle)은 (x1, y1, x2, y2) 형태로 주어지며, (x1, y1)은 사각형의 왼쪽 아래 꼭짓점 좌표, (x2, y2)는 오른쪽 위 꼭짓점 좌표를 나타냅니다. 이 글에서는 원과 사각형이 서로 겹치는지(overlap) 판별하는 방법을 알아보겠습니다.
예를 들어 다음과 같은 상황이 주어졌다면,
원과 사각형이 겹치므로 출력 결과는 true가 됩니다.
해결 접근 방법
이 문제의 핵심 아이디어는 사각형 내부에서 원의 중심에 가장 가까운 점을 찾은 뒤, 그 점과 원 중심 사이의 거리가 반지름 이하인지 확인하는 것입니다. 다음 단계를 따라 해결할 수 있습니다.
먼저
eval()함수를 정의합니다. 이 함수는 a, b, c 세 값을 인자로 받으며, b와 min(a, c) 중 더 큰 값을 반환합니다. 쉽게 말해 a를 [b, c] 구간 안으로 제한하는 클램프(clamp) 연산입니다.메인 메소드에서는 다음을 수행합니다:
cdx = eval(cx, left, right),cdy = eval(cy, bottom, top)— 사각형 범위 안에서 원 중심에 가장 가까운 점의 x, y 좌표를 계산합니다.rwid = right - left,rh = top - bottom— 사각형의 너비와 높이를 구합니다.dx = cx - cdx,dy = cy - cdy— 원 중심과 가장 가까운 점 사이의 x, y 방향 거리 성분을 계산합니다.disSq = (dx * dx) + (dy * dy)— 두 점 사이 거리의 제곱을 구합니다. 제곱근 연산을 생략하고 제곱 값끼리 비교하면 부동소수점 오차와 연산 비용을 줄일 수 있습니다.sqrRadius = (r * r)— 반지름의 제곱을 구합니다.disSq <= sqrRadius가 참이면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 두 거리가 정확히 같으면 원이 사각형 변에 닿아 있는 경우이므로 겹치는 것으로 간주합니다.
구현 예시
아래 C++ 구현을 통해 동작 방식을 더 자세히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int eval(int a, int b, int c){
return max(b, min(a, c));
}
bool checkOverlap(int r, int cx, int cy, int left, int bottom, int right, int top){
double cdx = eval(cx, left, right);
double cdy = eval(cy, bottom, top);
double rwid = right - left;
double rh = top - bottom;
double dx = cx - cdx;
double dy = cy - cdy;
double disSq = (dx * dx) + (dy * dy);
double sqrRadius = (r * r);
return (disSq <= sqrRadius);
}
};
main(){
Solution ob;
cout << (ob.checkOverlap(1, 0, 0, 1, -1, 3, 1));
}
입력
1, 0, 0, 1, -1, 3, 1
출력
1
정리
이 알고리즘은 원 중심을 사각형의 x, y 범위로 각각 클램핑하여 최근접 점을 구한 뒤, 유클리드 거리의 제곱과 반지름의 제곱을 비교하는 방식으로 동작합니다. 시간 복잡도는 O(1)로 매우 효율적이며, 게임 충돌 판정이나 2D 그래픽 처리 등 다양한 분야에서 널리 활용되는 기법입니다.