소개
2차원 평면 위에서 두 선분이 주어졌을 때 두 선분의 교차 여부를 판단하는 알고리즘
아이디어
2차원 평면 상에 3개의 점이 있을 때, 이들을 이루는 방향을 계산해서 두 선분의 교차 여부를 판단한다.
여기서 말하는 3개의 점은 기준이 되는 선분의 양 끝점($P_1$, $P_2$라 하면)과, 나머지 선분의 한 끝점($Q_1$ 또는 $Q_2$)을 말한다.
총 4개의 점인데 왜 3개의 점이냐고 하냐면, 기준이 되는 선분의 양 끝점과 나머지 선분의 한 끝점을 이용해 각각 CCW를 계산하기 때문이다.
알고리즘
3개의 점을 각각 $A(x_1, y_1)$, $B(x_2, y_2)$, $C(x_3, y_3)$ 라고 했을 때, $\vec{AB}$와 $\vec{AC}$의 외적을 계산한다.
$CCW = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)$
CCW의 값에 따라서 A, B, C의 관계를 알 수 있다.
- 양수: 반시계 방향 (CCW)
- 음수: 시계 방향 (CW)
- 0: 일직선
직관적으로 생각하면 A를 기준으로 B를 향해 이동한 뒤 C를 바라보았을 때, 어느 방향으로 회전하는지를 나타낸다고 이해하면 쉽다.
동작 원리
CCW를 사용하면, 세 점이 어떤 방향으로 회전하고 있는지 알 수 있다. 선분 $\overline{P_1P_2}$와 $\overline{Q_1Q_2}$가 있다 할 때, 두 선분이 교차하려면 벡터 $\vec{P_1P_2}$와 $\vec{P_1Q_1}$의 CCW, 그리고 벡터 $\vec{P_1P_2}$와 $\vec{P_1Q_2}$의 CCW가 서로 반대 방향이어야 한다.
하지만 선분은 길이가 한정되어 있으므로, 반대 방향이어도 교차하지 않을 수 있다. 이를 위해서 선분 $\overline{Q_1Q_2}$를 기준으로 CCW 비교를 한번 더 한다.
두 선분이 교차하는지 판단할 때는 네 점에 대해 CCW를 계산한다.
- 선분 $\overline{P_1P_2}$를 기준으로 $Q_1$, $Q_2$가 서로 다른 방향에 위치한다.
- 선분 $\overline{Q_1Q_2}$를 기준으로 $P_1$, $P_2$가 서로 다른 방향에 위치한다.
이를 식으로 쓰면 다음과 같다.
$$ CCW(P_1, P_2, Q_1) \times CCW(P_1, P_2, Q_2) \le 0 $$
$$ CCW(Q_1, Q_2, P_1) \times CCW(Q_1, Q_2, P_2) \le 0 $$
두 곱이 모두 음수라면 두 선분은 확실히 교차한다. 곱이 0인 경우에는 세 점 이상이 일직선 위에 있다는 뜻이므로 추가 확인이 필요하다. 두 선분을 각각 축에 투영했을 때 구간이 겹쳐야 실제로 만나거나 겹치는 선분이다.
즉, 일반적인 선분 교차 판정은 CCW 네 번과 일직선인 경우의 바운딩 박스 검사를 함께 사용해야 한다.
시간/공간 복잡도
CCW 계산과 바운딩 박스 검사는 입력 크기와 관계없이 일정한 횟수만 수행한다.
- Time Complexity: O(1)
- Space Complexity: O(1)