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

1. Якщо задані по дві точки на кожній прямій [ правити | правити код ]
2. Якщо задані рівняння прямих [ правити | правити код ]
3. Використання однорідних координат [ правити | правити код ]
4. Існування і вираз перетину [ правити | правити код ]
5. У тривимірному просторі [ правити | правити код ]
6. Найближча точка до непересічних прямим [ правити | правити код ]
7. У двомірному просторі [ правити | правити код ]
8. У тривимірному просторі [ правити | правити код ]

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

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

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

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

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

Розглянемо перетин двох прямих L 1 {\ displaystyle L_ {1} \,} і L 2 {\ displaystyle L_ {2} \,} на площині, де пряма L 1 {\ displaystyle L_ {1} \,} визначена двома різними точками (x 1, y 1) {\ displaystyle (x_ {1}, y_ {1}) \,} і (x 2, y 2) {\ displaystyle (x_ {2}, y_ {2}) \,} , А пряма L 2 {\ displaystyle L_ {2} \,} - різними точками (x 3, y 3) {\ displaystyle (x_ {3}, y_ {3}) \,} і (x 4, y 4) {\ displaystyle (x_ {4}, y_ {4}) \,} [1] .

Перетин P {\ displaystyle P \,} прямих L 1 {\ displaystyle L_ {1} \,} і L 2 {\ displaystyle L_ {2} \,} можна знайти за допомогою визначників .

P x = | | x 1 y 1 x 2 y 2 | | x 1 + 1 x 2 1 | | x 3 y 3 x 4 y 4 | | x 3 1 x 4 1 | | | | x 1 + 1 x 2 1 | | y 1 + 1 y 2 1 | | x 3 1 x 4 1 | | y 3 1 y 4 1 | | P y = | | x 1 y 1 x 2 y 2 | | y 1 + 1 y 2 1 | | x 3 y 3 x 4 y 4 | | y 3 1 y 4 1 | | | | x 1 + 1 x 2 1 | | y 1 + 1 y 2 1 | | x 3 1 x 4 1 | | y 3 1 y 4 1 | | {\ 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}}} \, \!}

Визначники можна переписати у вигляді:

(P x, P y) = ((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), (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)) {\ 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 - параметри).

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

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

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

Якщо задані рівняння прямих [ правити | правити код ]

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

Припустимо, що дві прямі мають рівняння y = a x + c {\ displaystyle y = ax + c} і y = b x + d {\ displaystyle y = bx + d} , Де a {\ displaystyle a} і b {\ displaystyle b} - кутові коефіцієнти прямих, а c {\ displaystyle c} і d {\ displaystyle d} - перетину прямих з віссю y. У точці перетину прямих (якщо вони перетинаються), обидві координати y {\ displaystyle y} збігатимуться, звідки отримуємо рівність:

a x + c = b x + d {\ displaystyle ax + c = bx + d} .

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

a x - b x = dc {\ displaystyle ax-bx = dc} ,

а тоді

x = dc ab {\ displaystyle x = {\ frac {dc} {ab}}} .

Щоб знайти координату y, все що нам потрібно, це підставити значення x в одну з формул прямих, наприклад, в першу:

y = a dc ab + c {\ displaystyle y = a {\ frac {dc} {ab}} + c} .

Звідси отримуємо точку перетину прямих

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

Зауважимо, що при a = b дві прямі паралельні. Якщо при цьому c ≠ d, прямі різні і не мають перетинів, в іншому ж випадку прямі збігаються [2] .

Використання однорідних координат [ правити | правити код ]

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

Припустимо, що ми хочемо знайти перетин двох нескінченних прямих в 2-вимірному просторі, які задані формулами a 1 x + b 1 y + c 1 = 0 {\ displaystyle a_ {1} x + b_ {1} y + c_ {1} = 0} і a 2 x + b 2 y + c 2 = 0 {\ displaystyle a_ {2} x + b_ {2} y + c_ {2} = 0} . Ми можемо уявити ці дві прямі в лінійних координатах [En] як U 1 = (a 1, b 1, c 1) {\ displaystyle U_ {1} = (a_ {1}, b_ {1}, c_ {1})} і U 2 = (a 2, b 2, c 2) {\ displaystyle U_ {2} = (a_ {2}, b_ {2}, c_ {2})} ,

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

P '= (ap, bp, cp) = U 1 × 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 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})}

Якщо c p = 0 {\ displaystyle c_ {p} = 0} , Прямі не перетинаються.

Існування і вираз перетину [ правити | правити код ]

У двомірному просторі [ правити | правити код ]

У двомірному просторі прямі числом більше двох майже достовірно не перетинаються в одній точці. Щоб визначити, чи перетинаються вони в одній точці, і, якщо перетинаються, щоб знайти точку перетину, запишемо i -е рівняння (i = 1, ..., n) як (ai 1 ai 2) (xy) T = bi, {\ displaystyle (a_ {i1} \ quad a_ {i2}) (x \ quad y) ^ {T} = b_ {i},} і скомпонуємо ці рівняння в матричний вигляд

A w = b, {\ displaystyle Aw = b,}

де i -а рядок n × 2 матриці A дорівнює (a i 1, a i 2) {\ displaystyle (a_ {i1}, a_ {i2})} , W є 2 × 1 вектором (x, y) T, а i -ий елемент вектора-стовпця b дорівнює b i. Великі значення матриці A незалежні, ранг матриці дорівнює 2. Тоді і тільки тоді, коли ранг розширеної матриці [En] [A | b] дорівнює також 2, існує рішення матричного рівняння, а тоді існує і точка перетину n прямих. Точка перетину, якщо така існує, задається формулою

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

де A g {\ displaystyle A ^ {g}} - псевдообернена матриця матриці A {\ displaystyle A} . Альтернативно рішення може бути знайдено шляхом вирішення будь-яких двох незалежних рівнянь. Але якщо ранг матриці A дорівнює 1, а ранг розширеної матриці дорівнює 2, рішень немає. У разі ж, коли ранг розширеної матриці дорівнює 1, всі прямі збігаються.

У тривимірному просторі [ правити | правити код ]

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

У тривимірному просторі пряма представляється перетином двох площин, кожна з яких задається формулою (a i 1 a i 2 a i 3) (x y z) T = b i. {\ Displaystyle (a_ {i1} \ quad a_ {i2} \ quad a_ {i3}) (x \ quad y \ quad z) ^ {T} = b_ {i}.} Тоді безліч n прямих може бути представлено у вигляді 2 n рівнянь від 3-мірного координатного вектора w = (x, y, z) T:

A w = b {\ displaystyle Aw = b} ,

де A - матриця 2 n × 3, а b - 2 n × 1. Як і раніше, єдина точка перетину існує тоді і тільки тоді, коли A має повний ранг по стовпцях, а розширена матриця [A | b] такою не є. Єдина точка перетину, якщо існує, задається формулою

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

Найближча точка до непересічних прямим [ правити | правити код ]

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

У двомірному просторі [ правити | правити код ]

У разі двомірного простору представимо пряму i як точку p i {\ displaystyle p_ {i}} на прямий і одиничну нормаль n ^ i {\ displaystyle {\ hat {n}} _ {i}} , Перпендикулярну прямій. Тобто, якщо x 1 {\ displaystyle x_ {1}} і x 2 {\ displaystyle x_ {2}} - точки на прямій 1, то нехай p 1 = x 1 {\ displaystyle p_ {1} = x_ {1}} і

n ^ 1: = [0 - 1 1 0] (x 2 - x 1) / ‖ x 2 - x 1 ‖ {\ displaystyle {\ hat {n}} _ {1}: = {\ begin {bmatrix} 0 & -1 \\ 1 & 0 \ end {bmatrix}} (x_ {2} -x_ {1}) / \ | x_ {2} -x_ {1} \ |} ,

який є одиничним вектором уздовж прямої, поверненим на 90º.

Зауважимо, що відстань від точки x до прямої (p, n ^) {\ displaystyle (p, {\ hat {n}})} задається формулою

d (x, (p, n)) = ‖ (x - p) ⋅ n ^ ‖ = ‖ (x - p) ⊤ n ^ ‖ = (x - p) ⊤ n ^ n ^ ⊤ (x - p). {\ Displaystyle d (x, (p, n)) = \ | (xp) \ cdot {\ hat {n}} \ | = \ | (xp) ^ {\ top} {\ hat {n}} \ | = {\ sqrt {(xp) ^ {\ top} {\ hat {n}} {\ hat {n}} ^ {\ top} (xp)}}.}

Отже, квадрат відстані від x до прямої дорівнює

d (x, (p, n)) 2 = (x - p) ⊤ (n ^ n ^ ⊤) (x - p). {\ Displaystyle d (x, (p, n)) ^ {2} = (xp) ^ {\ top} ({\ hat {n}} {\ hat {n}} ^ {\ top}) (xp) .}

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

E (x) = Σ i (x - p i) ⊤ (n ^ i n ^ i ⊤) (x - p i). {\ Displaystyle E (x) = \ sum _ {i} (x-p_ {i}) ^ {\ top} ({\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top}) (x-p_ {i}).}

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

E (x) = Σ ix ⊤ n ^ in ^ i ⊤ x - x ⊤ n ^ in ^ i ⊤ pi - pi ⊤ n ^ in ^ i ⊤ x + pi ⊤ n ^ in ^ i ⊤ pi = x ⊤ (Σ in ^ in ^ i ⊤) x - 2 x ⊤ (Σ in ^ in ^ i ⊤ pi) + Σ ipi ⊤ n ^ in ^ i ⊤ pi. {\ Displaystyle {\ begin {aligned} E (x) & = \ sum _ {i} x ^ {\ top} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} xx ^ {\ 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 і прирівняємо результат нулю:

∂ E (x) ∂ x = 0 = 2 (Σ in ^ in ^ i ⊤) x - 2 (Σ in ^ in ^ i ⊤ pi) {\ 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)}

Таким чином,

(Σ in ^ in ^ i ⊤) x = Σ in ^ in ^ i ⊤ pi {\ displaystyle \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} \ right) x = \ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} p_ {i} }

звідки

x = (Σ i n ^ i n ^ i ⊤) - 1 (Σ i n ^ i n ^ i ⊤ 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).}

У тривимірному просторі [ правити | правити код ]

Хоча в размерностях вище двох нормаль n ^ i {\ displaystyle {\ hat {n}} _ {i}} Не визначено, його можна узагальнити на будь-яку розмірність, якщо зауважити, що n ^ in ^ i ⊤ {\ displaystyle {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top} } є просто (симетричною) матрицею з усіма власними значеннями, рівними одиниці, крім нульового власного значення в напрямку прямої, що задає напівнорма між точкою p i {\ displaystyle p_ {i}} і іншою точкою. У просторі будь-якої розмірності, якщо v ^ i {\ displaystyle {\ hat {v}} _ {i}} є одиничним вектором уздовж i -ої прямий, то

n ^ i n ^ i ⊤ {\ displaystyle {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top}} перетворюється в E - v ^ i v ^ i ⊤ {\ displaystyle E - {\ hat {v}} _ {i} {\ hat {v}} _ {i} ^ {\ top}} ,

де E - одинична матриця, а тоді

x = (Σ i E - v ^ i v ^ i ⊤) - 1 (Σ i (E - v ^ i v ^ i ⊤) p i). {\ 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.