CCW 알고리즘은 2차원 평면 상의 3개의 점의 위치 관계를 알고자 할 때 유용한 기하 알고리즘이다.
2차원 평면상에 세 점으로 만들 수 있는 두 개의 벡터의 방향성(시계 or 반시계)을, 두 벡터의 외적을 통해서 파악할 수 있다.
두 벡터의 외적 결과가 음수이면 시계 방향, 0이면 직선, 양수이면 반시계 방향이 된다.
외적 (벡터 곱) : u x v = |u||v|sin(seta)
두 벡터의 외적 결과는 두 벡터와 수직인 법선 벡터가 된다. (스칼라 x)
외적은 내적(스칼라 곱)과 다르게 교환 법칙이 성립하지 않는다. (a x b != b x a)
두 벡터의 외적 결과의 크기는 두 벡터가 만들어 내는 평행사변형의 넓이와 같다.
두 벡터의 외적 결과의 방향을 알아내기 위해서는 오른손 법칙을 사용하면 된다.
오른손으로 두 벡터를 순서대로 감싸는 방향으로 쥐었을 때, 엄지 손가락이 가리키는 방향이 외적 결과벡터의 방향이 된다.
행렬식을 통해 외적을 계산할 수 있다.
위의 연산식을 이용하여 2차원 평면 상의 세 좌표를 알면, 세 점이 이루는 두 벡터의 방향성을 파악할 수 있다.
def ccw(x1, y1, x2, y2, x3, y3):
cp = (x1*y2+x2*y3+x3*y1)-(x2*y1+x3*y2+x1*y3)
if cp == 0: return 0 # 0이면 직선
elif cp > 0: return 1 # 양수이면 반시계 방향
else:: return -1 # 음수이면 시계 방향