알고리즘 준비하기

🎯 CCW

CCW (Counter Clock Wise) 알고리즘은 3개의 점 A, B, C가 있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 방법이다. 경우의 수는 총 시계방향, 반시계방향, 직선 3가지가 존재한다.

기하와 벡터에서 외적을 사용해서 구한다고 하는데 본인은 문과 수학만 배웠기에 외적에 대해 많은 문서를 읽어봐도 이해가 잘 가지 않았다. 따라서 직선의 방정식을 이용해서 이에 대해 설명하고자 한다.

💎 직선의 방정식 구하기

좌표 A(X1, X2)와 B(X2, Y2)의 직선의 방정식을 구해보자.

Y = (Y2 - Y1) / (X2 - X1) * (X - X1) + Y1

💎 C 대입하기

X2 - X1 값이 양수인 경우 (직선의 방향이 오른쪽인 경우)

Y3 - Y1 = (Y2 - Y1) / (X2 - X1) * (X3 - X1) (직선 방향)

Y3 - Y1 < (Y2 - Y1) / (X2 - X1) * (X3 - X1) (시계 방향)

Y3 - Y1 > (Y2 - Y1) / (X2 - X1) * (X3 - X1) (반시계 방향)

X2 - X1 값이 음수인 경우 (직선의 방향이 왼쪽인 경우)

Y3 - Y1 = (Y2 - Y1) / (X2 - X1) * (X3 - X1) (직선 방향)

Y3 - Y1 < (Y2 - Y1) / (X2 - X1) * (X3 - X1) (반시계 방향)

Y3 - Y1 > (Y2 - Y1) / (X2 - X1) * (X3 - X1) (시계 방향)

💎 통일 시켜서 하나의 식으로 정리하기

X2 - X1 값의 양수 여부에 따라 부등호의 결과가 반대이므로 X2 - X1을 양쪽에 곱해서 부등호를 통일시킨다. 이후 X2 - X1이 양수일 때에는 곱해도 부등호가 유지되고, 음수일 경우는 곱하면 부등호가 반대로 뒤집히는 것을 이용한다.

(Y3 - Y1) * (X2 - X1) = (Y2 - Y1) * (X3 - X1) (직선 방향)

(Y3 - Y1) * (X2 - X1) < (Y2 - Y1) * (X3 - X1) (시계 방향)

(Y3 - Y1) * (X2 - X1) > (Y2 - Y1) * (X3 - X1) (반시계 방향)

💎 코드 구현하기 (JS)

[[X1, Y1], [X2, Y2], [X3, Y3]] = numberArray;

const NUM1 = (Y3 - Y1) * (X2 - X1);
const NUM2 = (Y2 - Y1) * (X3 - X1);

if (NUM1 < NUM2) return -1;
if (NUM1 > NUM2) return 1;
return 0;

🎯 CCW