CCW를 이용한 선분 교차 판별

CCW를 이용한 선분 교차 판별

• 2차원 좌표 평면 위의 두 선분 $L_1, L_2$가 주어졌을 때, 두 선분이 교차하는지 아닌지 CCW(Counterc-ClockWise)를 이용하여 간단하게 구할 수 있습니다.
• CCW 알고리즘은 3개의 점 $A, B, C$가 있을 때 이 점 3개를 이은 직선의 방향을 알 수 있는 알고리즘입니다.

CCW는 삼각형의 면적을 구하는 공식 + 벡터를 이용하여 아래와 같이 표현할 수 있습니다.

$2 \times S=\begin{vmatrix}x_1&y_1&1\\ x_2&y_2&1\\ x_3&y_3&1 \end{vmatrix}=(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)$

해당 식에서 S가 0보다 크면 반시계 방향, S가 0보다 작으면 시계 방향, S가 0이면 세 점이 평행이란 것을 알 수 있습니다.

이를 소스코드로 작성하면 다음과 같은 함수를 만들 수 있습니다.

def ccw(x1, y1, x2, y2, x3, y3):
  ans = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
  if ans < 0:
    return -1
  elif ans > 0:
    return 1
  else:
    return 0

---

볼록다각형에서 사용할 수 있는 방법

• 위 그림과 같이 선분 $AB, CD$가 있다고 가정하였을 때, $AB, CD$가 교차하는지 확인하는 방법은 선분 $AB$로 선분 $CD$를 확인하는 CCW인 CCW(A, B, C), CCW(A, B, D)를 호출하여 CCW(A, B, C), CCW(A, B, D)의 곱을 확인합니다.
• CCW(A, B, C) * CCW(A, B, D)가 음수이면, 즉 각 함수의 반환값이 0이 아닌 음수와 양수이면 두 선분은 교차하는 것으로 판별할 수 있습니다.
• 만약 값이 0이라면 두 선분은 평행하다고 판별할 수 있습니다.

---

좌표평면에서 사용할 수 있는 방법

하지만 위 그림과 같은 경우도 CCW(A, B, C) * CCW(A, B, D)의 값은 음수이지만, 두 선분 $AB, CD$는 교차하지 않습니다.

따라서 볼록다각형이 아닌 좌표평면에서 두 선분이 교차하는지 판별하는 경우 선분 $AB$에 대해서 선분 $CD$에 대한 CCW만 구하는 것이 아닌, 두 선분에 대한 CCW를 모두 구해주어야 합니다.

따라서 다음과 같은 조건에 의하여 두 선분이 교차한다고 할 수 있습니다.

• CCW(A, B, C) * CCW(A, B, D) <= 0 && CCW(C, D, A) * CCW(C, D, B) <= 0

하지만 이 식을 써도 위 그림과 같은 경우엔 식을 만족하지만 두 선분은 교차하지 않습니다.

두 선분에 대한 CCW를 모두 구했을 때 둘 다 0이 나오지만, 위 그림과 같은 경우인지, 아래 그림과 같은 경우인지 알 방법이 없습니다.

따라서 이런 경우엔 두 선분의 정점의 상대적인 위치를 확인하여 두 선분이 교차하는지 확인할 수 있습니다.

• $B$가 $C$보다 크거나 같고, $A$가 $D$보다 작거나 같으면 두 선분은 교차하게 됩니다.

결과적으로 아래의 식을 만족하면,

$\begin{cases} CCW(A, B, C) \times CCW(A, B, D) <= 0\\ CCW(C, D, A) \times CCW(C, D, B) <= 0\\ A<=D\\ B>=C\\ \end{cases}$

혹은 아래 조건식을 만족하면 좌표평면상에 있는 두 선분은 교차한다고 말할 수 있습니다.

CCW(A, B, C) * CCW(A, B, D) <= 0 && CCW(C, D, A) * CCW(C, D, B) <= 0
A <= D && B >= C