볼록다각형(Convex)의 넓이 구하기

얼마전 볼록껍질 문제를 해결하고 기하 문제에 관심이 생겨 백준 1077번 넓이 문제에 도전해봤다. 새로 배워야 할 개념이 많았는데 넓이를 구하는 기초적인 아이디어를 잘 구현해낸 것 같아 정리해보고자 한다.

 

1. 볼록다각형의 정의

이 문제를 연구하다가 새로 알게된 사실이다. 볼록다각형은 이웃하지 않는 두 점을 이은 선분이 도형 내부에 존재하는 단순다각형을 말한다. 단순다각형은 다각형을 이루는 변들이 서로 교차하지 않는 다각형을 말한다. 볼록 집합이라는 것도 있는데, 집합 내에서 어떤 두 점을 선택해도 선분이 집합 내부에 그려지게 되는 집합을 말한다. 볼록다각형은 볼록 집합을 이루는 단순다각형이기도 하다.

 

엄밀한 볼록다각형은 모든 내각의 크기가 180도 미만이어야 한다. 어떤 문제들은 이 조건을 명시하지만 그렇지 않는 문제에서는 볼록다각형의 내각이 180도인 경우도 고려해보아야 한다.

 

2. 볼록다각형의 넓이를 구하는 방법

한 꼭짓점을 정해 다각형을 여러 삼각형으로 분할하여 넓이를 구하는 방법, 모든 꼭짓점이 정수 좌표일 때, 교차점의 개수를 세어 넓이를 구하는 픽의 정리, 좌표 값을 교차하며 곱한 값을 더하는 방법 등 여러 가지 방법이 있고 상황에 따라 효율적인 방법을 선택할 수 있을 것 같지만 아무도 설명해주지 않는(아마도 비효율적인 방법이기 때문인 것 같다.) 방법으로 넓이를 구해본다.

위와 같은 볼록다각형의 넓이를 구해보자.

전체 다각형의 넓이를 S라고 하자. 이제 넓이를 두 부분으로 나누어 계산할 것이다.

 

나중에 소스코드에서는 x좌표를 기준으로 하겠지만 직관한 아이디어를 그대로 그려서 설명한다.

다각형에서 같은 y좌표를 갖는 점 중에서 y축으로부터 가장 멀리 떨어져있는 점들을 y축까지 이동시키며 자취를 남긴다고 해보자. 모든 자취의 면적을 S1이라고 한다. 이 넓이는 S를 포함하고 있다.

 

반대로 같은 y좌표를 갖는 점 중에서 y축에 가까운 점들을 y축까지 이동시키며 그린 자취는 S2로 표현할 수 있다. 그럼 S=S1-S2이다. 다각형이 볼록다각형이기 때문에 항상 S=S1-S2를 만족한다.

 

S1의 자취를 그릴 점들은 upper, S2의 자취를 그릴 점들은 lower에 저장한다. 그럼 전체 다각형을 이루는 좌표를 이렇게 분리할 수 있다. 여기서 그라함 스캔을 활용한다. 좌표계를 2차원 배열 정렬 방식으로 정렬한 후, 정방향으로 스캔, 역방향으로 스캔하면 볼록다각형의 윗면과 아랫면을 각각 따로 구성할 수 있다.

볼록껍질 문제(Convex Hull), 그라함 스캔(Graham's scan)

그렇게 얻은 좌표는 위 그림과 같다.

 

그럼 S1과 S2를 각각 여러 개의 사다리꼴로 나누어 구할 수 있다. 결과, S1-S2를 해주면 된다.

 

3. 소스코드

# 세 점의 위치관계를 파악
# 양쪽의 볼록껍질을 구성하는데 필요하다.
def ccw(a, b, c):
    k = (b[1]-a[1])*(c[0]-b[0])-(b[0]-a[0])*(c[1]-b[1])
    if k > 0: return 1
    elif k < 0: return -1
    else: return 0

# poly의 넓이를 구한다.
def area(poly):
    poly.sort()
    result = 0
    
    # 왼쪽 껍질의 넓이를 더한다.
    # 평면좌표계에 그대로 적용한다면 사실 왼쪽보단 아래쪽에 가깝다.
    left = []
    for p in poly:
        while len(left) >= 2 and ccw(left[-2],left[-1],p) <= 0:
            left.pop()
        left.append(p)
    for i in range(len(left)-1):
    	# 여기서 넓이를 더하는 이유는
        # left[i+1][0] < left[i][0] 이기 때문에
        # 넓이가 음수로 나온다.
        # 그대로 더해버리면 알아서 S2가 제거된다.
        result += (left[i+1][0]-left[i][0])*(left[i+1][1]+left[i][1])/2
    
    # 오른쪽(위쪽) 껍질의 넓이를 더한다.
    right = []
    for p in reversed(poly):
        while len(right) >= 2 and ccw(right[-2],right[-1],p) <= 0:
            right.pop()
        right.append(p)
    for i in range(len(right)-1):
        result += (right[i+1][0]-right[i][0])*(right[i+1][1]+right[i][1])/2
    
    return result