직선의 교점¶

두 직선이 방정식 $a_1 x + b_1 y + c_1 = 0$과 $a_2 x + b_2 y + c_2 = 0$으로 주어집니다. 두 직선의 교점을 구하거나, 두 직선이 평행함을 판별해야 합니다.

풀이¶

두 직선이 평행하지 않으면 두 직선은 교차합니다. 교점을 구하려면 다음 연립일차방정식을 풀어야 합니다:

$$\begin{cases} a_1 x + b_1 y + c_1 = 0 \\ a_2 x + b_2 y + c_2 = 0 \end{cases}$$

크라메르 공식을 사용하면 연립방정식의 해를 바로 적을 수 있으며, 이 해가 곧 우리가 구하려는 두 직선의 교점입니다:

$$x = - \frac{\begin{vmatrix}c_1 & b_1 \cr c_2 & b_2\end{vmatrix}}{\begin{vmatrix}a_1 & b_1 \cr a_2 & b_2\end{vmatrix} } = - \frac{c_1 b_2 - c_2 b_1}{a_1 b_2 - a_2 b_1},$$

$$y = - \frac{\begin{vmatrix}a_1 & c_1 \cr a_2 & c_2\end{vmatrix}}{\begin{vmatrix}a_1 & b_1 \cr a_2 & b_2\end{vmatrix}} = - \frac{a_1 c_2 - a_2 c_1}{a_1 b_2 - a_2 b_1}.$$

분모가 $0$이면, 즉

$$\begin{vmatrix}a_1 & b_1 \cr a_2 & b_2\end{vmatrix} = a_1 b_2 - a_2 b_1 = 0 $$

연립방정식은 해가 없거나(두 직선이 평행하고 서로 다른 경우) 해가 무수히 많습니다(두 직선이 겹치는 경우). 이 두 경우를 구별해야 한다면, 계수 $c$가 계수 $a$, $b$와 같은 비율로 비례하는지 확인해야 합니다. 이를 위해서는 다음 행렬식들만 계산하면 되며, 둘 다 $0$이면 두 직선은 겹칩니다:

$$\begin{vmatrix}a_1 & c_1 \cr a_2 & c_2\end{vmatrix}, \begin{vmatrix}b_1 & c_1 \cr b_2 & c_2\end{vmatrix} $$

참고로, 교점을 계산하는 다른 방법은 기초 기하 문서에 설명되어 있습니다.

구현¶

struct pt {
    double x, y;
};

struct line {
    double a, b, c;
};

const double EPS = 1e-9;

double det(double a, double b, double c, double d) {
    return a*d - b*c;
}

bool intersect(line m, line n, pt & res) {
    double zn = det(m.a, m.b, n.a, n.b);
    if (abs(zn) < EPS)
        return false;
    res.x = -det(m.c, m.b, n.c, n.b) / zn;
    res.y = -det(m.a, m.c, n.a, n.c) / zn;
    return true;
}

bool parallel(line m, line n) {
    return abs(det(m.a, m.b, n.a, n.b)) < EPS;
}

bool equivalent(line m, line n) {
    return abs(det(m.a, m.b, n.a, n.b)) < EPS
        && abs(det(m.a, m.c, n.a, n.c)) < EPS
        && abs(det(m.b, m.c, n.b, n.c)) < EPS;
}