두 선분의 충돌 검사는 기하학적으로 두 선분이 교차하는지를 확인하는 방법이다. 이 과정을 좀 더 정확하게 설명하겠다.

선분 충돌 검사 과정

1. 선분 정의

두 개의 선분을 다음과 같이 정의한다: - 첫 번째 선분 $AB$: 점 $A(x_1, y_1)$와 점 $B(x_2, y_2)$를 연결한 선분. - 두 번째 선분 $CD$: 점 $C(x_3, y_3)$와 점 $D(x_4, y_4)$를 연결한 선분.

2. 벡터 계산

각 선분의 벡터는 다음과 같이 계산된다: - $\overrightarrow{AB} = (x_2 - x_1, y_2 - y_1)$ - $\overrightarrow{CD} = (x_4 - x_3, y_4 - y_3)$

3. 교차 여부 확인

선분이 교차하는지 확인하기 위해 외적(Cross Product) 을 사용한다. 외적을 통해 한 선분이 다른 선분의 양쪽에 있는지를 확인할 수 있다. 이를 위해 다음 절차를 따른다:

3.1. 외적 계산

두 선분의 시작점과 끝점이 서로 반대쪽에 있는지 확인하기 위해 네 개의 외적을 계산한다: - $\text{cross}(A, B, C) = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)$ - $\text{cross}(A, B, D) = (x_2 - x_1)(y_4 - y_1) - (y_2 - y_1)(x_4 - x_1)$ - $\text{cross}(C, D, A) = (x_4 - x_3)(y_1 - y_3) - (y_4 - y_3)(x_1 - x_3)$ - $\text{cross}(C, D, B) = (x_4 - x_3)(y_2 - y_3) - (y_4 - y_3)(x_2 - x_3)$

3.2. 교차 조건

두 선분이 교차하려면 아래 조건이 모두 성립해야 한다: - $\text{cross}(A, B, C) \times \text{cross}(A, B, D) < 0$ - $\text{cross}(C, D, A) \times \text{cross}(C, D, B) < 0$

위 조건이 만족되면, 두 선분은 교차하는 것으로 판단할 수 있다.

4. 결론

• 두 선분이 교차하면 충돌한 것으로 간주한다.
• 교차하지 않으면 충돌하지 않는다고 판단한다.

이 방법은 두 선분이 명확하게 교차하는지를 확인할 수 있으며, 선분이 정확히 한 점에서 교차하는 경우를 처리할 수 있다.