직사각형 겹침

직사각형 겹침(충돌) 판단하는 코드 작성하기

직사각형 겹침 판단

이 문제는 기본적인 물리 충돌 감지에 사용되는 지식이기도 하다.

문제 내용

두 직사각형이 충돌했는지 파악하는 코드를 작성하라.

문제 해설

먼저 x, y 좌표를 가지는 Vector2 또는 Point라는 클래스를 가정한다.
그리고 해당 Vector2 클래스를 사용하는 직사각형 클래스 Rect를 간단히 정의한다.

주의할점은, 문제에서 물어보는 것은 변형되지 않은 직사각형이라는 것이다. 즉 마름모 형태나, 회전등으로 변형된 직사각형을 고려하지 않기 때문에 직사각형은 매우 간단하게 구현된다.

Rect 클래스 구현

변형되지 않는 간단한 직사각형을 만드는데는 4개의 점이 필요없다. 좌측 하단의 Min 점과 우측 상단의 Max 점만 있으면 되기 때문이다. (두 점을 기준으로 잡아 늘린 영역이 직사각형이 된다)
Min 점과 Max 점은 UnderLeft, UpperRight (또는 BottonLeft, TopRight) 라고 표현하기도 한다.

물론 좌표계 취향에 따라 좌측 상단과 우측 하단을 기준으로 직사각형을 만들 순 있다. 이 경우 아래 해설에 나열된 조건을 다르게 적용해야 한다는 사실에 주의한다.
따라서 Rect 클래스를 다음과 같이 구현한다.

public class Rect {
    public Vector2 min;
    public Vector2 max;
}

점의 포함 여부

이어서, 문제를 풀기 위해서는 점이 직사각형에 어떻게 포함되는지 알아야 한다.

어떤 직사각형의 Min 점보다 크고, Max 점보다 작은 좌표를 가진 점은, 해당 직사각형에 포함된다.

간단한 원리다.

  • Min 점보다 크다는 것은, Min 점보다 오른쪽 상단에 있다는 뜻이다.
  • Max 점보다 작다는 것은, Max 점보다 왼쪽 하단에 있다는 뜻이다.

그런데 Min 점과 Max 점을 통해 직사각형을 그리는 것은, Min 점과 Max 점 방향으로 영역을 잡아 늘려 만드는 것이므로, 해당 직사각형 내부의 점들은 모두 위 조건을 만족하게 된다.

직사각형 포함 여부

이제 직사각형의 포함 여부를 판별하는 방법을 알아보자.
그런데 우리는 논리식에서 !A => B 라면, !B => A 라는 사실을 알고 있다.

즉 두 직사각형이 겹치지 않을 조건을 찾으면, 두 직사각형이 겹치게 될 조건을 알 수 있다.

두 직사각형 A와 B가 존재할때 A와 B는 겹치지 않는 경우는 다음과 같은 경우들이 있다.

  • A의 전체 점이, B보다 왼쪽에 있다.
  • A의 전체 점이, B보다 오른쪽에 있다.
  • A의 전체 점이, B보다 아래에 있다.
  • A의 전체 점이, B보다 위에 있다.

이것을 다르게 말하면 다음과 같다.

다음 경우 중 하나라도 해당하면 A와 B는 서로 겹치지 않는다.
(Min의 x, y 값은 Max의 x, y 값보다 항상 작기 때문에 아래 조건들이 생각보다 간결하게 표현된다는 것에 주목한다).

  • A의 Max의 x 값이 B의 Min의 x 값보다 작다
  • A의 Min의 x 값이 B의 Max의 x 값보다 크다
  • A의 Max의 y 값이 B의 Min의 y 값보다 작다
  • A의 Min의 y 값이 B의 Max의 y 값보다 크다

완성된 코드

위 조건을 코드로 나열하면 다음과 같다.

bool isNotOverlaped = a.max.x < b.min.x || a.min.x > b.max.x || a.max.y < b.min.y || a.min.y > b.max.y;

그리고 Not(!)을 붙여 표현하면 다음과 같은 함수를 완성할 수 있게 된다.

bool IsOverlaped(Rect a, Rect b) {	
    return !(a.max.x < b.min.x || a.min.x > b.max.x || a.max.y < b.min.y || a.min.y > b.max.y);
}

이것으로 완성이다.
여기서 드 모르강 법칙을 사용하면 코드를 다른 형태로 다듬을 수 있다. 이것도 언급하면 좋다.

드모르강 법칙
!(A OR B) = !A AND !B
!(A AND B) = !A OR !B

여기에 다음 정리도 사용한다.

!(A > B) = A <= B

따라서 코드를 다시 작성하면 다음과 같다.

bool IsOverlaped(Rect a, Rect b) {	
    return !(a.max.x < b.min.x) && ! (a.min.x > b.max.x) && ! (a.max.y < b.min.y) && !(a.min.y > b.max.y);
}

을 거쳐 다음과 같이 정리된다.

bool IsOverlaped(Rect a, Rect b) {	
    return (a.max.x >= b.min.x) && (a.min.x <= b.max.x) && (a.max.y >= b.min.y) && (a.min.y <= b.max.y);
}