# 선과 선의 충돌 검사

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

#### 선분 충돌 검사 과정

**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. 결론**

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

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