June 8, 2022

Intersection Point of Lines¶

You are given two lines, described via the equations $a_{1} x + b_{1} y + c_{1} = 0$ and $a_{2} x + b_{2} y + c_{2} = 0$ . We have to find the intersection point of the lines, or determine that the lines are parallel.

Solution¶

If two lines are not parallel, they intersect. To find their intersection point, we need to solve the following system of linear equations:

{\begin{cases} a_{1} x + b_{1} y + c_{1} = 0 \\ a_{2} x + b_{2} y + c_{2} = 0 \end{cases}

Using Cramer's rule, we can immediately write down the solution for the system, which will give us the required intersection point of the lines:

x = - \frac{| \begin{matrix} c_{1} & b_{1} \\ c_{2} & b_{2} \end{matrix} |}{| \begin{matrix} a_{1} & b_{1} \\ a_{2} & b_{2} \end{matrix} |} = - \frac{c_{1} b_{2} - c_{2} b_{1}}{a_{1} b_{2} - a_{2} b_{1}},

y = - \frac{| \begin{matrix} a_{1} & c_{1} \\ a_{2} & c_{2} \end{matrix} |}{| \begin{matrix} a_{1} & b_{1} \\ a_{2} & b_{2} \end{matrix} |} = - \frac{a_{1} c_{2} - a_{2} c_{1}}{a_{1} b_{2} - a_{2} b_{1}} .

If the denominator equals $0$ , i.e.

| \begin{matrix} a_{1} & b_{1} \\ a_{2} & b_{2} \end{matrix} | = a_{1} b_{2} - a_{2} b_{1} = 0

then either the system has no solutions (the lines are parallel and distinct) or there are infinitely many solutions (the lines overlap). If we need to distinguish these two cases, we have to check if coefficients $c$ are proportional with the same ratio as the coefficients $a$ and $b$ . To do that we only have calculate the following determinants, and if they both equal $0$ , the lines overlap:

| \begin{matrix} a_{1} & c_{1} \\ a_{2} & c_{2} \end{matrix} |, | \begin{matrix} b_{1} & c_{1} \\ b_{2} & c_{2} \end{matrix} |

Notice, a different approach for computing the intersection point is explained in the article Basic Geometry.

Implementation¶

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;
}

Contributors:

s9v (64.86%)
jakobkogler (25.68%)
adamant-pwn (8.11%)
tcNickolas (1.35%)