CCW(counter clockwise) 알고리즘

1. CCW 알고리즘 이란

점 A, B, C 세 점이 존재하였을 때, 이 세 점의 방향관계를 구하는 알고리즘이다.

A, B, C를 연결하였을 때, 반시계 방향일 경우 양수를, 시계 방향일 경우 음수를, 직선일 경우 0을 반환한다.

 

 

세 점의 방향관계

이 세점의 방향관계를 구하기 위해서 세 점을 두 개의 벡터로 표현하고, 외적을 통하여 그 값이 음수인지 양수인지 0인지를 확인하는 과정이 필요하다. 그럼 우선 외적에 대해 알아보자.

 

2. 외적

• 두 벡터 A와 B에 모두 수직인 벡터 A X B를 A, B의 외적이라고 정의한다.
• 외적의 크기는 |A||B|sinθ이고, 두 벡터가 만드는 평행사변형의 넓이와 같다.
• 두 벡터의 외적의 방향은 오른손의 법칙을 따른다.
• 교환법칙이 성립하지 않는다. ( A X B != B X A)
• A X B = - (B X A)

두 벡터의 외적은 단위벡터와 행렬식을 통하여 구할 수 있다.

두 벡터 A = (a1, a2, a3), B = (b1, b2, b3)와 단위벡터 E1=(1,0,0), E2=(0,1,0), E3=(0,0,1)가 있을 때, 외적 A X B를 구하는 과정은 다음과 같다.

위의 행렬곱 연산을 하고 나면 결과는 A X B = (a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1)가 나오게 된다.

여기서 오른손의 법칙을 이용하면 외적의 방향을 구할 수 있다.

오른손의 법칙 (출처 : 위키백과)

 

A X B = (a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1) 에서, A와 B를 2차원 XY평면 위에 존재하는 점이라고 한다면(z좌표가 없다면), A X B = (0,0,a1b2 - a2b1)이라고 나타낼 수 있다.

여기서 오른손의 법칙과 위 좌표계를 이용하여 생각해보면, A X B의 z좌표가 양수인 경우는 반시계 방향이고, A X B의 z좌표가 음수인 경우는 시계방향임을 알 수 있다. 

즉, A X B를 통해 구한 z좌표 a1b2 - a2b1이 양수인지 음수인지를 통해 시계방향인지 반시계방향인지를 구할 수 있다.

 

관련 문제는 백준 11758 CCW이다.

[BOJ/Python] 11758_CCW