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

В геометрії Евкліда перетином двох прямих може бути порожня множина, точка або пряма. Розрізнення цих випадків і пошук точки перетину використовується, наприклад, в комп'ютерній графіці, при плануванні руху і для виявлення зіткнень.

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

У тривимірної геометрії Евкліда, якщо для двох прямих немає такої площині, якій би вони належали, то вони називаються мимобіжними прямими і не мають точок перетину. Якщо прямі знаходяться в одній площині, то є три можливості. Якщо вони збігаються, вони мають нескінченно багато спільних точок (а саме, всі точки на цих прямих). Якщо прямі різні, але мають один і той же нахил, вони паралельні і не мають спільних точок. В іншому випадку вони мають одну точку перетину.

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

Перетин двох прямих

Необхідною умовою перетину двох прямих є приналежність їх одній площині, тобто ці прямі не повинні бути мимобіжними прямими. Виконання цієї умови еквівалентно виродженості чотиригранника, у якого дві вершини лежать на одній прямій, а дві інші — на іншій (тобто об'єм цього тетраедра дорівнює нулю). Алгебраїчну форму цієї умови можна знайти в статті (Мимобіжні прямі § Перевірка на мимобіжність).

Якщо задані по дві точки на кожній прямій.

Розглянемо перетин двох прямих ${\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})}$.

Точку перетину ${\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 — параметри).

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

${\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}$. Можемо записати ці дві прямі в ^[en] як ${\displaystyle U_{1}=(a_{1},b_{1},c_{1})}$ та ${\displaystyle U_{2}=(a_{2},b_{2},c_{2})}$.

Перетин ${\displaystyle P'}$ двох прямих тоді просто задається формулами:

${\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}$, то прямі не перетинаються.

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

Існування та вираз для перетину

У двомірному просторі

У двомірному просторі, перетин в одній точці трьох і більше прямих майже напевно неможливий. Для того, щоб визначити, чи перетинаються прямі в одній точці, і, якщо перетинаються, для пошуку точки перетину, запишемо 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 — одинична матриця, а тоді:

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

Див. також

• Перетин відрізків
• Проєктивна площина
• Проєкція точки на пряму
• Аксіома паралельності Евкліда
• (Перетин (евклідова геометрія) § Два відрізки)

Примітки

1. Weisstein, Eric W. "Line-Line Intersection." From MathWorld. A Wolfram Web Resource. Процитовано 10 січня 2008.
2. Antonio, Franklin (1992). Chapter IV.6: Faster Line Segment Intersection. У Kirk, David (ред.). Graphics Gems III. Academic Press, Inc. с. 199—202. ISBN .
3. Homogeneous coordinates. robotics.stanford.edu. Процитовано 18 серпня 2015.
4. Traa, Johannes. (PDF). Архів оригіналу (PDF) за 23 листопада 2018. Процитовано 30 серпня 2018.

Посилання

• Відстань між прямими та відрізками з їх найбільш близькою точкою, у вимірах 2, 3 або більше. (англ.)