[수학] 두 선분의 교차 여부 확인하기

[수학] 두 선분의 교차 여부 확인하기

아래와 같이 두 선분 AB, CD가 존재할 때

A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4)

fn(A, B, C) * fn(A, B, D) < 0 이면 두 선분은 교차합니다. (부호가 다르면)

* 여기서 fn은 두 벡터의 외적 값

   : 두 벡터의 외적의 절대값을 2로 나누면 삼각형의 넓이를 구할 수 있기 때문이다. 단, 여기서는 부호만 판별하면 되므로 2로 나누지 않아도 된다.

즉, 벡터1 = (x2-x1, y2-y1, 0)이고 벡터2 = (x3-x1, y3-y1, 0)일 때

 -> fn(A, B, C) = (x1y2 - x2y1) + (x2y3 - x3y2) + (x3y1 - x1y3)

 -> fn(A, B, D) = (x1y2 - x2y1) + (x2y4 - x4y2) + (x4y1 - x1y4)