Intersecció de rectes

En matemàtiques, i més concretament en geometria euclidiana, la intersecció de dues rectes pot ser el conjunt buit, un punt, o una recta. Distingir aquests casos i trobar el punt d'intersecció té utilitat, per exemple, en l'àmbit de la computació gràfica, la planificació de moviment, i la detecció de col·lisions.

Intersecció de rectes

En geometria euclidiana tridimensional, si dues rectes no són al mateix pla, hom diu que les rectes es creuen, i no tenen cap punt d'intersecció. Si les rectes pertanyen al mateix pla, hi ha tres possibilitats: si coincideixen (és a dir, no són rectes diferents) tenen un nombre infinit de punts en comú (coincideixen en tots els seus punts); si són rectes diferents però tenen el mateix pendent, hom diu que les rectes són paral·leles i no tenen cap punt en comú; altrament tenen un sol punt sol d'intersecció.

Les característiques distintives de la geometria no euclidiana són el nombre i la localització de les possibles interseccions entre dues rectes, i el nombre de possibles rectes sense interseccions (rectes paral·leles) respecte una recta donada.

Intersecció de dues rectes

Una condició necessària perquè dues rectes es tallin és que pertanyin al mateix pla; és a dir, que no siguin rectes que es creuen. Aquesta condició és equivalent a què el tetràedre amb vèrtexs a dos dels punts d'una recta i dos dels punts en l'altra sigui degenerat, en el sentit de tenir volum zero. Per a la forma algebraica d'aquesta condició, vegeu l'article Rectes que es creuen#Comprovació.

Donats dos punts sobre cada recta

Considerem primer la intersecció de dues rectes L₁ i L₂ en un espai bidimensional, on la recta L₁ està definida per dos punts diferents (x₁, y₁) i (x₂, y₂), i la recta L₂ està definida per dos punts diferents (x₃, y₃) i (x₄, y₄).

La intersecció P de les rectes L₁ i L₂ es pot definir utilitzant determinants.

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

$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}}}$

Els determinants es poden reescriure com:

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

Cal notar que el punt d'intersecció està definit per a les rectes infinitament llargues determinades pels punts, i no pels segments de recta entre els punts, i es pot produir un punt d'intersecció més enllà de les longituds dels segments de recta. Per tal de trobar la posició de la intersecció dins respecte als segments de recta, es poden definir rectes L₁ i L₂ en termes dels paràmetres de Bézier de primer grau:

$L_{1}={x_{1} \choose y_{1}}+t{x_{2}-x_{1} \choose y_{2}-y_{1}},\qquad L_{2}={x_{3} \choose y_{3}}+u{x_{4}-x_{3} \choose y_{4}-y_{3}}$

(on t i u són nombres reals). El punt d'intersecció de les rectes es troba amb un dels valors següents de t o u:

${\begin{aligned}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})}},\end{aligned}}$

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

amb:

${\begin{aligned}(P_{x},P_{y})&=(x_{1}+t(x_{2}-x_{1}),\;y_{1}+t(y_{2}-y_{1}))\quad {\text{o bé}}\\(P_{x},P_{y})&=(x_{3}+u(x_{4}-x_{3}),\;y_{3}+u(y_{4}-y_{3}))\end{aligned}}$

El punt d'intersecció estarà a l'interior del primer segment de recta si 0 ≤ t ≤ 1, i a l'interior del segon segment de recta si 0 ≤ u ≤ 1. Aquestes desigualtats es poden demostrar sense haver de dividir per t, la qual cosa permet una determinació ràpida de l'existència de qualsevol intersecció de segment de recta abans de calcular-ne el punt exacte.

Quan les dues rectes són paral·leles o coincidents, el denominador és zero:

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

Si les rectes són gairebé paral·leles, aleshores un algorisme computacional podria trobar problemes numèrics a l'hora d'implementar la solució descrita anteriorment: el reconeixement d'aquesta condició pot requerir una comprovació aproximada en una aplicació pràctica. Una aproximació alternativa seria rotar els segments de recta per tal que un d'ells sigui horitzontal, i d'aquí es pot trobar fàcilment la solució de la forma paramètrica girada de la segona recta.

Donades les equacions de les rectes

Les coordenades x i y del punt d'intersecció de dues rectes (que no siguin verticals) es pot trobar de manera senzilla emprant les següents substitucions i manipulacions algebraiques.

Hom suposa primer que les dues rectes tenen equacions y = ax + c i y = bx + d, on a i b són els pendents de les rectes, i c i d són les ordenades a l'origen de les rectes. En el punt on les dues rectes s'intersecten (en cas que es tallin), les dues coordenades y són iguals, i per tant hom pot establir la següent igualtat:

ax + c = bx + d

Es pot manipular algebraicament aquesta expressió per tal de trobar el valor de x:

ax - bx = d - c

i, per tant,

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

Per trobar la coordenada y, tot el que cal és substituir el valor de x a qualsevol de les dues equacions de les rectes; per exemple, a la primera:

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

En conclusió, el punt d'intersecció és

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

Cal notar que si a = b llavors les dues rectes són paral·leles. Si, a més, c ≠ d, les rectes són diferents i no hi ha cap intersecció; altrament, les dues rectes són idèntiques.

Coordenades homogènies

Si s'utilitzen coordenades homogènies, es pot determinar de manera senzilla el punt d'intersecció de dues rectes definides implícitament. En dues dimensions, tot punt es pot definir com una projecció d'un punt en tres dimensions, donat per una terna ordenada (x, y, w). La conversió de coordenades tridimensionals a coordenades bidimensionals és (x', y') = (x/w, y/w). Es poden convertir punts bidimensionals a les seves coordenades homogènies si es defineixen com a (x, y, 1).

Suposi's que hom vol trobar la intersecció de dues rectes infinites en l'espai bidimensional, definides per a₁x + b₁y + c₁ = 0 i a₂x + b₂y + c₂ = 0. Es poden representar aquestes dues rectes en coordenades de la recta com U₁ = (a₁, b₁, c₁) i U₁ = (a₁, b₁, c₁).

Llavors la intersecció P' de les dues rectes ve simplement donat per

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

Intersecció de n rectes

Existència i expressió per a la intersecció

En dues dimensions

En dues dimensions, és gairebé segur que més de dues rectes no s'intersecten en un sol punt. Per tal de determinar si ho fan i, en cas afirmatiu, trobar el punt d'intersecció, hom pot escriure l'equació i-sima (i = 1, ..., n) com $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i}$, i disposar aquestes equacions en forma matricial com a

$Aw=b,$

on la i-sima fila de la matriu A de dimensió n × 2 és $(a_{i1},a_{i2})$, w és el vector de dimensió 2 × 1 (x, y)^T, i l'i-sim element del vector columna b és b_i. Si A té columnes independents, el seu rang és 2. Aleshores existeix una solució de l'equació matricial (i per tant un punt d'intersecció de les n rectes) si i només si el rang de la matriu ampliada (A | b) també és 2. El punt d'intersecció, si existeix, ve donat per

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

on A^g és la pseudoinversa de Moore-Penrose de A (que té la forma indicada perquè A té rang columna complet). Alternativament, hom pot trobar la solució mitjançant la resolució simultània de dues equacions independents qualssevol. Però si el rang de A només és 1, llavors:

• si el rang de la matriu ampliada és 2, llavors no hi ha cap solució
• si el rang de la matriu ampliada és 1, llavors totes les rectes són coincidents

En tres dimensions

El procediment anterior es pot estendre de manera trivial al cas tridimensional. En dimensió 3 o superior, també és cert que és gairebé segur que dues rectes no s'intersecten; si un parell de rectes no es tallen, hom diu són rectes que es creuen. Però si existeix una intersecció, hom pot trobar-ne el punt de la manera següent.

En tres dimensions, una recta es pot representar per la intersecció de dos plans, cadascun dels quals té una equació de la forma $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}$. Així, un conjunt de n rectes es pot representar per 2n equacions, considerant el vector de coordenades tridimensionals w = (x, y, z)^T:

$Aw=b$

on A té ara dimensió 2n × 3 i b té dimensió 2n × 1. Anàlogament al cas anterior, existeix un únic punt d'intersecció si i només si A té rang columna complet i la matriu ampliada (A | b) no, i el punt únic d'intersecció (si existeix) ve donat per

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

Punt més proper a rectes que no s'intersequen

En dimensió 2 o superior, hom pot trobar un punt que sigui el més proper a dues o més rectes, en el sentit de mínims quadrats.

En dues dimensions

En el cas de dimensió 2, primer es representa la recta i com un punt p_i sobre la recta, i es defineix un vector normal unitari ${\hat {n}}_{i}$ perpendicular a aquesta recta. És a dir, si x₁ i x₂ són punts de la recta 1, llavors sigui p₁ = x₁, i sigui

${\hat {n}}_{1}:={1 \over \|x_{2}-x_{1}\|}{\begin{pmatrix}0&-1\\1&0\end{pmatrix}}(x_{2}-x_{1})$

que és el vector unitari al llarg de la recta, rotat 90 graus.

Cal observar que la distància des d'un punt x a la recta $(p,{\hat {n}})$ ve donada per

${\begin{aligned}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)}},\end{aligned}}$

i que el quadrat de la distància des d'un punt x a una recta és

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

La suma dels quadrats de les distàncies a diverses rectes és la funció de pèrdua:

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

Es pot reescriure com:

${\begin{aligned}E(x)&=\sum _{i}\left(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}\right)\\&=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}}$

Per trobar-ne el mínim, cal diferenciar amb respecte a x i igualar el resultat al vector nul:

${\frac {\partial E(x)}{\partial x}}=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)=0$

de tal manera que

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

i per tant

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

En tres dimensions

Encara que ${\hat {n}}_{i}$no està ben definit en dimensió superior a 2, es pot generalitzar a qualsevol dimensió si s'observa que ${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$és la matriu (simètrica) amb tots els valors propis unitaris llevat del valor propi 0 en la direcció de la recta, la qual cosa indueix una seminorma sobre la distància entre p_i i un altre punt que dona la distància a la recta. En un nombre de dimensions qualsevol, si ${\hat {v}}_{i}$ és un vector unitar al llarg de la recta i-sima, llavors

${\hat {n}}_{i}{\hat {n}}_{i}^{\top }$ esdevé $I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }$

on I és la matriu identitat, i per tant

$x=\left(\sum _{i}\left(I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\right)\right)^{-1}\left(\sum _{i}\left(I-{\hat {v}}_{i}{\hat {v}}_{i}^{\top }\right)p_{i}\right).$

Vegeu també

• Distància d'un punt a una recta
• Postulat de les paral·leles
• Intersecció (geometria)
• Rectes que es creuen

Enllaços externs

• Distance between Lines and Segments with their Closest Point of Approach Arxivat 2012-02-27 a Wayback Machine. (anglès), aplicable a dues, tres o més dimensions.