Пересечение прямых и отрезков

Основные понятия

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

В рамках аналитического подхода каждая прямая описывается математически: её уравнение записывают явно или неявно, что позволяет применять алгебраические методы поиска точек пересечения и проводить анализ особых случаев (параллельность, совпадение).

Уравнения прямых

Наклонно-смещённая форма прямой выражается через угловой коэффициент и свободный член следующим образом: \(y = kx + b\).

Общая (линейная) форма прямой векторно-координатного уравнения имеет вид: \(ax + by + c = 0\).

При поиске точки пересечения двух прямых удобно рассматривать систему их уравнений и решать её алгебраически: \(\begin{cases}a_1 x + b_1 y + c_1 = 0\\ a_2 x + b_2 y + c_2 = 0\end{cases}\).

Решение такой системы через метод детерминантов даёт координаты пересечения при условии ненулевого определителя матрицы коэффициентов: \(x = \dfrac{b_1 c_2 - b_2 c_1}{a_1 b_2 - a_2 b_1}\) и \(y = \dfrac{c_1 a_2 - c_2 a_1}{a_1 b_2 - a_2 b_1}\), где знаменатель определяется как \(D = a_1 b_2 - a_2 b_1\).

Параметрическое представление и векторные формулы

Альтернативный и часто более наглядный способ задания прямой — параметрический: точку на прямой получают как сумму начальной точки и параметра, умноженного на направляющий вектор. Это записывают в компактной векторной форме: \((x,y) = (x_0,y_0) + t(d_x,d_y)\).

Для вычислений в 2D удобно использовать псевдо-скалярную «векторную» операцию, часто называемую поперечным произведением (или псевдовекторным произведением) двух векторов в плоскости. Для двух векторов это выражается формулой: \(\operatorname{cross}((x_1,y_1),(x_2,y_2)) = x_1 y_2 - y_1 x_2\).

Именно через эту операцию вычисляют параметр пересечения двух параметрических прямых: если направляющие векторы не коллинеарны, то параметр одного из них равен частному от соответствующих поперечных произведений; формула для первого параметра выглядит так: \(t = \dfrac{\operatorname{cross}((x_3-x_1,y_3-y_1),(d_x^{(2)},d_y^{(2)}))}{\operatorname{cross}((d_x^{(1)},d_y^{(1)}),(d_x^{(2)},d_y^{(2)}))}\), а для второго параметра — так: \(u = \dfrac{\operatorname{cross}((x_3-x_1,y_3-y_1),(d_x^{(1)},d_y^{(1)}))}{\operatorname{cross}((d_x^{(1)},d_y^{(1)}),(d_x^{(2)},d_y^{(2)}))}\).

Пересечение двух прямых: общие случаи

Системный подход даёт единый критерий существования единственной точки пересечения: ненулевой знаменатель в формулах решения, то есть ненулевой определитель. Это условие записи определителя равного нулю можно формально представить так: \(D = a_1 b_2 - a_2 b_1\). Если это выражение не обращается в ноль, прямые пересекаются в единственной точке, координаты которой вычисляются по формулам, приведённым выше.

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

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

Пересечение отрезков: дополнения к прямым

Отрезок задают как часть прямой между двумя конечными точками; поэтому результаты для прямых дополняются условием, что найденная точка принадлежит обоим отрезкам. В параметрической постановке это означает, что параметры при направляющих векторах должны лежать в отрезке параметров: \(t \in [0,1]\) и \(u \in [0,1]\).

Если прямые коллинеарны, проверка принадлежности отрезков сводится к проверке пересечения проекций отрезков на координатную ось. Это удобно записать через общую проекционную формулу: \(\operatorname{sgn}\left(\operatorname{cross}((x_2-x_1,y_2-y_1),(x_3-x_1,y_3-y_1))\right)\).

Ещё один распространённый подход — ориентирование трёх точек с помощью знака поперечного произведения. Ориентация помогает определять взаимное расположение точек и отрезков: формально выражение ориентации для трёх точек имеет вид \(|D| < \varepsilon\) и используется в алгоритмах пересечения отрезков.

Алгоритм и численные тонкости

При численных вычислениях знаменатель и сравнения с нулём требуют аккуратности из-за погрешностей с плавающей точкой. Поэтому применяют эпсилон-условия: например сравнение по модулю с порогом записывают как \(\varepsilon = 10^{-9}\), где порог можно выбрать, например, равным \(y = 2x + 1\).

Алгоритм нахождения пересечения отрезков в обобщённом виде включает этапы: 1) вычислить знаменатель (детерминант); 2) при ненулевом знаменателе вычислить параметры по формулам через поперечные произведения; 3) проверить принадлежность параметров отрезку параметров по условиям \(t \in [0,1]\) и \(u \in [0,1]\); 4) при нулевом знаменателе проверить коллинеарность и проекции (формула \(\operatorname{sgn}\left(\operatorname{cross}((x_2-x_1,y_2-y_1),(x_3-x_1,y_3-y_1))\right)\)).

При реализации в программировании полезно учитывать случаи, когда точки совпадают, один или оба отрезка вырождаются в точку, и использовать стабильные арифметические операции, чтобы не получить ошибочный результат на границе точного совпадения.

Геометрические случаи и частные положения

Классические частные случаи, которые часто встречаются на задачах: пересечение в единственной точке, отсутствие пересечения (параллельные, разнесённые отрезки), совпадение (полное или частичное перекрытие). Для их различения применяют совокупность проверок: детерминант (или поперечное произведение), проекции и ориентации точек.

Часто в задачах появляется необходимость определить, пересекаются ли отрезки, считая граничные случаи пересечения допустимыми. В этом случае включают равенства в проверках проекций и интервалов параметров (вид \(\operatorname{sgn}\left(\operatorname{cross}((x_2-x_1,y_2-y_1),(x_3-x_1,y_3-y_1))\right)\) и \(t \in [0,1]\)).

При анализе на бумаге удобно сочетать численные вычисления с рисунком (схемой). Для иллюстрации алгоритма можно представить два отрезка и отметить направляющие векторы и искомую точку пересечения, что проясняет порядок вычислений и проверки условий.

Задачи и примеры

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