CCW (Counter-ClockWise) - (2)

CCW (Counter-ClockWise) - (2)

 

이전 게시글 (CCW (Counter-ClockWise)  https://wogud6792.tistory.com/10)

 

이번 게시글에서는 CCW알고리즘이 어떻게 이용되는지를 알아볼 것이다.

 

우선 CCW 알고리즘 코드는 다음과 같다.

 

 

소개할 내용은 아래와 같이 총 3가지이다.

 

1. 두 선분의 교차 여부

2. 다각형의 넓이

3. 볼록 껍질 (Convex Hull)

 

이 중에서 3. 볼록 껍질은 기하 알고리즘에서 중요한 파트이므로 별도의 게시글로 작성할 예정이다.

 

 

1. 두 선분의 교차 여부

 

평면상에서 어떤 두 선분이 주어졌을 때, 이 두 선분이 교차하고 있는지를 어떻게 판단할까?

 

이는 CCW알고리즘을 이용하면 매우 쉽게 판단할 수 있다.

 

위의 그림과 같이 선분이 교차하게 된다면 선분 AB를 기준으로

나머지 한 선분의 두 꼭짓점이 서로 다른 방향에 위치하게 된다.

즉, C와 D가 선분 AB를 기준으로 반대방향에 위치한다.

 

점 A,B,C는 시계방향의 방향관계를 가지고, 점 A,B,D는 시계반대방향의 방향관계를 가지는 것을 알 수 있다.

따라서 CCW함수의 반환값의 부호가 다르게 나온다.

 

그러므로 CCW(A, B, C) x CCW(A, B, D) < 0을 만족하면 두 선분은 교차하고 있는 것이다.

 

그렇다면 교차하지 않는 경우는 어떨까?

이 경우는 위의 내용에 따르면 CCW(A, B, C) x CCW(A, B, D) > 0을 만족하게 된다.

 

그렇다면 CCW(A, B, C) x CCW(A, B, D) = 0인 경우는 어떤 경우일까?

이 경우는 선분의 두 꼭짓점중 적어도 한 꼭짓점이 다른 선분위에 위치하는 경우이다.

이에 대해서는 직접 그림을 그려봄으로써 쉽게 이해할 수 있다.

 

 

단, 여기서 매우 주의할 점이 있다.

위의 그림같은 경우에는 실제로 두 선분이 만나지 않는 경우이지만,

CCW(A, B, C) x CCW(A, B, D) < 0 을 만족하는 경우이다. 

그러므로 두 '직선'인 경우에는 단순히 두 CCW값의 곱을 통해서 따질 수 있지만

'선분'인 경우에는 위와 같은 경우도 고려를 해주어야 한다! 

 

 

 

2. 다각형의 넓이

 

보통 다각형이라고 한다면 가장 기본적인 삼각형, 사각형 정도를 떠올릴 것이다.

이는 특별한 방법없이 단순한 코딩으로도 넓이를 계산해낼 수 있을 것이다.

하지만, 만약 10각형, 50각형, ... 과 같이 n각형에서 n이 큰 경우나

혹은 모든 내각이 180도 보다 작은 볼록 다각형이 아니라, 오목 다각형인 경우에 대해서는

넓이를 구하기가 다소 난감할 것이다.

 

그러나 CCW 알고리즘을 이용한다면 이 경우도 매우 쉽게 해결할 수 있다.

 

"외적" ( https://wogud6792.tistory.com/11 ) 게시글에서 외적을 통해 나온 식이 삼각형의 넓이를 구하는

"사선 공식"의 식과 동일하다는 것을 언급했다.

 

실제로 세 점 A(x1, y1) , B(x2, y2) , C(x3, y3) 으로 이루어진 삼각형의 넓이는 다음과 같다.

 

<사선 공식>

 

그러므로 CCW 함수의 반환값의 절댓값에 1/2만 곱해주면 된다.

이제 다각형의 넓이를 구하는 과정을 그림을 통해서 알아보자.

 

위와 같은 다각형이 주어진다면, 이 다각형의 넓이는 CCW 알고리즘을 반복해서 사용함으로써 구할 수 있다.

 

1. 고정점을 설정한다.

2. 고정점을 기준으로 시계방향 or 시계반대방향으로 꼭짓점을 돌면서 CCW 알고리즘을 적용한다.

3. 절댓값으로 만든 후 1/2을 곱해준다.

 

점 A를 고정점으로 설정하였고, 시계반대방향으로 꼭짓점을 돌았다.

CCW(A, B, C)의 값은 삼각형 ABC의 넓이의 2배가 나오게 된다. (부호는 일단 무시)

그 다음은 CCW(A,C,D) 를 구한다.

이처럼 점 A는 항상 고정점으로 두고 i번째와 i+1번째 점, i+1번째와 i+2번쨰 점, ... 을 계속해서 CCW함수에 대입한다.

 

CCW(A, D, E)                                                     CCW(A, E, F)

 

이렇게 구한 CCW값들을 모두 더한 후, 절댓값을 씌워 1/2로 나누어주면 다각형의 넓이가 나오게 된다!

(시계 반대방향이므로 ccw의 반환값은 양수이다.

볼록 다각형이기 때문에 중간에 세 점의 방향관계가 바뀌지 않는다는 점을 염두하자)

 

 

그렇다면 만약 중간에 방향관계가 바뀌는 "오목 다각형"인 경우는 어떨까?

사실 이 경우에도 실제 코드에는 변함이 없다.

 

이렇게 크기가 180도보다 큰 내각이 존재하는 다각형을 오목다각형이라고 한다.

 

위의 과정과 마찬가지로 다각형의 넓이를 구할 수 있다.

     

CCW(A, B, C)                           CCW(A, C, D)

 

계속 과정을 적용하여 A, D, E에 대해 CCW를 이용하면 아래와 같이 다각형 외부의 넓이까지 더해지게 된다.

외부의 넓이까지 더하기 때문에 올바르지 않은 과정이라 생각할 수 있지만,

 그 다음 차례인 A,E,F에 대해 CCW를 적용하게 되면 기존의 방향과 반대방향인 시계방향이므로

A,E,F 세 점으로 이루어진 삼각형의 넓이를 빼는 셈이 되는 것이다. (부호가 반대이므로 절댓값의 크기는 작아진다)

그러므로 볼록다각형과 동일하게 순서대로 세 점씩 CCW 함수를 계속 적용하면 넓이를 구할 수 있다.

 

 

 실제 코드 : 백준 알고리즘 2166번 (다각형의 면적) https://wogud6792.tistory.com/13

 

 

피드백은 언제나 환영입니다.