Прямые

Способы задания прямой

1. Нормальным уравнением: $A\cdot x + B \cdot y + C = 0$. В структуре храним (скорее всего в $double$'ах) коэффициенты $A, B, C$.
2. Двумя точками. Храним, внезапно, эти 2 точки.
3. Точкой и направляющим вектором (любых из них).
4. Точкой и нормальным вектором (любым из них).

Важные переходы между способами хранения

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

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

Прямые могут:

1. Совпадать
2. Быть параллельными, но не совпадать
3. Пересекаться в одной точке

Научимся отличать эти случаи. Рассуждения ниже приведены для прямых, заданных нормальными уравнениями $A_{i}x + B_{i}y + C_{i}, i \in {1, 2}$. Провести аналогичные рассуждения в случае других способ задания прямых автор оставляет в качестве упражнения читателю.

• Прямые параллельны $\iff$ их нормальные векторы параллельны $\iff \frac{A_1}{A_2} = \frac{B_1}{B_2}$. Проблема этого равенства в том, что оно неопределено в случае, если $A_2 = 0$ или $B_2 = 0$. Перепишем: $A_1 \cdot B_2 = A_2 \cdot B_1$.
• Прямые совпадают $\iff$ их нормальные уравнения пропорциональны $\iff \frac{A_1}{A_2} = \frac{B_1}{B_2} = \frac{C_1}{C_2}$, или, с учётом возможных нулей в знаменателях:

$\underbrace{A_1 \cdot B_2 = A_2 \cdot B_1}_\text{нормальные векторы параллельны} \land B_1 \cdot C_2 = B_2 \cdot C_1 \land A_1 \cdot C_2 = A_2 \cdot C_1$. Здесь важно проверять все три равенства, потому что, например, первых двух недостаточно в случае, когда $B_1=B_2=0$.

• Прямые пересекаются в одной точке $\iff$ они не параллельны, проверять это мы научились в пунктах выше.

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

Код пересечения прямых:

// эта функция находит точку пересечения в случае, если мы знаем, что она ровно одна
pt LineIntersectionPoint(line& L1, line& L2) {
  // здесь должен быть ваш код, решающий систему уравнений
}

bool AreParallel(line& L1, line& L2) {
  return (L1.a * L2.b == L1.b * L2.a);
}

// # точек пересечения + какая-нибудь точка пересечения
pair<int, pt> LineIntersection (line& L1, line& L2) {
  if (AreParallel(L1, L2)) {
    if (L1 == L2) {
      return {3, {L1.GetAnyPoint()}};
    } else {
      return {0, {}};
    }
  }
  
  return {1, LineIntersectionPoint(L1, L2)};
}

Лежат ли точки по разную сторону от прямой?

(в этом разделе мы всё ещё задаём прямую с помощью 2 точек)

Чтобы проверить, лежат ли точки $P_1, P_2$ по разные стороны от прямой, заданной точками $A, B$, достаточно проверить, что повороты от $\overline{AB}$ к $\overline{AP_i}$ разного знака. В этом нам поможет векторное произведение.

int sgn(long long a) {
  if (a < 0) {
    return -1;
  } else if (a > 0) {
    return 1;  
  } else {
    return 0; // нам это не понадобится, но для полноты напишем
  }
}

// эта функция предполагает, что точки не лежат на прямой
bool IsPointsAtDifferentSemiplanes(line& l1, pt& P1, pt& P2) {
  pt A = l1.pts[0];
  pt B = l1.pts[1];

  return sgn(AB % AP1) != sgn(AB % AP2);
}

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

Если прямая задана 2 точками

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

Примечание: в числителе стоит косое произведение векторов, оно же dot product.

Если прямая задана нормальным уравнением

$\rho((x_0, y_0), L_{Ax+By+C=0}) = \frac{|Ax_0 + By_0 + C|}{\sqrt{A^2 + B^2}}$

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

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

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex