Перетин прямих

Розглянемо перетин двох прямих ${\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_{4})}$ та ${\displaystyle (x_{4},y_{4})}$[1].

Точку перетину ${\displaystyle P(P_{x},P_{y})}$ прямих ${\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 — параметри)[2].

Якщо дві прямі є паралельними або збігаються, тоді знаменник дорівнює нулю:

${\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}$ — координати перетину прямих з віссю Oy. У точці перетину прямих (якщо вони перетинаються), обидві координати ${\displaystyle y}$ будуть збігатися, звідки отримуємо рівність:

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

Ми можемо перетворити це рівняння з метою виділення ${\displaystyle x}$:

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

тоді:

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

Для знаходження ${\displaystyle y}$ підставляємо ${\displaystyle 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)}$

Зауважимо, що при ${\displaystyle a=b}$ дві прямі паралельні. Якщо при цьому ${\displaystyle c\neq d}$, прямі різні та не мають перетинів, в іншому ж випадку прямі збігаються.

При використанні однорідних координат точка перетину двох явно заданих прямих може бути знайдена досить просто. У 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-е рівняння прямої ${\displaystyle a_{i1}x+a_{i2}y=b_{i}}$ (i = 1, …, n), як ${\displaystyle (a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},}$ і скомпонуємо ці рівняння в матричному вигляді

${\displaystyle Aw=b,}$

де i-м рядком матриці n × 2 буде ${\displaystyle (a_{i1},a_{i2})}$, відповідно w — це 2 × 1 вектор (x, y)^T, а i-й елемент вектора-стовпця b дорівнює b_i (i = 1, …, n). Якщо матриця 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, всі прямі збігаються.

Представлений вище підхід поширюється на тривимірний простір. У тривимірному та n-вимірних просторах навіть дві прямі майже напевно не перетинаються. Пари непаралельних прямих, які не перетинаються, називаються перехресними. Але коли перетин існує, його можна знайти наступним чином. У тривимірному просторі пряма представляється перетином двох площин, кожна з яких задається формулою ${\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.}$

У двох чи більше вимірах зазвичай можна знайти точку, яка є найближчою до двох чи більше прямих у сенсі найменших квадратів.

У двовимірному просторі спочатку представляють пряму ${\displaystyle 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 }}$є просто (симетричною) матрицею усі власні значення якої дорівнюють 1, за винятком нульового власного значення в напрямку вздовж прямої, яка визначає напівнорму на відстані між точкою ${\displaystyle p_{i}}$ та іншою точкою, на якій досягається відстань до прямої. У просторі довільної вимірності, якщо ${\displaystyle {\hat {v}}_{i}}$ це — одиничний вектор уздовж i-ї лінії, тоді

${\displaystyle {\hat {n}}_{i}{\hat {n}}_{i}^{\top }}$ перетворюється на ${\displaystyle I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }}$

де E — одинична матриця, а тоді[4]:

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

Для того, щоб знайти точку перетину набору прямих, обчислюємо точку з мінімальною відстанню до них. Кожна пряма визначається точкою ${\displaystyle a_{i}}$ та вектором одиничної довжини ${\displaystyle n_{i}}$. Квадрат відстані від точки ${\displaystyle p}$ до однієї з прямих обчислюється за теоремою Піфагора:

${\displaystyle d_{i}^{2}={{\left[\left|\left|p-{{a}_{i}}\right|\right|\right]}^{2}}-{{\left[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}\right]}^{2}}={{\left(p-{{a}_{i}}\right)}^{T}}*\left(p-{{a}_{i}}\right)-{{\left[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}\right]}^{2}}}$

Де: ${\displaystyle {\left(p-a_{i}\right)}^{T}*n_{i}}$ є проєкція:${\displaystyle \left(p-{{a}_{i}}\right)}$ на ${\displaystyle i}$-ту пряму. Сума квадратів відстаней до всіх прямих становить:

${\displaystyle {\underset {i}{\mathop {\sum } }}\,d_{i}^{2}={\underset {i}{\mathop {\sum } }}\,\left[{{\left(p-{{a}_{i}}\right)}^{T}}*\left(p-{{a}_{i}}\right)-{{\left[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}\right]}^{2}}\right]}$.

Щоб мінімізувати цей вираз, візьмемо похідну по ${\displaystyle p}$:

${\displaystyle {\underset {i}{\mathop {\sum } }}\,\left[2*\left(p-{{a}_{i}}\right)-2*\right[{{\left(p-{{a}_{i}}\right)}^{T}}*{{n}_{i}}]*{{n}_{i}}]=0}$

${\displaystyle {\underset {i}{\mathop {\sum } }}\,\left(p-{{a}_{i}}\right)={\underset {i}{\mathop {\sum } }}\,\left[{{n}_{i}}*{{n}_{i}}^{T}\right]*\left(p-{{a}_{i}}\right)}$.

В результаті:

${\displaystyle [{\underset {i}{\mathop {\sum } }}\,\left[{{n}_{i}}*{{n}_{i}}^{T}-I\right]]*p={\underset {i}{\mathop {\sum } }}\,\left[{{n}_{i}}*{{n}_{i}}^{T}-I\right]*{{a}_{i}}}$,

де ${\displaystyle I}$ — цє одинична матриця. Це матриця ${\displaystyle S*p=C}$, з розв'язком ${\displaystyle p={{S}^{+}}*C}$, ${\displaystyle {S}^{+}}$ є псевдообернена матриця до ${\displaystyle S}$.