Intersecția liniilor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 13 octombrie 2020; verificările necesită 2 modificări .

În geometria euclidiană, intersecția a două drepte poate fi o mulțime goală , un punct sau o dreaptă. Distingerea acestor cazuri și găsirea punctului de intersecție este folosită, de exemplu, în grafica computerizată , în planificarea mișcării și în detectarea coliziunilor .

În geometria euclidiană tridimensională , dacă două drepte nu sunt în același plan , ele se numesc înclinate și nu au puncte de intersecție. Dacă liniile sunt în același plan, există trei posibilități. Dacă coincid, ele au infinit de puncte în comun (și anume, toate punctele de pe aceste linii). Dacă dreptele sunt distincte, dar au aceeași pantă , ele sunt paralele și nu au puncte comune. În caz contrar, au un punct de intersecție.

În geometria non-euclidiană, două drepte se pot intersecta în mai multe puncte, iar numărul altor linii (paralele) care nu se intersectează cu o dreaptă dată poate fi mai mare decât unul.

Intersecția a două linii

O condiție necesară pentru intersecția a două linii este ca acestea să aparțină aceluiași plan, adică aceste linii să nu se intersecteze. Îndeplinirea acestei condiții este echivalentă cu degenerarea tetraedrului , în care două vârfuri se află pe o linie dreaptă, iar celelalte două se află pe cealaltă (adică volumul acestui tetraedru este egal cu zero). Forma algebrică a acestei condiții poate fi găsită în articolul „ Verificarea încrucișării ”.

Dat două puncte pe fiecare linie

Se consideră intersecția a două drepte și pe plan, unde linia este definită de două puncte diferite și , iar linia este definită de puncte diferite și [1] . $L_{1}\,$ $L_{2}\,$ $L_{1}\,$ $(x_{1},y_{1})\,$ $(x_{2},y_{2})\,$ $L_{2}\,$ $(x_{3},y_{3})\,$ $(x_{4},y_{4})\,$

Intersecția dreptelor și poate fi găsită folosind determinanții . $P\,$ $L_{1}\,$ $L_{2}\,$

P_{x}={\frac {\begin{vmatrix}{\begin{vmatrix}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatrix})&{\ începe{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}{\ începe{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 rescriși astfel:

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

Rețineți că punctul de intersecție se referă la liniile infinite, nu la segmentele de linie dintre puncte și poate fi în afara segmentelor de linie. Dacă (în loc să rezolvăm într-un singur pas) căutăm o soluție în termeni de curbe Bezier de ordinul întâi , atunci putem verifica parametrii acestor curbe 0.0 ≤ t ≤ 1.0 și 0.0 ≤ u ≤ 1.0 ( t și u sunt parametri) .

Dacă două drepte sunt paralele sau coincid, numitorul dispare:

(x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0 .

Dacă liniile sunt foarte aproape de paralele (aproape paralele), pot apărea probleme numerice în calculul computerizat, iar recunoașterea unei astfel de condiții poate necesita un test de „incertitudine” adecvat pentru aplicație. O soluție mai stabilă și mai generală se poate obține prin rotirea segmentelor în așa fel încât unul dintre ele să devină orizontal, iar apoi soluția parametrică a celei de-a doua drepte este ușor de obținut. La rezolvare, este necesară luarea în considerare atentă a cazurilor speciale (paralelism/coincidență a liniilor drepte, suprapunerea segmentelor).

Dacă sunt date ecuații de linii

Coordonatele și punctele de intersecție a două drepte neverticale pot fi găsite cu ușurință folosind următoarele substituții și transformări. $X$ $y$

Să presupunem că două drepte au ecuații și , unde și sunt pantele dreptelor și și sunt intersecțiile dreptelor cu axa y . În punctul de intersecție al dreptelor (dacă se intersectează), ambele coordonate vor coincide, din care obținem egalitatea: $y=ax+c$ $y=bx+d$ $A$ $b$ $c$ $d$ $y$

ax+c=bx+d

Putem transforma această egalitate pentru a evidenția , $X$

ax-bx=dc

și apoi

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

Pentru a găsi coordonata y , tot ce trebuie să facem este să introducem valoarea x într-una dintre formulele liniei, ca prima:

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

De aici obținem punctul de intersecție al liniilor

P\left({\frac {dc}{ab)),a{\frac {dc}{ab)}+c\right)=P\left({\frac {dc}{ab)), {\frac {ad-bc}{ab}}\right)

Rețineți că pentru a = b cele două drepte sunt paralele. Dacă în același timp c ≠ d , liniile sunt diferite și nu au intersecții, în caz contrar liniile coincid [2] .

Utilizarea coordonatelor omogene

Când se utilizează coordonate omogene , punctul de intersecție a două linii date explicit poate fi găsit destul de simplu. În spațiul bidimensional, orice punct poate fi definit ca o proiecție a unui punct tridimensional dat de un triplu . Maparea coordonatelor 3-dimensionale la cele 2-dimensionale are loc conform formulei . Putem converti punctele din spațiul bidimensional în coordonate omogene prin echivalarea celei de-a treia coordonate cu unu - . $(x,y,w)$ $(x',y')=(x/w,y/w)$ $(x,y,1)$

Să presupunem că vrem să găsim intersecția a două linii infinite în spațiul bidimensional, care sunt date de formulele și . Putem reprezenta aceste două linii în coordonate liniare ca , $a_{1}x+b_{1}y+c_{1}=0$ $a_{2}x+b_{2}y+c_{2}=0$ $U_{1}=(a_{1},b_{1},c_{1})$ $U_{2}=(a_{2},b_{2},c_{2})$

Intersecția a două drepte este dată pur și simplu de formulele [3] $P'$

$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ă , liniile nu se intersectează. $c_{p}=0$

Intersecția a n linii

Existența și expresia intersecției

În două dimensiuni

În spațiul bidimensional, liniile cu mai mult de două aproape sigur nu se intersectează la un punct. Pentru a determina dacă se intersectează într-un punct, iar dacă se intersectează, pentru a găsi punctul de intersecție, scriem ecuația i -a ( i = 1, ..., n ) ca și aranjam aceste ecuații sub formă de matrice $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},$

Aw=b,

unde al i -lea rând al matricei n × 2 A este , w este un vector 2 × 1 ( x, y ) T , iar al i -lea element al vectorului coloană b este b i . Dacă coloanele matricei A sunt independente, atunci rangul matricei este 2. Dacă și numai dacă rangul matricei extinse este [ A | b ] este, de asemenea, egal cu 2, există o soluție pentru ecuația matriceală și apoi există și un punct de intersecție a n drepte. Punctul de intersecție, dacă există, este dat de $(a_{i1}, a_{i2})$

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

unde este pseudoinversul matricei . Alternativ, soluția poate fi găsită prin rezolvarea oricăror două ecuații independente. Dar dacă rangul matricei A este 1 și rangul matricei augmentate este 2, nu există soluții. În cazul în care rangul matricei extinse este egal cu 1, toate liniile coincid. $A^{g)$ $A$

În spațiul 3D

Abordarea prezentată mai sus se extinde cu ușurință la spațiul tridimensional. În spațiile tridimensionale și superioare, chiar și două linii aproape sigur nu se intersectează. Perechile de linii neparalele, care nu se intersectează, se numesc oblic . Dar când există o intersecție, aceasta poate fi găsită după cum urmează.

În spațiul tridimensional, o linie dreaptă este reprezentată de intersecția a două plane, fiecare dintre acestea fiind dat de formula Apoi mulțimea de n drepte poate fi reprezentată ca 2 n ecuații dintr-un vector de coordonate tridimensional w = ( x , y , z ) T : $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.$

Aw=b

unde A este o matrice 2n × 3 și b este o matrice 2n × 1. Ca și mai înainte, un punct de intersecție unic există dacă și numai dacă A are rang de coloană complet și matricea augmentată [ A | b ] nu este. Singurul punct de intersecție, dacă există, este dat de

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

Cel mai apropiat punct de liniile care nu se intersectează

În dimensiunile două și mai sus, se poate găsi punctul care este cel mai apropiat de aceste două (sau mai multe) linii în sensul celei mai mici sume de pătrate .

În două dimensiuni

În cazul unui spațiu bidimensional, reprezentați dreapta i ca un punct pe dreptă și o unitate normală perpendiculară pe dreaptă. Adică dacă și sunt puncte pe linia 1, atunci fie și $p_{i}$ ${\pălărie {n}}_{i}$ $x_{1}$ $x_{2}$ $p_{1}=x_{1}$

{\hat {n}}_{1}:={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}(x_{2}-x_{1})/\|x_{ 2}-x_{1}\|

care este vectorul unitar de-a lungul liniei rotite cu 90º.

Rețineți că distanța de la punctul x la linie este dată de formula $(p,{\hat {n))}$

d(x,(p,n))=\|(xp)\cdot {\hat {n))\|=\|(xp)^{\top }{\hat {n))\| ={\sqrt {(xp)^{\top }{\hat {n}}{\hat {n}}^{\top }(xp))).

Prin urmare, pătratul distanței de la x la linie este

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

Suma pătratelor distanțelor față de un set de drepte este funcția obiectiv :

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

Expresia poate fi convertită:

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

Pentru a găsi minimul, diferențiam față de x și setăm rezultatul egal cu zero:

{\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}^{\ sus }p_{i}\dreapta)

În acest fel,

\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)x=\sum _{i} {\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}

Unde

x=\left(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }\right)^{-1}\ stânga(\sum _{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right).

În spațiul 3D

Deși normalul nu poate fi definit în dimensiuni de peste doi , ea poate fi generalizată la orice dimensiune dacă se observă că este pur și simplu o matrice (simetrică) cu toate valorile proprii egale cu unu, cu excepția valorii proprii zero în direcția dreptei , care dă o semi- normă între un punct și un alt punct. Într-un spațiu de orice dimensiune, dacă este un vector unitar de-a lungul liniei drepte i -a, atunci ${\pălărie {n}}_{i}$ ${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$ $p_{i}$ ${\pălărie {v}}_{i}$

{\hat {n}}_{i}{\hat {n}}_{i}^{\top }

se transformă în

E-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }

unde E este matricea identității și apoi

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).

Vezi și

Note

^ Weisstein , Eric W. „Line-Line Intersection”. De la Mathworld . O resursă web Wolfram . Consultat la 10 ianuarie 2008. Arhivat din original la 10 octombrie 2007. (nedefinit)
↑ Calcule similare pot fi găsite în cartea lui Delaunay și Raikov (pp. 202-203)
↑ Coordonate omogene . robotică.stanford.edu . Preluat la 18 august 2015. Arhivat din original la 23 august 2015. (nedefinit)

Literatură

B. N. Delaunay, D. A. Raikov. Geometrie analitică. - M., L.: OGIZ, Editura de stat de literatură tehnică și teoretică, 1948. - T. 1.

Link -uri

Distanța dintre linii și segmente cu cel mai apropiat punct de apropiere al acestora , aplicabilă la două, trei sau mai multe dimensiuni.