Intersecția a două drepte

În geometria euclidiană intersecția a două drepte poate fi mulțimea vidă, un singur punct sau o dreaptă (dacă coincid). Distingerea acestor cazuri și găsirea intersecției au diferite utilizări, de exemplu în grafica digitală, planificarea mișcării^⁠(d) și detectarea ciocnirilor.

Două drepte care se intersectează

Într-un spațiu euclidian dacă două drepte nu sunt coplanare, ele nu au niciun punct de intersecție.^[1] Dacă sunt coplanare există trei posibilități: dacă coincid (sunt aceeași dreaptă), au în comun toate punctele lor, infinit de multe; dacă sunt distincte, dar au aceeași direcție, se spune că sunt paralele și nu au puncte în comun; în caz contrar, au un singur punct de intersecție.

Relații de calcul

O condiție necesară pentru ca două drepte să se intersecteze este ca acestea să fie în același plan. Îndeplinirea acestei condiții este echivalentă cu situația tetraedrului degenerat, cu vârfuri în două dintre punctele de pe una din drepte și celelalte două vârfuri în cealaltă dreaptă, în sensul de a avea volumul nul.

Drepte date prin câte două puncte

Pentru început se consideră intersecția a două drepte L₁ și L₂ iîn spațiul bidimensional, dreapta L₁ fiind definită prin două puncte distincte (x₁, y₁) și (x₂, y₂), iar dreapta L₂ prin două puncte distincte (x₃, y₃) și (x₄, y₄).^[2]

Intersecția P a dreptelor L₁ și L₂ poate fi definită cu ajutorul determinanților.

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

Determinanții pot fi scriși sub forma:

${\displaystyle {\begin{aligned}P_{x}&={\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})}}\\[4px]P_{y}&={\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})}}\end{aligned}}}$

Dacă două drepte sunt paralele sau coincid, numitorul este nul.

Segmente date prin punctele de la capetele lor

Vezi și: Intersecție (geometrie)#Două_segmente_de_dreaptă.

Punctul de intersecție de mai sus este pentru dreptele infinit de lungi, definite de puncte, în loc de segmente de dreaptă dintre puncte, iar punctul de intersecție poate să nu aparțină niciunuia dintre cele două segmente. Pentru a găsi intersecția segmentelor se pot defini dreptele L₁ și L₂ în funcție de parametrii Bézier de gradul întâi:

${\displaystyle L_{1}={\begin{bmatrix}x_{1}\\y_{1}\end{bmatrix}}+t{\begin{bmatrix}x_{2}-x_{1}\\y_{2}-y_{1}\end{bmatrix}},\qquad L_{2}={\begin{bmatrix}x_{3}\\y_{3}\end{bmatrix}}+u{\begin{bmatrix}x_{4}-x_{3}\\y_{4}-y_{3}\end{bmatrix}}}$

unde t și u sunt numere reale. Punctul de intersecție al liniilor se găsește la una dintre următoarele valori t sau u, unde

${\displaystyle t={\frac {\begin{vmatrix}x_{1}-x_{3}&x_{3}-x_{4}\\y_{1}-y_{3}&y_{3}-y_{4}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}={\frac {(x_{1}-x_{3})(y_{3}-y_{4})-(y_{1}-y_{3})(x_{3}-x_{4})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}}}$

și

${\displaystyle u=-{\frac {\begin{vmatrix}x_{1}-x_{2}&x_{1}-x_{3}\\y_{1}-y_{2}&y_{1}-y_{3}\end{vmatrix}}{\begin{vmatrix}x_{1}-x_{2}&x_{3}-x_{4}\\y_{1}-y_{2}&y_{3}-y_{4}\end{vmatrix}}}=-{\frac {(x_{1}-x_{2})(y_{1}-y_{3})-(y_{1}-y_{2})(x_{1}-x_{3})}{(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})}},}$

cu

${\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{3}+u(x_{4}-x_{3}),\;y_{3}+u(y_{4}-y_{3}){\bigr )}}$

Va exista o intersecție dacă 0 ≤ t ≤ 1 și 0 ≤ u ≤ 1. Punctul de intersecție se află pe primul segment dacă 0 ≤ t ≤ 1 și pe al doilea segment dacă 0 ≤ u ≤ 1. Aceste inegalități pot fi testate fără a face împărțirile, permițând determinarea rapidă a existenței oricărei intersecții a segmentelor înainte de calcularea punctului său exact.^[3]

În cazul în care primul dintre cele două segmente are un punct pe axa x și ${\displaystyle x_{2}=x_{1}+1}$, expresiile pentru ${\displaystyle t}$ și ${\displaystyle u}$ se simplifică la:

${\displaystyle t=u={\frac {y_{1}-y_{3}}{y_{1}-y_{2}-y_{3}+y_{4}}}}$

cu

${\displaystyle (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{1}+t(y_{2}-y_{1}){\bigr )}\quad {\text{or}}\quad (P_{x},P_{y})={\bigl (}x_{1}+t,\;y_{3}+t(y_{4}-y_{3}){\bigr )}}$

Drepte date prin ecuațiile lor

Vezi și: Intersecție (geometrie)#Două_drepte.

Coordonatele x și y ale punctului de intersecție a două drepte care nu sunt verticale pot fi ușor determinate folosind următoarele substituții și rearanjări.

Fie două drepte au ecuațiile y = ax + c și y = bx + d, unde a și b sunt pantele dreptelor și unde c și d sunt intersecțiile cu axa y ale dreptelor. În punctul în care cele două drepte se intersectează (dacă se intersectează), ambele coordonate y vor fi aceleași, de unde următoarea egalitate:

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

Pentru a obține valoarea lui x această expresie se rearanjează:

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

de unde:

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

Pentru a găsi coordonata y se înlocuiește valoarea lui x în oricare dintre cele două ecuații liniare, de exemplu, în prima:

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

Prin urmare, punctul de intersecție este:

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

De observat că dacă a = b atunci cele două drepte sunt paralele și nu se intersectează, cu excepția cazului în care c = d, caz în care dreptele coincid și se intersectează în fiecare punct.

Folosind coordonate omogene

Prin utilizarea coordonatelor omogene, punctul de intersecție a două drepte definite implicit poate fi determinat destul de ușor. În spațiul bidimensional, fiecare punct poate fi definit ca o proiecție a unui punct tridimensional, dat ca triplet ordonat (x, y, w). Aplicarea coordonatelor tridimensionale pe cele bidimensionale este ${\displaystyle (x',y')=\left({\frac {x}{w}},{\frac {y}{w}}\right).}$ Se pot converti punctele bidimensionale în coordonate omogene definindu-le ca (x, y, 1).

Presupunând că se dorește găsirea intersecției a două drepte infinite în spațiul bidimensional, definite ca a₁x + b₁y + c₁ = 0 și a₂x + b₂y + c₂ = 0. Se pot reprezenta aceste două linii în coordonate liniare drept U₁ = (a₁, b₁, c₁) și U₂ = (a₂, b₂, c₂). Intersecția P′ a două drepte este apoi dată de:^[4]

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

Dacă c_p = 0, dreptele nu se intersectează.

Mai multe de două drepte

Intersecția a două drepte poate fi generalizată pentru a trata drepte suplimentare. Existența și expresia pentru problema intersecției a n drepte sunt următoarele.

În două dimensiuni

Într-un spațiu bidimensional este aproape sigur că mai mult de două drepte nu se intersectează într-un singur punct. Pentru a determina dacă se intersectează și, dacă da, pentru a găsi punctul de intersecție, se scrie ecuația (i, i = 1, ... , n) ca:

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}=b_{i}}$

și se aranjează aceste ecuații sub formă de matrice:

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} ,}$

unde linia ia matricei n × 2 A este [a_i1, a_i2], w este vectorul 2 × 1 [x
y], iar elementul i din vectorul coloană b este b_i. Dacă A are coloane independente rangul său este 2. Dacă și numai dacă rangul matricei extinse [A | b] este și el 2, atunci există o soluție a ecuației matriciale, deci un punct de intersecție al celor n drepte. Acest punct, dacă există, este:

${\displaystyle \mathbf {w} =\mathbf {A} ^{\mathrm {g} }\mathbf {b} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} }$

unde A^g este inversa generalizată Moore–Penrose a lui A. Alternativ, soluția poate fi găsită prin rezolvarea împreună a oricăror două ecuații independente. Dar dacă rangul lui A este doar 1, atunci dacă rangul matricei augmentate este 2 nu există soluție, dar dacă rangul său este 1, atunci toate dreptele respective coincid.

În trei dimensiuni

Abordarea de mai sus poate fi extinsă cu ușurință la un spațiu tridimensional. În trei sau mai multe dimensiuni, chiar și două drepte aproape sigur nu se intersectează. Dar dacă există o intersecție, aceasta poate fi găsită după cum urmează.

În trei dimensiuni, o dreaptă este reprezentată prin intersecția a două plane, fiecare dintre ele având o ecuație de forma:

${\displaystyle {\begin{bmatrix}a_{i1}&a_{i2}&a_{i3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}=b_{i}}$

Astfel, un set de n drepte poate fi reprezentat prin 2n ecuații în vectorul de coordonate tridimensional w:

${\displaystyle \mathbf {A} \mathbf {w} =\mathbf {b} }$

unde acum A este o matrice 2n × 3 iar b este una 2n × 1 . Ca și înainte, există un punct unic de intersecție dacă și numai dacă A are un rang egal cu numărul coloanlor sale, iar matricea extinsă [A | b] nu. Unica intersecție, dacă există, este dată de:

${\displaystyle \mathbf {w} =\left(\mathbf {A} ^{\mathsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\mathsf {T}}\mathbf {b} }$

Cele mai apropiate puncte ale dreptelor care nu se intersectează

PQ, cea mai mică distanță între dreptele AB și CD este lungimea segmentului perpendicular pe ambele

În două sau mai multe dimensiuni de obicei putem găsi un punct care este cel mai apropiat de două sau mai multe drepte în sensul metodei celor mai mici pătrate.

În două dimensiuni

În cazul bidimensional, mai întâi se reprezintă dreapta i prin punctul p_i de pe dreaptă și versorul n̂_i, perpendicular pe ea. Adică, dacă x₁ și x₂ sunt puncte de pe drepta 1, atunci fie p₁ = x₁ și fie

${\displaystyle \mathbf {\hat {n}} _{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}{\frac {\mathbf {x} _{2}-\mathbf {x} _{1}}{\|\mathbf {x} _{2}-\mathbf {x} _{1}\|}}}$

care este versorul în direcția dreptei, rotit co 90°.

Distanța de la punctul x la dreapta (p, n̂) este dată de:

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}={\bigl |}(\mathbf {x} -\mathbf {p} )\cdot \mathbf {\hat {n}} {\bigr |}=\left|(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \right|=\left|\mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )\right|={\sqrt {(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}(\mathbf {x} -\mathbf {p} )}}}$

Și astfel, pătratul distanței de la un punct x la o dreaptă este:

${\displaystyle d{\bigl (}\mathbf {x} ,(\mathbf {p} ,\mathbf {\hat {n}} ){\bigr )}^{2}=(\mathbf {x} -\mathbf {p} )^{\mathsf {T}}\left(\mathbf {\hat {n}} \mathbf {\hat {n}} ^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} )}$

Suma pătratelor distanțelor la mai multe drepte este funcția de cost^⁠(d):

${\displaystyle E(\mathbf {x} )=\sum _{i}(\mathbf {x} -\mathbf {p} _{i})^{\mathsf {T}}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)(\mathbf {x} -\mathbf {p} _{i})}$

Aceasta poate fi aranjată sub forma:

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

Pentru a găsi minimul, se derivează în funcție de x și se egalează rezultatul cu vectorul zero:

${\displaystyle {\frac {\partial E(\mathbf {x} )}{\partial \mathbf {x} }}={\boldsymbol {0}}=2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} -2\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)}$

ca urmare:

${\displaystyle \left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {x} =\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}}$

și:

${\displaystyle \mathbf {x} =\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\mathbf {p} _{i}\right)}$

În mai multe de două dimensiuni

Deși n̂_i nu este bine definit în mai multe de două dimensiuni, acest lucru poate fi generalizat la orice număr de dimensiuni observând că n̂_i n̂_i^T este matricea simetrică cu toate valorile proprii egale cu unitatea, cu excepția unei valori proprii nule în direcția de-a lungul dreptei, oferind direcția distanței dintre p_i și un alt punct care dă distanța până la dreaptă. În orice număr de dimensiuni, dacă v̂_i este un versor de-a lungul dreptei i, atunci

${\displaystyle \mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}}$ devine ${\displaystyle \mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}}$

unde I este matricea unitate, iar astfel:^[5]

${\displaystyle x=\left(\sum _{i}\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)^{-1}\left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {v}} _{i}\mathbf {\hat {v}} _{i}^{\mathsf {T}}\right)\mathbf {p} _{i}\right)}$

Obținerea în general

Pentru a găsi punctul de intersecție al unui set de drepte, se calculează punctul cu distanța minimă față de acestea. Fiecare dreaptă este definită de o origine a_i și un versor de direcție n̂_i. Pătratul distanței de la un punct p la una dintre drepte este dat de Pitagora:

${\displaystyle d_{i}^{2}=\left\|\mathbf {p} -\mathbf {a} _{i}\right\|^{2}-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}=\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}$

unde (p − a_i)^T n̂_i este proiecția lui p − a_i pe dreapta i. Suma distanțelor la pătrat pentru toate dreptele este:

${\displaystyle \sum _{i}d_{i}^{2}=\sum _{i}\left({\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}}\left(\mathbf {p} -\mathbf {a} _{i}\right)-{\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)^{2}}\right)}$

Pentru a minimiza această expresie, se derivează în funcție de p, iar derivata se egalează cu 0:

${\displaystyle \sum _{i}\left(2\left(\mathbf {p} -\mathbf {a} _{i}\right)-2\left(\left(\mathbf {p} -\mathbf {a} _{i}\right)^{\mathsf {T}}\mathbf {\hat {n}} _{i}\right)\mathbf {\hat {n}} _{i}\right)={\boldsymbol {0}}}$

${\displaystyle \sum _{i}\left(\mathbf {p} -\mathbf {a} _{i}\right)=\sum _{i}\left(\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\left(\mathbf {p} -\mathbf {a} _{i}\right)}$

di care rezultă:

${\displaystyle \left(\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\right)\mathbf {p} =\sum _{i}\left(\mathbf {I} -\mathbf {\hat {n}} _{i}\mathbf {\hat {n}} _{i}^{\mathsf {T}}\right)\mathbf {a} _{i}}$

unde I este matricea unitate. Aceasta este matricea Sp = C, cu soluția p = S⁺C, unde S⁺ este pseudo-inversa^⁠(d) (inversa generalizată) a lui S.

În geometriile neeuclidiene

Vezi și: Axioma paralelelor.

De la stânga la dreapta: geometrie euclidiană, geometrie sferică și geometrie hiperbolică

Geometriile neeuclidiene, cum ar fi geometria sferică, descriu spații în care o dreaptă poate să nu fie paralelă cu nicio altă dreaptă, respectiv geometria hiperbolică, în care mai multe drepte care trec printr-un singur punct pot fi toate paralele cu o altă dreaptă.^[6]