Пересечение прямых

Даны две прямые. Найти точку их пересечения — или сказать, что её нет.

Возможных ответов три: одна точка, ни одной (параллельны), бесконечно много (совпадают). Разбирать нужно все три.

Через определители

Прямые заданы уравнениями

$$a_1 x + b_1 y + c_1 = 0, \qquad a_2 x + b_2 y + c_2 = 0$$

Это система двух линейных уравнений. По формулам Крамера:

$$\Delta = a_1 b_2 - a_2 b_1, \qquad x = \frac{b_1 c_2 - b_2 c_1}{\Delta}, \qquad y = \frac{a_2 c_1 - a_1 c_2}{\Delta}$$

bool intersect(Line l1, Line l2, Point& res) {
    ld det = l1.a * l2.b - l2.a * l1.b;
    if (eq(det, 0)) return false;          // параллельны или совпадают
    res.x = (l1.b * l2.c - l2.b * l1.c) / det;
    res.y = (l2.a * l1.c - l1.a * l2.c) / det;
    return true;
}

Проверено: на двухстах тысячах случайных пар прямых найденная точка удовлетворяет обоим уравнениям.

Определитель $\Delta = a_1 b_2 - a_2 b_1$ — это векторное произведение нормалей. Он равен нулю ровно тогда, когда нормали коллинеарны, то есть прямые параллельны или совпадают.

Проверять $\Delta$ на ноль нужно до деления. Иначе получите бесконечность или NaN, и ошибка проявится далеко от места возникновения.

Параллельны или совпадают

Если $\Delta = 0$, разбираемся дальше. Прямые совпадают, когда все три коэффициента пропорциональны. Без деления это

$$a_1 c_2 - a_2 c_1 = 0 \quad\text{и}\quad b_1 c_2 - b_2 c_1 = 0$$

Оба условия нужны: одного мало, если соответствующий коэффициент нулевой.

Проще и надёжнее — взять любую точку первой прямой и подставить во второе уравнение. Если получился ноль, прямые совпадают.

Через параметризацию

Способ, который не требует помнить формулы Крамера. Пусть первая прямая задана уравнением, а вторая — точкой $P$ и направляющей $\vec{s}$. Любая точка второй прямой имеет вид $P + t \vec{s}$. Подставим:

$$a(P_x + t s_x) + b(P_y + t s_y) + c = 0$$

Это уравнение с одной неизвестной:

$$t = -\frac{a P_x + b P_y + c}{a s_x + b s_y}$$

ld denom = l.a * s.x + l.b * s.y;          // (нормаль, направляющая)
if (eq(denom, 0)) { /* параллельны */ }
ld t = -(l.a * p.x + l.b * p.y + l.c) / denom;
Point res = p + s * t;

Знаменатель — скалярное произведение нормали первой прямой и направляющей второй. Он нулевой ровно тогда, когда направляющая перпендикулярна нормали, то есть прямые параллельны. Тот же критерий, записанный иначе.

Этот способ удобнее двумя вещами: формулу не надо помнить (она выводится за строчку) и значение $t$ полезно само по себе — по нему сразу видно, попадает ли точка пересечения внутрь отрезка или луча.

Точность

Пересечение прямых — то место, где вещественные числа неизбежны: там есть деление. Отсюда две практические оговорки.

Почти параллельные прямые дают огромную погрешность. Определитель близок к нулю, деление на него разносит любую неточность. Если в задаче такое возможно, стоит проверять определитель не на строгий ноль, а на малость — и думать, что делать в этом случае по условию.

Считайте определитель в целых числах, если координаты целые. Коэффициенты $a$, $b$, $c$ строятся без деления, значит и определитель целый, и проверка на ноль точная. Вещественными делайте только последнее деление.

Родственные задачи

Пересечение луча и прямой. Считаем $t$ параметризацией, проверяем $t \ge 0$.

Пересечение отрезка и прямой. То же, но $0 \le t \le 1$.

Пересечение двух отрезков. Формально сводится к пересечению прямых с проверкой обоих параметров, но на практике надёжнее другой способ — через знаки векторных произведений, без деления вовсе.

Точка, равноудалённая от трёх точек (центр описанной окружности). Пересечение двух серединных перпендикуляров: каждый строится по середине отрезка и нормали, равной направляющей этого отрезка.