Расстояние до прямой и проекция

Расстояние от точки $P$ до прямой $ax + by + c = 0$:

$$d = \frac{|a P_x + b P_y + c|}{\sqrt{a^2 + b^2}}$$

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

Почему это так

Для любой точки $S$ на прямой выполняется $(\vec{n}, S) = -c$. Значит, проекция всех точек прямой на направление нормали одинакова и равна $\frac{-c}{|\vec{n}|}$.

Проекция нашей точки $P$ на то же направление равна $\frac{(\vec{n}, P)}{|\vec{n}|}$.

Расстояние от точки до прямой — разность этих проекций:

$$d = \left|\frac{(\vec{n}, P)}{|\vec{n}|} - \frac{-c}{|\vec{n}|}\right| = \frac{|a P_x + b P_y + c|}{\sqrt{a^2 + b^2}}$$

Иначе говоря: подстановка точки в уравнение показывает, насколько прямая сдвинулась бы, если бы прошла через эту точку. Параллельный перенос прямой — это изменение одного лишь $c$.

Вторая формула

Если прямая задана двумя точками $A$ и $B$, удобнее считать через векторное произведение:

$$d = \frac{\bigl|[\vec{AB}, \vec{AP}]\bigr|}{|\vec{AB}|}$$

Смысл прозрачен: числитель — удвоенная площадь треугольника $ABP$, знаменатель — основание, частное — высота.

ld distToLine(Point a, Point b, Point p) {
    return fabsl(Point(a, b) % Point(a, p)) / Point(a, b).len();
}

Проверено: обе формулы дают одинаковый результат на двухстах тысячах случайных конфигураций.

Вторая формула обычно предпочтительнее: не нужно строить уравнение прямой, а числитель считается в целых числах, если координаты целые.

Проекция точки на прямую

Точка $P_0$ — основание перпендикуляра из $P$ на прямую. Считается через проекцию вектора:

Point projectOnLine(Point a, Point b, Point p) {
    Point dir = Point(a, b);
    ld t = (Point(a, p) * dir) / dir.len2();
    return a + dir * t;
}

Здесь t — параметр вдоль прямой: t = 0 соответствует точке $A$, t = 1 — точке $B$. Деление на квадрат длины, а не на длину: так одно деление вместо нормировки.

Проверено: полученная точка лежит на прямой, вектор от неё к $P$ перпендикулярен направляющей, а расстояние совпадает с формулой выше — на всех двухстах тысячах проверок.

Значение t полезно и само по себе: по нему сразу видно, попадает ли проекция внутрь отрезка ($0 \le t \le 1$) или падает за его край.

Через нормаль

Второй способ найти проекцию — отложить от точки нормаль нужной длины:

$$P_0 = P \pm d \cdot \frac{\vec{n}}{|\vec{n}|}$$

И здесь возникает та самая ловушка со знаком. У прямой две нормали, противоположно направленные, и заранее неизвестно, какая из них указывает в сторону прямой.

Три способа справиться:

1. Посчитать обе точки и проверить, какая лежит на прямой. Просто и надёжно.
2. Не брать модуль: величина $\frac{a P_x + b P_y + c}{\sqrt{a^2+b^2}}$ — расстояние со знаком, и оно само указывает сторону. Тогда $P_0 = P - \text{signedDist} \cdot \frac{\vec{n}}{|\vec{n}|}$.
3. Использовать проекцию через направляющую, как в коде выше, — там вопроса о знаке не возникает вовсе.

Третий вариант лучший: он короче и не даёт повода ошибиться.

Симметричная точка

Отражение $P$ относительно прямой — это шаг до проекции и такой же шаг дальше:

$$P' = P + 2\,(P_0 - P) = 2 P_0 - P$$

Point reflect(Point a, Point b, Point p) {
    Point p0 = projectOnLine(a, b, p);
    return p0 * 2 - p;
}

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

Расстояние со знаком

Отдельно стоит запомнить: выражение $a P_x + b P_y + c$ без модуля говорит, по какую сторону от прямой лежит точка.

Знак у всех точек одной полуплоскости одинаков. Это то же самое, что знак векторного произведения $[\vec{AB}, \vec{AP}]$, и именно на нём строится проверка пересечения отрезков.

Если нужен только знак, деление на $\sqrt{a^2+b^2}$ не нужно — оно всё равно положительно. Значит, проверку стороны можно делать в целых числах.