Прямые: различия между версиями
Строка 81: | Строка 81: | ||
$\rho(P, L(A, B)) = \frac{ \overrightarrow{PA} \cdot \overrightarrow{PB}}{|\overrightarrow{(A, B)}|}$ | $\rho(P, L(A, B)) = \frac{ \overrightarrow{PA} \cdot \overrightarrow{PB}}{|\overrightarrow{(A, B)}|}$ | ||
− | Примечание: в числителе стоит косое произведение векторов, оно же | + | Примечание: в числителе стоит косое произведение векторов, оно же cross product. |
===Если прямая задана нормальным уравнением=== | ===Если прямая задана нормальным уравнением=== |
Текущая версия на 17:27, 22 ноября 2021
Содержание
Способы задания прямой
- Нормальным уравнением: $A\cdot x + B \cdot y + C = 0$. В структуре храним (скорее всего в $double$'ах) коэффициенты $A, B, C$.
- Двумя точками. Храним, внезапно, эти 2 точки.
- Точкой и направляющим вектором (любых из них).
- Точкой и нормальным вектором (любым из них).
Важные переходы между способами хранения
- $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$.
Пересечение прямых
Прямые могут:
- Совпадать
- Быть параллельными, но не совпадать
- Пересекаться в одной точке
Научимся отличать эти случаи. Рассуждения ниже приведены для прямых, заданных нормальными уравнениями $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)}|}$
Примечание: в числителе стоит косое произведение векторов, оно же cross 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