Aizu Online Judge의 Courses를 메우고 있었는데, 2선분의 교점을 구하는 문제를 만났다.
그래서 2선분의 교점 도출 방법을 생각한다.

2선분의 교점 도출 알고리즘

여기에서는 동일 평면상에 존재하고, 병행이 아닌 선분 $AB, CD$ 에 대해 생각한다.
4점 $A, B, C, D$ 의 2차원 좌표가 주어졌을 때의 교점 $X$ 의 좌표를 구하고 싶다.

점 $X$ 는 선분 $AB, CD$ 에 존재하므로 매개 변수 $s, t$ 를 사용하여

X = A + s\vec{AB} = C + t \vec{CD}

라고 표현할 수 있다.


$\vec{AB} = B - A,\vec{CD} = D - C$ 이므로 각 점에 대해 $x, y$ 좌표의 관계식이 구해진다.

\begin{equation}
\left \{
\begin{array}{l}
A_x + s(B_x - A_x) = C_x + t(D_x - C_x) \\
A_y + s(B_y - A_y) = C_y + t(D_y - C_y)
\end{array}
\right.
\end{equation}

이것을 $s, t$ 에 관해서 풀린다.

s = \frac{(C_x - A_x)(D_y - C_y) - (C_y - A_y)(D_x - C_x)}{(B_x - A_x)(D_y - C_y) - (B_y - A_y)(D_x - C_x)} \\
t = \frac{(A_x - C_x)(B_y - A_y) - (A_y - C_y)(B_x - A_x)}{(D_x - C_x)(B_y - A_y) - (D_y - C_y)(B_x - A_x)}

선분 $AB, CD$ 가 병행이 아닌 경우, 이 식보다 2 선분의 끝점 좌표로부터 $s, t$ 의 값이 구해져, 교점의 좌표를 계산할 수 있다.

2선분의 교차 판정

$s, t$의 값으로부터 2선분의 교차 판정을 행할 수 있다.
직선 $AB, CD$ 의 교점이 선분 $AB, CD$ 상에 존재할 때 선분 $AB, CD$ 의 교점이 존재한다고 할 수 있다.
따라서 $s, t$ 가 함께 $[0, 1]$ 의 범위에 들어갈 때 선분 $AB, CD$ 는 교차한다.

0 \leq s, t \leq 1 を満たすとき交差する

매개 변수 s, t의 기하학적 의미

2선분의 교점 도출 알고리즘 에서 얻어진 $s, t$ 의 식을 보면 분모 분자가 함께 외적의 형태를 하고 있다는 것을 깨닫는다.

s = \frac{(C_x - A_x)(D_y - C_y) - (C_y - A_y)(D_x - C_x)}{(B_x - A_x)(D_y - C_y) - (B_y - A_y)(D_x - C_x)}
  = \frac{|\vec{AC} \times \vec{CD}|}{|\vec{AB} \times \vec{CD}|}

2 차원 벡터에서의 외적의 크기는 2 벡터로 구성된 평행 사변형의 면적과 동일하다.
여기서 $\vec {AC},\vec {AB},\vec {CD} $의 관계를 보여줍니다.


$|\vec{AC}\times\vec{CD}|$ 와 같은 면적을 가진 병렬 사변형을 녹색,
$|\vec{AB}\times\vec{CD}|$ 와 같은 면적을 가진 병렬 사변형을 파란색으로 나타내었다.

그림으로 표현해 보면 $|\vec{AC}\times\vec{CD}| = |\vec{AX}\times\vec{CD}|$ 라는 것을 잘 이해할 수 있다.
또한 매개 변수 $ s $가 파란색과 녹색의 평행 사변형의 면적비를 나타냅니다.

C++ 소스 코드

인수에 4점 $A, B, C, D$의 좌표를 건네주면 2선분 $AB, CD$의 교점의 좌표를 돌려주는 함수 Intersection을 C++로 쓴다.

#define INF 1e60
typedef struct Point_Coordinates {
    double x, y;
    friend Point_Coordinates operator-(const Point_Coordinates& l, const Point_Coordinates& r) {
        return { l.x - r.x, l.y - r.y };
    }
} point;

double Cross(const point& a, const point& b) {
    return a.x * b.y - a.y * b.x;
}

point Intersection(const point& a, const point& b, const point& c, const point& d) {
    double s, t, deno = Cross(b - a, d - c);
    point error = { INF, INF };
    if (deno == 0.0) {
        // 線分が平行
        return error;
    }
    s = Cross(c - a, d - c) / deno;
    t = Cross(b - a, a - c) / deno;
    if (s < 0.0 || 1.0 < s || t < 0.0 || 1.0 < t) {
        // 線分が交差していない
        return error;
    }
    return { a.x + s * (b - a).x, a.y + s * (b - a).y };
}

요약

그림으로 나타내면 그 식이 나오는 이유가 비치는 일이 있어 재미있습니다.
AOJ 채우기 여유롭게 노력합니다.