Прямые и отрезки

Отрезок можно задать двумя точками своих концов. В любом порядке — ведь он, в отличие от вектора, неориентирован.

struct segment {
    r p, q;
};

В вычислительной геометрии часто требуется уметь определять взаимное положение геометрических объектов. Например, проверять, пересекаются ли отрезки. В этом нам поможет скалярное и векторное произведение, а также небольшой разбор случаев:

В терминах произведений, «концы отрезка лежат по разные стороны относительно другого отрезка», например, записывается как:

Записав ещё одно дополнительное условие, относительно $(M_1, M_2)$ в качестве разделительного отрезка, мы получим легко вычислимый предикат, который верен тогда и только тогда, когда отрезки пересекаются.

#Лучи и прямые

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

С прямыми дела обстоят немного сложнее. Здесь есть целых 4 имеющих право на жизнь способа их хранить:

1. Нормальным уравнением: $A \cdot x + B \cdot y + C = 0$.
2. Двумя точками.
3. Точкой и направляющим вектором (любым): $\vec{r} = \vec{a}t + \vec{b}$.
4. Точкой и нормальным вектором (любым).

Также их иногда удобно хранить уравнением $y = kx + b$, как в школе, однако для вертикальных прямых придётся делать отдельный костыль.

Часто во входе прямые заданы в одном виде, но удобнее работать с другим. Реализуются основные переходы так:

• $2 \rightarrow 1$: достаточно найти любое решение системы из 2 уравнений и 3 неизвестных.
• $1 \rightarrow 3$: если прямая задаётся уравнением, то вектор $\overline{(-B; A)}$ — направляющий к прямой (важно помнить, что у прямой есть два «направления»).
• $1 \rightarrow 4$: если прямая задаётся уравнением, то вектор $\overline{(A; B)}$ — нормальный к прямой (важно помнить, что упрямой есть 2 «направления нормали»).
• $4,3 \rightarrow 1$: нужно решить систему из 1 уравнения и 1 неизвестного, раз уж из предыдущих пунктов мы уже знаем подходящие $A$ и $B$.
• $1 \rightarrow 2$: достаточно выбрать любые две точки на прямой — например:

// даны A, B, C (A^2 + B^2 != 0)
r a, b;
if (eq(A, 0)) // если это горизонтальная прямая
    a = {0, -C/B}, b = {1, -C/B);
else
    a = {-C/A, 0}, b = {-(C+B)/A, 1);

#Проверки

Для способов 2-4 все проверки почти такие же, как для отрезков. На самом деле, в геометрических задачах часто можно ввести «bounding box» — квадрат с очень далекими границами, все точки за пределами которого считаются «бесконечностью». Тогда бесконечные прямые и лучи можно заменить на отрезки, упирающиеся в эти бесконечные границы, и делать все проверки как с обычными отрезками.

В случае прямых, заданных формулой, всё совсем по-другому.

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

Заметим, что если прямая задается уравнением вида $Ax + By + C = 0$, то полуплоскость можно задать таким же неравенством. Это можно сразу использовать для проверки, по какую сторону от прямой находится точка.

Вектор нормали этой прямой будет иметь координаты $(A, B)$. Он перпендикулярен прямой, а в случае с полуплоскостью $Ax + By + C \geq 0$ будет указывать в сторону самой полуплоскости.

Чтобы найти расстояние от точки $(x_0, y_0)$ до прямой $Ax + By + C = 0$, можно воспользоваться следующей формулой:

Об этой формуле можно думать как о скалярном произведении вектора-точки на нормированный ($\frac{1}{\sqrt{A^2+B^2}}$) вектор нормали, геометрически равный проекции точки на него.

Если же прямая задана 2 точками, то можно выразить высоту из формулы для площади треугольника:

Обратите внимание, что в числителе стоит векторное произведение — мы воспользовались тем, что по модулю оно равно удвоенной площади треугольника $\angle PAB$,

#Точка пересечения прямых

Найти точку пересечения двух прямых — это то же самое, что и найти точку, которая удовлетворяет обоим условиям их уравнений:

Аналогично, $x = \frac{B_1 C_2 - B_2 C_1}{A_1 B_2 - A_2 B_1}$ (обратите внимание на знаки).

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

Приведем несколько примеров конструктивного подхода.

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

Чтобы спроецировать точку $P$ на прямую $L$, достаточно прибавить к ней нормальный вектор прямой, приведённый к длине $\rho(P, L)$ и направленный от точки к прямой. Поскольку нормальный вектор может быть направлен в двух разных (но противоположных друг другу!) направлениях, то достаточно попробовать оба варианта, и принять тот, в котором расстояние от получившейся точки до прямой будет меньше.

#Отражение от прямой

Пусть нам надо отразить точку $(x_0, y_0)$ симметрично относительно заданной прямой $ax+by+c=0$.

Чисто в педагогических целях, начнём решать эту задачу как математики, чтобы никогда потом так не делать.

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

Мы не хотим раскрывать эти формулы покоординатно и предъявлять готовый ответ. Мы знаем, что он получится громоздким. Нам не жалко посчитать всё по частям — здесь нет смысла заниматься оптимизациями. Также мы хотим делать всё по частям, потому что так становится более наглядной логика алгоритма, и, как следствие, его проще дебажить.

// прямая r = at + b, точка c
r pr(r a, r b, r c) {
    c -= b; // пусть c и a выходят из одной точки
    return b + (a * b / len(a) / len(a)) * a;
}

r reflect(r a, r b, r c) {
    return c + 2*(pr(a, b, c)-c);
}