Прямая: три представления

Школьная запись прямой $y = kx + b$ в программе непригодна: вертикальную прямую ей не задать. Коэффициент $k$ — тангенс угла наклона, а у вертикали тангенса нет.

Обходить это условиями («если прямая вертикальная, то…») можно, но каждый такой случай — место для ошибки. Проще взять представление, которое работает всегда.

Общее уравнение

$$ax + by + c = 0$$

Точка $(x, y)$ лежит на прямой тогда и только тогда, когда подстановка даёт ноль.

Переход из школьной формы очевиден: $y = kx + b$ равносильно $kx - y + b = 0$, то есть $a = k$, коэффициент при $y$ равен $-1$, свободный член $b$.

А вот вертикальная прямая теперь задаётся спокойно: $x = 5$ — это $1 \cdot x + 0 \cdot y - 5 = 0$. Горизонтальная — $0 \cdot x + 1 \cdot y - 3 = 0$.

Уравнение определено с точностью до множителя: $2x + 4y - 6 = 0$ и $x + 2y - 3 = 0$ задают одну прямую. Это важно помнить при сравнении прямых на совпадение.

Нормаль

Вектор $\vec{n} = (a, b)$ из коэффициентов уравнения называется нормалью, и он перпендикулярен прямой.

Почему. Возьмём две точки $P$ и $Q$ на прямой. Обе удовлетворяют уравнению, значит $(\vec{n}, P) = -c$ и $(\vec{n}, Q) = -c$. Вычитая, получаем $(\vec{n}, \vec{PQ}) = 0$ — а нулевое скалярное произведение и означает перпендикулярность. Вектор $\vec{PQ}$ идёт вдоль прямой, значит нормаль ей перпендикулярна.

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

Отсюда второе представление: точка на прямой плюс нормаль. По ним уравнение восстанавливается сразу: $c = -(\vec{n}, P)$.

У прямой две нормали, $(a, b)$ и $(-a, -b)$, и какая из них «правильная», не определено. Это регулярно всплывает, когда нужно отложить вектор в конкретную сторону, — об этом отдельно.

Направляющая

Третье представление: точка плюс направляющий вектор $\vec{s}$, идущий вдоль прямой. Тогда любая точка прямой — это

$$P + t \cdot \vec{s}, \qquad t \in \mathbb{R}$$

Такая запись называется параметрической и особенно удобна для лучей и отрезков: ограничив $t$, получаем $t \ge 0$ для луча и $t \in [0, 1]$ для отрезка.

Направляющая и нормаль перпендикулярны, поэтому одна получается из другой поворотом на $90°$.

Переходы

из чего	во что	как
точка $P$ и нормаль $(a, b)$	уравнение	$c = -(a \cdot P_x + b \cdot P_y)$
уравнение	нормаль	$\vec{n} = (a, b)$
нормаль $(a, b)$	направляющая	$\vec{s} = (-b, a)$
направляющая $(s_x, s_y)$	нормаль	$\vec{n} = (-s_y, s_x)$
две точки $P$, $Q$	направляющая	$\vec{s} = \vec{PQ}$

По двум точкам — без деления

Самый частый случай: прямая задана двумя точками, нужно уравнение.

Обе точки удовлетворяют уравнению. Вычтя одно равенство из другого, получаем $a(x_1 - x_2) + b(y_1 - y_2) = 0$. Решений бесконечно много (уравнение определено с точностью до множителя), и нам подойдёт любое:

$$a = y_2 - y_1, \qquad b = x_1 - x_2, \qquad c = -(a x_1 + b y_1)$$

struct Line { long long a, b, c; };

Line lineThrough(Point p, Point q) {
    long long a = q.y - p.y;
    long long b = p.x - q.x;
    return {a, b, -(a * p.x + b * p.y)};
}

Обратите внимание: ни одного деления. Целые координаты дают целые коэффициенты, и вся дальнейшая работа с прямой остаётся точной.

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

Заметьте, что $(a, b) = (y_2 - y_1,\; x_1 - x_2)$ — это в точности направляющая $\vec{PQ}$, повёрнутая на $90°$. Формула не с потолка: это тот же переход из таблицы выше.

Совпадение и параллельность

Две прямые параллельны или совпадают, когда их нормали коллинеарны:

$$a_1 b_2 - a_2 b_1 = 0$$

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

Различить «параллельны» и «совпадают» можно проверкой пропорциональности всех трёх коэффициентов. Надёжнее — без деления: прямые совпадают, если ещё и $a_1 c_2 - a_2 c_1 = 0$ и $b_1 c_2 - b_2 c_1 = 0$.

Нормированная форма

Если поделить уравнение на $\sqrt{a^2 + b^2}$, получится форма, где $a^2 + b^2 = 1$. Тогда $a$ и $b$ — косинус и синус угла нормали, а $-c$ — расстояние от начала координат до прямой.

В задачах эта форма встречается редко (она требует деления и портит точность), но именно из неё естественно выводится формула расстояния от точки до прямой.