[알고리즘] CCW(Counter Clock Wise)

INDEX

1. 개요

2. 외적

3. 사용

 

1. 개요

외적을 이용해 3개의 점 사이의 관계를 구할 때 사용되는 알고리즘이다. 이 알고리즘을 보고 놀랐던 게, 컴퓨터는 생각보다 인간이 쉽게 할 수 있는 일들을 못한다. 예를 들어 좌표 평면에 존재하는 좌표들의 관계를 파악함에 있어 인간의 인지 능력이 훨씬 직관적으로 정확하다. 

 

ccw알고리즘은 세 가지 상황에 대해 세 가지 값을 return한다. 

• 시계 방향 → ccw<0
• 일직선 → ccw=0
• 반 시계 방향 → ccw>0

2. 외적

외적과 연관이 깊은 알고리즘이고 사실 외적의 원리 그 자체를 이용한다고 해도 과언이 아니다. 

 

외적은 일반적으로 2개의 3차원 공간의 벡터에 대한 연산이다. 스칼라가 나오는 내적과 달리 외적은 크기(스칼라)와 방향(벡터)을 모두 얻을 수 있다. 사실 ccw에서는 방향만이 관심 대상이다. 

 

외적을 아래와 같이 시각화할 수 있다.

교환 법칙이 성립하지 않기 때문에 연산의 순서가 매우 중요하다. 어떤 벡터가 먼저 오냐에 따라 벡터 방향이 바뀌기 때문이다. 오른손 법칙에 의해 오른손 엄지를 제외한 4개의 손가락으로 첫 번째 벡터를 가리키고 두 번째 벡터 방향으로 4개의 손가락을 감쌀 수 있는 방향으로 손을 돌려주면 엄지의 방향이 외적의 방향과 일치한다.

 

3. 사용

그렇다면 위의 개념들을 가지고 어떻게 코드로 옮길 수 있을까? 먼저 점 3개의 좌표가 필요하다. 각 점을 p1, p2, p3라고 하고 각각의 x, y좌표를 x1, y1, x2, y2, x3, y3라고 하자. 또한 p1과 p2를 이은 벡터를 a, p1과 p3를 이은 벡터를 b라고 하자. 

 

따라서 이제 벡터 a와 벡터 b에 대해 외적 연산을 해주면 점 p1, p2, p3가 시계 방향, 직선, 반시계 방향 관계에 있는지 확인할 수 있는 것이다.  

즉 기저 벡터 k에 대한 값이 양수이면 세 점 p1, p2, p3는 차례대로 반시계 관계에 있고 0이면 직선 관계, 음수이면 시계 방향 관계에 있다고 할 수 있다. 이를 전개하고 파이썬 코드로 나타내면 다음과 같다.

x1, y1, x2, y2, x3, y3 = map(int, input().split())

def ccw(x1, y1, x2, y2, x3, y3):
    return x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3

if ccw(x1, y1, x2, y2, x3, y3) > 0:
    print('counter clockwise')
elif ccw(x1, y1, x2, y2, x3, y3) == 0:
    print('one line')
else:
    print('clock wise')