Прямые: различия между версиями
(Новая страница: «==Способы задания прямой== # Нормальным уравнением: $A\cdot x + B \cdot y + C = 0$. В структуре храним (с...») |
|||
Строка 48: | Строка 48: | ||
return {1, LineIntersectionPoint(L1, L2)}; | return {1, LineIntersectionPoint(L1, L2)}; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ==Лежат ли точки по разную сторону от прямой?== | ||
+ | *в этом разделе мы всё ещё задаём прямую с помощью 2 точек* | ||
+ | |||
+ | Чтобы проверить, лежат ли точки $P_1, P_2$ по разные стороны от прямой, заданной точками $A, B$, достаточно проверить, что повороты от $\overline{AB}$ к $\overline{AP_i}$ разного знака. В этом нам поможет векторное произведение. | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | 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); | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
{{Автор|Александр Гришутин|rationalex}} | {{Автор|Александр Гришутин|rationalex}} |
Версия 19:35, 16 декабря 2019
Содержание
Способы задания прямой
- Нормальным уравнением: $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$
- Прямые пересекаются в одной точке $\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);
}
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex