Прямые и отрезки - Алгоритмика
Прямые и отрезки

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

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

struct segment {
    r p, q;
};

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

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

$$ [(M_1 - P_1) \times (P_2 - P_1)] \cdot [(M_2 - P_1) \times (P_2 - P_1)] < 0 $$

Записав ещё одно дополнительное условие, относительно $(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$, можно воспользоваться следующей формулой:

$$ d = \frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}} $$

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

Если же прямая задана 2 точками, то можно сделать так:

$$ \rho(P, L(A, B)) = \frac{ \overrightarrow{PA} \cdot \overrightarrow{PB}}{|\overrightarrow{(A, B)}|} $$

Обратите внимание, что в знаменателе стоит скалярное произведение.

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

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

$$ \begin{cases} A_1 x + B_1 y + C_1 = 0 \\ A_2 x + B_2 y + C_2 = 0 \end{cases} $$ Если выразить из обоих уравнений $x$ и приравнять, то получается $$ \begin{cases} -x = \frac{B_1 y + C_1}{A_1} \\ -x = \frac{B_2 y + C_2}{A_2} \end{cases} \implies \frac{B_1 y + C_1}{A_1} = \frac{B_2 y + C_2}{A_2} \implies y = - \frac{A_1 C_2 - A_2 C_1}{A_1 B_2 - A_2 B_1} $$

Аналогично, $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$.

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

$$ \Pr_a b = \frac{a \cdot b}{|a|} \frac{a}{|a|} = \frac{|a| |b| \cos \alpha}{|a|} \frac{a}{|a|} = |b| \cos \alpha \frac{a}{|a|} $$

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

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

// прямая 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);
}