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

Рассмотрим пересечение двух прямых ${\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 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, прямые различны и не имеют пересечений, в противном же случае прямые совпадают [2].

При использовании однородных координат точка пересечения двух явно заданных прямых может быть найдена достаточно просто. В 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'}$ двух прямых тогда просто задаётся формулами [3]

${\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).}$