AtCoder에서 놀고 있던 곳 "이러한 문제"를 만났다.
그래서 동일 평면상에 존재하는 2선분의 교차 판정 수법에 대해 조사했다.

선분이 교차하는 조건

선분 $AB$ 과 선분 $CD$ 에 대해 생각한다.

(1) 점 $A$ 점 $B$ 를 포함하는 직선 $AB$ 를 경계선으로 하여 평면을 분할할 때 점 $C$ 점 $D$ 가 각각 다른 영역에 존재
(2) 점 $C$ 점 $D$를 포함하는 직선 $CD$를 경계선으로 하여 평면을 분할할 때 점 $A$ 점 $B$가 각각 다른 영역에 존재

(1), (2)의 조건을 모두 만족할 때 선분 $AB$와 선분 $CD$는 교차한다.

점이 존재하는 영역

점 $P$가 평면을 분할하는 직선에 대해 어느 영역에 존재하는지는 직선의 방정식에 점 $P$의 좌표를 대입한 값의 정 부로 판정할 수 있다.

예를 들어, 직선 $x - y = 0$ 에 대한 점 $C$ $(4, -2)$ 의 존재하는 영역을 조사하는 경우
$x - y$ 에 $(x, y) = (4, -2)$ 를 대입하면 $x - y = 6$ $(> 0)$

한편, 직선 $x - y = 0$ 에 대한 점 $D$ $(-4, 2)$ 의 존재하는 영역을 조사하는 경우
$x - y$ 에 $(x, y) = (-4, 2)$ 를 대입하면 $x - y = -6$ $(< 0)$

점 $ C, D $에서 얻은 값의 양수가 다르기 때문에 점 $ C, D $는 다른 영역에 존재한다는 것을 알 수 있습니다.


즉,이 판정

직선 $AB$ 에 대한 점 $C, D$

직선 $CD$ 에 대한 점 $A, B$

로 하면 선분의 교차 판정을 할 수 있다.
(선분의 끝점이 다른 선분 상에 존재하는 경우에 주의)

선분의 교차 판정을 실시하는 알고리즘

우선 점 $A$ $(x_A, y_A),$ 점 $B$ $(x_B, y_B)$ 를 포함한 직선 $AB$ 의 방정식을 구한다.

직선 $AB$의 기울기는 $\frac{y_A - y_B}{x_A - x_B}$

직선 $AB$ 는 점 $A$ 를 포함하기 때문에, 직선 $AB$ 의 방정식은 $y - y_A =\frac{y_A - y_B}{x_A - x_B} (x - x_A)$

식을 변형하면 $(x_A - x_B)(y - y_A) - (y_A - y_B)(x - x_A) = 0$

따라서 점 $C$ $(x_C, y_C),$ 점 $D$ $(x_D, y_D)$ 의 영역 판정을 실시하는 경우

$s = (x_A - x_B)(y_C - y_A) - (y_A - y_B)(x_C - x_A)$
$t = (x_A - x_B)(y_D - y_A) - (y_A - y_B)(x_D - x_A)$

그렇다면 $ st <0 $ 일 때 점 $ C, D $는 직선 $ AB $에 대해 다른 영역에 존재한다고 할 수있다.

상기의 알고리즘을 C++로 기술한 예를 이하에 나타낸다.

typedef struct Point_Coordinates {
    double x, y;
} point;

// 線分ab, cdが交差する場合True
// 端点が他方の線分上にある場合もTrue
// 端点が他方の線分の延長線上にある場合もTrueを返すので注意
int Judge(point &a, point &b, point &c, point &d) {
    double s, t;
    s = (a.x - b.x) * (c.y - a.y) - (a.y - b.y) * (c.x - a.x);
    t = (a.x - b.x) * (d.y - a.y) - (a.y - b.y) * (d.x - a.x);
    if (s * t > 0)
        return false;

    s = (c.x - d.x) * (a.y - c.y) - (c.y - d.y) * (a.x - c.x);
    t = (c.x - d.x) * (b.y - c.y) - (c.y - d.y) * (b.x - c.x);
    if (s * t > 0)
        return false;
    return true;
}

외적을 이용하는 방법

지금까지 직선의 방정식을 이용하여 영역 판정을 행해 왔지만, 외적을 이용하면 간단하게 판정을 행할 수 있다.


2차원 평면에서 벡터 $\vec{a},\vec{b}$ 의 외적 $\vec{a}\times\vec{b}$ 는 $\vec{a}$ 에서 $\vec{b}$ 에의 오른쪽 나사의 방향을 부호로 가지는 스칼라값이 된다.
따라서 선분 $AB, CD$의 교차 판정을 할 경우

$s =\vec{AB}\times\vec{AC} = (x_B - x_A)(y_C - y_A) - (x_C - x_A)(y_B - y_A)$
$t =\vec{AB}\times\vec{AD} = (x_B - x_A)(y_D - y_A) - (x_D - x_A)(y_B - y_A)$

그렇다면 $ st <0 $ 일 때 점 $ C, D $는 직선 $ AB $에 대해 다른 영역에 존재한다고 할 수있다.
또한 이 $st$ 의 값은 선분의 교차 판정을 실시하는 알고리즘 와 같은 값을 취하는 것을 알 수 있다

요약

겉보기 다른 구하는 방법에서도 같은 식이 인도되는 재미