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

В евклидовой геометрии пересечение двух прямых может быть пустым множеством, точкой или прямой. Различение этих случаев и поиск точки пересечения используется, например, в компьютерной графике, при планировании движения^[англ.] и для обнаружения столкновений.

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

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

Необходимым условием пересечения двух прямых является принадлежность их одной плоскости, то есть эти прямые не должны быть скрещивающимися. Выполнение этого условия эквивалентно вырожденности тетраэдра, у которого две вершины лежат на одной прямой, а две другие — на другой (т.е. объём этого тетраэдра равен нулю). Алгебраическую форму этого условия можно посмотреть в статье «Проверка скрещенности».

Рассмотрим пересечение двух прямых ${\displaystyle L_{1}\,}$ и ${\displaystyle L_{2}\,}$ на вещественной плоскости, где прямая ${\displaystyle L_{1}\,}$ определена двумя различными точками ${\displaystyle (x_{1},y_{1})\,}$ и ${\displaystyle (x_{2},y_{2})\,}$, а прямая ${\displaystyle L_{2}\,}$ — различными точками ${\displaystyle (x_{3},y_{3})\,}$ и ${\displaystyle (x_{4},y_{4})\,}$ ^[1].

Пересечение ${\displaystyle P\,}$ прямых ${\displaystyle L_{1}\,}$ и ${\displaystyle L_{2}\,}$ можно найти при помощи определителей.

${\displaystyle P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!\qquad P_{y}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&y_{3}\\x_{4}&y_{4}\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}{\begin{vmatrix}{\begin{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\\{\begin{vmatrix}x_{3}&1\\x_{4}&1\end{vmatrix}}&{\begin{vmatrix}y_{3}&1\\y_{4}&1\end{vmatrix}}\end{vmatrix}}}\,\!}$

Определители можно переписать в виде:

${\displaystyle {\begin{aligned}(P_{x},P_{y})={\bigg (}&{\frac {(x_{1}y_{2}-y_{1}x_{2})(x_{3}-x_{4})-(x_{1}-x_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},\\&{\frac {(x_{1}y_{2}-y_{1}x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}y_{4}-y_{3}x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}{\bigg )}\end{aligned}}}$

Заметим, что точка пересечения относится к бесконечным прямым, а не отрезкам между точками, и она может лежать вне отрезков. Если (вместо решения за один шаг) искать решение в терминах кривых Безье первого порядка, то можно проверить параметры этих кривых 0.0 ≤ t ≤ 1.0 и 0.0 ≤ u ≤ 1.0 (t и u — параметры).

Если две прямые параллельны или совпадают, знаменатель обращается в ноль:

${\displaystyle (x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0.}$

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

Рассмотрим пересечение двух прямых ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$ на комплексной плоскости, где прямая ${\displaystyle L_{1}}$ определена двумя различными точками ${\displaystyle z_{1}}$ и ${\displaystyle z_{2}}$, а прямая ${\displaystyle L_{2}}$ — различными точками ${\displaystyle z_{3}}$ и ${\displaystyle z_{4}}$. Эти прямые ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$ имеют уравнения

${\displaystyle z={\frac {z_{1}+uz_{2}}{1+u}},}$ ${\displaystyle z={\frac {z_{3}+vz_{4}}{1+v}}}$

соответственно^[2].

Правые части равны, если ${\displaystyle z}$ — точка пересечения прямых ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$:

${\displaystyle (1+v)(z_{1}+uz_{2})=(1+u)(z_{3}+vz_{4}),}$

причём это уравнение справедливо и для сопряжённых комплексных чисел^[2]:

${\displaystyle (1+v)({\bar {z}}_{1}+u{\bar {z}}_{2})=(1+u)({\bar {z}}_{3}+v{\bar {z}}_{4}).}$

Выразим из двух последних уравнений значение ${\displaystyle u}$ или ${\displaystyle v}$ и подставим его в уравнение прямой линии соответственно ${\displaystyle L_{1}}$ или ${\displaystyle L_{2}}$, получим уравнение точки пересечения прямых ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$^[2]:

${\displaystyle z={\frac {(z_{1}{\bar {z}}_{2}-{\bar {z}}_{1}z_{2})(z_{3}-z_{4})-(z_{3}{\bar {z}}_{4}-{\bar {z}}_{3}z_{4})(z_{1}-z_{2})}{(z_{1}-z_{2})({\bar {z}}_{3}-{\bar {z}}_{4})-({\bar {z}}_{1}-{\bar {z}}_{2})(z_{3}-z_{4})}}.}$

В случае параллельных прямых линий ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$ знаменатель этого выражения равен нулю по критерию параллельности, то есть ${\displaystyle z=\infty ,}$ что и следовало ожидать^[3].

Упростим уравнение точки пересечения двух прямых, перейдя к векторам прямых. Пусть прямые ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$ задаются соответственно векторами

${\displaystyle p_{1}=2{\frac {z_{2}-z_{1}}{{\bar {z}}_{1}z_{2}-z_{1}{\bar {z}}_{2}}},}$ ${\displaystyle p_{2}=2{\frac {z_{4}-z_{3}}{{\bar {z}}_{3}z_{4}-z_{3}{\bar {z}}_{4}}},}$

которые подставим в уравнение точки пересечения двух прямых и получим следующее более простое уравнение для этой точки^[4]:

${\displaystyle z=2{\frac {p_{2}-p_{1}}{{\bar {p}}_{1}p_{2}-p_{1}{\bar {p}}_{2}}}.}$

Координаты ${\displaystyle x}$ и ${\displaystyle y}$ точки пересечения двух невертикальных прямых можно легко найти с помощью следующих подстановок и преобразований.

Предположим, что две прямые имеют уравнения ${\displaystyle y=ax+c}$ и ${\displaystyle y=bx+d}$, где ${\displaystyle a}$ и ${\displaystyle b}$ — угловые коэффициенты прямых, а ${\displaystyle c}$ и ${\displaystyle d}$ — пересечения прямых с осью y. В точке пересечения прямых (если они пересекаются), обе координаты ${\displaystyle y}$ будут совпадать, откуда получаем равенство:

${\displaystyle ax+c=bx+d}$.

Мы можем преобразовать это равенство с целью выделения ${\displaystyle x}$,

${\displaystyle ax-bx=d-c}$,

а тогда

${\displaystyle x={\frac {d-c}{a-b}}}$.

Чтобы найти координату y, всё что нам нужно, это подставить значение x в одну из формул прямых, например, в первую:

${\displaystyle y=a{\frac {d-c}{a-b}}+c}$.

Отсюда получаем точку пересечения прямых

${\displaystyle P\left({\frac {d-c}{a-b}},a{\frac {d-c}{a-b}}+c\right)=P\left({\frac {d-c}{a-b}},{\frac {ad-bc}{a-b}}\right)}$.

Заметим, что при a = b две прямые параллельны. Если при этом c ≠ d, прямые различны и не имеют пересечений, в противном же случае прямые совпадают ^[5].

При использовании однородных координат точка пересечения двух явно заданных прямых может быть найдена достаточно просто. В 2-мерном пространстве любая точка может быть определена как проекция 3-мерной точки, заданной тройкой ${\displaystyle (x,y,w)}$. Отображение 3-мерных координат в 2-мерные происходит по формуле ${\displaystyle (x',y')=(x/w,y/w)}$. Мы можем преобразовать точки в 2-мерном пространстве в однородные координаты, приравняв третью координату единице — ${\displaystyle (x,y,1)}$.

Предположим, что мы хотим найти пересечение двух бесконечных прямых в 2-мерном пространстве, которые заданы формулами ${\displaystyle a_{1}x+b_{1}y+c_{1}=0}$ и ${\displaystyle a_{2}x+b_{2}y+c_{2}=0}$. Мы можем представить эти две прямые в линейных координатах^[англ.] как ${\displaystyle U_{1}=(a_{1},b_{1},c_{1})}$ и ${\displaystyle U_{2}=(a_{2},b_{2},c_{2})}$,

Пересечение ${\displaystyle P'}$ двух прямых тогда просто задаётся формулами ^[6]

${\displaystyle P'=(a_{p},b_{p},c_{p})=U_{1}\times U_{2}=(b_{1}c_{2}-b_{2}c_{1},a_{2}c_{1}-a_{1}c_{2},a_{1}b_{2}-a_{2}b_{1})}$

Если ${\displaystyle c_{p}=0}$, прямые не пересекаются.

В двумерном пространстве прямые числом больше двух почти достоверно не пересекаются в одной точке. Чтобы определить, пересекаются ли они в одной точке, и, если пересекаются, чтобы найти точку пересечения, запишем i-ое уравнение (i = 1, ...,n) как ${\displaystyle (a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},}$ и скомпонуем эти уравнения в матричный вид

${\displaystyle Aw=b,}$

где i-ая строка n × 2 матрицы A равна ${\displaystyle (a_{i1},a_{i2})}$, w является 2 × 1 вектором (x, y)^T, а i-ый элемент вектора-столбца b равен b_i. Если столбцы матрицы A независимы, ранг матрицы равен 2. Тогда и только тогда, когда ранг расширенной матрицы^[англ.] [A | b ] равен также 2, существует решение матричного уравнения, а тогда существует и точка пересечения n прямых. Точка пересечения, если таковая существует, задаётся формулой

${\displaystyle w=A^{g}b=(A^{T}A)^{-1}A^{T}b,}$

где ${\displaystyle A^{g}}$ — псевдообратная матрица матрицы ${\displaystyle A}$. Альтернативно решение может быть найдено путём решения любых двух независимых уравнений. Но если ранг матрицы A равен 1, а ранг расширенной матрицы равен 2, решений нет. В случае же, когда ранг расширенной матрицы равен 1, все прямые совпадают.

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

В трёхмерном пространстве прямая представляется пересечением двух плоскостей, каждая из которых задаётся формулой ${\displaystyle (a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.}$ Тогда множество n прямых может быть представлено в виде 2n уравнений от 3-мерного координатного вектора w = (x, y, z)^T:

${\displaystyle Aw=b}$,

где A — матрица 2n × 3, а b — 2n × 1. Как и ранее, единственная точка пересечения существует тогда и только тогда, когда A имеет полный ранг по столбцам, а расширенная матрица [A | b ] таковой не является. Единственная точка пересечения, если существует, задаётся формулой

${\displaystyle w=(A^{T}A)^{-1}A^{T}b.}$

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

В случае двумерного пространства представим прямую i как точку ${\displaystyle p_{i}}$ на прямой и единичную нормаль ${\displaystyle {\hat {n}}_{i}}$, перпендикулярную прямой. То есть, если ${\displaystyle x_{1}}$ и ${\displaystyle x_{2}}$ — точки на прямой 1, то пусть ${\displaystyle p_{1}=x_{1}}$ и

${\displaystyle {\hat {n}}_{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}(x_{2}-x_{1})/\|x_{2}-x_{1}\|}$,

который является единичным вектором вдоль прямой, повёрнутым на 90º.

Заметим, что расстояние от точки x до прямой ${\displaystyle (p,{\hat {n}})}$ задаётся формулой

${\displaystyle d(x,(p,n))=\|(x-p)\cdot {\hat {n}}\|=\|(x-p)^{\top }{\hat {n}}\|={\sqrt {(x-p)^{\top }{\hat {n}}{\hat {n}}^{\top }(x-p)}}.}$

Следовательно, квадрат расстояния от x до прямой равен

${\displaystyle d(x,(p,n))^{2}=(x-p)^{\top }({\hat {n}}{\hat {n}}^{\top })(x-p).}$

Сумма квадратов расстояний до набора прямых является целевой функцией:

${\displaystyle E(x)=\sum _{i}(x-p_{i})^{\top }({\hat {n}}_{i}{\hat {n}}_{i}^{\top })(x-p_{i}).}$

Выражение можно преобразовать:

${\displaystyle {\begin{aligned}E(x)&=\sum _{i}x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }x-x^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}-p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }x+p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\\&=x^{\top }\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x-2x^{\top }\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right)+\sum _{i}p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}.\end{aligned}}}$

Чтобы найти минимум, продифференцируем по x и приравняем результат нулю:

${\displaystyle {\frac {\partial E(x)}{\partial x}}=0=2\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x-2\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right)}$

Таким образом,

${\displaystyle \left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x=\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}}$

откуда

${\displaystyle x=\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)^{-1}\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right).}$

Хотя в размерностях выше двух нормаль ${\displaystyle {\hat {n}}_{i}}$ не определить, его можно обобщить на любую размерность, если заметить, что ${\displaystyle {\hat {n}}_{i}{\hat {n}}_{i}^{\top }}$ является просто (симметричной) матрицей со всеми собственными значениями, равными единице, кроме нулевого собственного значения в направлении прямой, что задаёт полунорму между точкой ${\displaystyle p_{i}}$ и другой точкой. В пространстве любой размерности, если ${\displaystyle {\hat {v}}_{i}}$ является единичным вектором вдоль i-ой прямой, то

${\displaystyle {\hat {n}}_{i}{\hat {n}}_{i}^{\top }}$ превращается в ${\displaystyle E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }}$,

где E — единичная матрица, а тогда

${\displaystyle x=\left(\sum _{i}E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\right)^{-1}\left(\sum _{i}(E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top })p_{i}\right).}$

• Пересечение отрезков
• Расстояние от точки до прямой на плоскости
• Аксиома параллельности Евклида

• Б. Н. Делоне, Д. А. Райков. Аналитическая геометрия. — М., Л.: ОГИЗ, Государственнон издательство технико-теоретической литературы, 1948. — Т. 1.
• Zwikker C.^[англ.] The Advanced Geometry of Plane Curves and Their Applications^[англ.]The Advanced Geometry of Plane Curves and Their Applications. New York: Dover Publications, Inc., 1963. 299 p. ISBN 0486610780. ISBN 9780486610788.

• Distance between Lines and Segments with their Closest Point of Approach, applicable to two, three, or more dimensions.