문제
왼쪽 위 코너의 좌표 (0, 0), 오른쪽 아래 코너의 좌표 (w-1, h-1) 총 두 개의 좌표로 사각형을 표현한다고 하자.
rect1 = [x1, y1, x2, y2], rect2 = [x3, y3, x4, y4] 두 개의 사각형의 겹치는 넓이는 구하여라.
먼저 사각형이 겹치는 케이스를 여러가지로 고려해보자.
회색 사각형을 기준으로
- 한쪽 귀퉁이를 덮음
- 한 변을 덮음
- 자신의 한 변이 모두 덮임
- 교차
- 자신이 포함됨
- 다른 사각형을 모두 덮음
- 겹치지 않음
겹치는 사례를 나누어서 처리할 수 있으나 겹치는 영역은 공통점이 있기 때문에 하나의 사례로 처리한다.
겹치는 영역의
왼쪽 변은, 기존 두 사각형의 왼쪽 변 중에서 더 오른쪽에 있는 것
위쪽 변은, 기존 두 사각형의 위쪽 변 중에서 더 아래쪽에 있는 것
오른 쪽변은, 기존 두사각형의 오른쪽 변 중에서 더 왼쪽에 있는 것
아래쪽 변은, 기존 두 사각형의 아래쪽 변 중에서 더 위쪽에 있는 것
위의 사항을 파악하여 겹치는 사각형의 최종 넓이를 구현할 수 있다.
(왼쪽 변) 겹치는 영역의 left upper corner의 x는 두 사각형의 left upper corner 중 더 큰 x
(위쪽 변) 겹치는 영역의 left upper corner의 y는 두 사각형의 left upper corner 중 더 큰 y
(오른 쪽변) 겹치는 영역의 right lower corner의 x는 두 사각형의 left upper corner 중 더 작은 x
(아래쪽 변) 겹치는 영역의 right lower corner의 y는 두 사각형의 left upper corner 중 더 작은 y
허접하지만 python 코드로 구현하면 아래와 같다. 겹치지 않는 경우가 있기에 예외 처리해주는 것도 잊어서는 안된다.
def compute_intersect_area(rect1, rect2):
x1, y1 = rect1[0], rect1[1]
x2, y2 = rect1[2], rect1[3]
x3, y3 = rect2[0], rect2[1]
x4, y4 = rect2[2], rect2[3]
## case1 오른쪽으로 벗어나 있는 경우
if x2 < x3:
return 0
## case2 왼쪽으로 벗어나 있는 경우
if x1 > x4:
return 0
## case3 위쪽으로 벗어나 있는 경우
if y2 < y3:
return 0
## case4 아래쪽으로 벗어나 있는 경우
if y1 > y4:
return 0
left_up_x = max(x1, x3)
left_up_y = max(y1, y3)
right_down_x = min(x2, x4)
right_down_y = min(y2, y4)
width = right_down_x - left_up_x
height = right_down_y - left_up_y
return width * height
<참고 자료>