Ponto de interseção de linhas

Você recebe duas linhas, descritas pelas equações $a_1 x + b_1 y + c_1 = 0$ e $a_2 x + b_2 y + c_2 = 0$. Temos que encontrar o ponto de interseção das linhas ou determinar se as linhas são paralelas.

Solução

Se duas linhas não são paralelas, elas se cruzam. Para encontrar seu ponto de interseção, precisamos resolver o seguinte sistema de equações lineares:

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

Usando a regra de Cramer, podemos escrever imediatamente a solução para o sistema, o que nos dará o ponto de interseção necessário das linhas:

$$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}.$$

Se o denominador for igual a $0$, ou seja,

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

então, o sistema não tem soluções (as linhas são paralelas e distintas) ou há infinitas soluções (as linhas se sobrepõem). Se precisarmos distinguir esses dois casos, devemos verificar se os coeficientes $c$ são proporcionais com a mesma proporção que os coeficientes $a$ e $b$. Para fazer isso, apenas calculamos os seguintes determinantes e, se ambos forem iguais a $0$, as linhas/retas se sobrepõem:

$$\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} $$

Observe que uma abordagem diferente para calcular o ponto de interseção é explicada em outro artigo.

Implementação

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