이번에는 CCW 알고리즘을 활용해서 다각형의 넓이를 구해보려고 한다.

물론 다각형이 만약 삼각형과 사각형과 같은 단순하고 기본적인 도형이라면 그 넓이를 구하는 방법은 쉬울 것이다. 하지만 만약 50각형,100각형 등등 N각형의 N이 커졌을 때, 그 넓이를 구하는 방법은 생각보다 힘들다.

그래서 CCW를 이용해서 간단하게 N각형의 도형을 구하는 방법을 설명하겠다.

실제로 우리가 구현할 때 방식은 4가지 단계를 거친다.

1. 고정점 한개를 고른다.
2. 고정점을 기준으로 반시계방향으로 2개의 점을 고른 뒤 CCW 코드를 돌린다.
3. 반시계방향으로 점을 바꿔가면서 CCW를 돌려서 그 결과를 누적시킨다.
4. 누적값을 2로 나눈 뒤 절댓값을 씌운다.

우선 CCW를 사용하는 이유는 앞선 포스트에서 CCW의 결과값이 2S였는데 여기서 S에 절대값을 붙이면 그게 바로 삼각형의 넓이가 된다.

저 4가지 단계를 반복 수행하면 N각형의 도형의 넓이를 3각형들의 넓이의 합으로 표현 가능한 것이다.

간단한 예시와 함께 제대로 설명하자면

위와같은 5각형을 생각해보자. 우선 고정점을 C로 잡으면 반시계 방향으로 D,E를 고를 수 있다. 그리고 CCW(C,D,E)를 돌려 결과값을 구한다.

다시 새로 CCW를 돌리기위해 반시계방향으로 한칸 이동하면 D,E에서 E,A로 이동할 것이다. 그러면 다시 C,E,A를 이용해 CCW를 돌려서 결과값을 구한다.

마지막으로 남은 CAB까지 돌린다.

마무리로 총 결과값의 합을 2로 나눈 뒤 절대값을 씌우면 우리가 구하고자하는 5각형의 넓이가 된다.

그런데 사실 지금의 예시는 모든 3개의 점이 같은 방향을 가지고 있기 때문에 CCW의 결과 값의 부호가 모두 같아서 부호를 바꿔준다거나 할 필요가 없다.

하지만 만약 도형이 찌그러져있거나 형태가 이상해져서 어떤 3개의 점은 시계방향이고 다른 3개의 점은 반시계방향일 수도있다. 그때 우리는 어떻게 도형의 넓이를 구해야 할까?

아래의 예시를 통해서 방법을 알아보기로 하자.

이 사진의 경우 고정점을 A라고 했을때 ABC는 시계방향이지만 나머지는 시계 반대방향이다. 일단 우선 규칙대로 CCW를 구하며 진행을 해보자.

처음에 ABC를 이용해서 CCW를 구하게 되면 시계방향이기 때문에 그 결과값이 음수가 나온다. 또한 그 결과값은 사실 도형의 일부가 아니라 도형 밖의 의미없는 부분의 넓이이다.

그리고 ACD를 이용해서 CCW를 돌리면 ACD 또한 의미없는 부분을 포함하는데 그 부분이 ABC의 일부분과 합쳐진다. 이때 ACD는 반시계방향이고 ABC는 시계방향이기 때문에 CCW의 부호가 정반대가되고 즉 겹치는 부분의 값은 부호를 제외하면 같기 때문에 그 부분의 결과값이 상쇄된다.

그러므로 위의 그림과 같이 상쇄되어 결과값들의 누적값은 색칠된 부분에 영향을 미친다.

ADE를 CCW를 돌리면 상쇄되고 남은 나머지 ABC부분과 겹치게 되는데 ADE 또한 ABC와 반대 방향이기 때문에 겹치는 부분이 모두 상쇄된다.

결국에는 우리가 필요한 부분의 결과값만 남게 되기때문에 똑같은 방식으로 도형의 넓이를 구할 수 있게된다.

그러므로 모든 도형에 대해서 이 방식을 사용할 수 있다.

관련문제 - 백준 2166번 다각형의 면적