Intersecció de dos rectes

Intersecció de dos rectes.

En geometria euclidiana, la intersecció de dos rectas pot ser el conjunt buit, un punt o una recta. Distinguir estos casos i trobar el punt d'intersecció tenen us, per eixemple, en computació gràfica, planificació de moviment i detecció de colisions.

En la geometria euclidiana tridimensional, si dos llínees rectes no estan en el mateix pla es diuen rectes que es creuen i no tenen punt d'intersecció. Si estan en el mateix pla, hi ha tres possibilitats: si coincidixen (no són rectes distintes) tenen un número infinit de punts en comú (és dir, tots els punts de qualsevol d'elles); si són distintes pero tenen la mateixa pendent, es diu que són paraleles i no tenen punts en comú; de lo contrari, tenen un únic punt d'intersecció.

Les característiques distintives de les geometria no euclidianas són el número i les ubicacions de les possibles interseccions entre dos rectes i el número de rectes possibles sense interseccions (rectes paraleles) sobre una recta determinada.

Intersecció de dos rectes

Una condició necessària per a que dos rectes es tallen és que estiguen en el mateix pla, és dir, que no siguen rectes que es creuen (intuitivamente en l'espai tridimensional, les rectes que es creuen poden interpretar-se com si estigueren a distint nivell). La satisfacció d'esta condició és equivalent a que un tetraedre en dos vèrtiços en una de les rectes i els atres dos en l'atra, siga un poliedre degenerado en el sentit de tindre volum zero. Per a la forma algebraica d'esta condició, vore rectes que es creuen.

Daus dos punts de cada recta

Primer es considera l'intersecció de dos rectes, $L_{1}$ i $L_{2}$ , en l'espai bidimensional, en la recta $L_{1}$ definida per dos punts distints, $(x_{1}, y_{1})$ i $(x_{2}, y_{2})$ , i la recta $L_{2}$ definida per dos punts distints, $(x_{3}, y_{3})$ i $(x_{4}, y_{4})$ .^[1]

L'intersecció $P$ de la recta $L_{1}$ i $L_{2}$ es pot definir utilisant determinants.

P_{x} = \frac{| \begin{matrix} | \begin{matrix} x_{1} & y_{1} \\ x_{2} & y_{2} \end{matrix} | & | \begin{matrix} x_{1} & 1 \\ x_{2} & 1 \end{matrix} | \\ | \begin{matrix} x_{3} & y_{3} \\ x_{4} & y_{4} \end{matrix} | & | \begin{matrix} x_{3} & 1 \\ x_{4} & 1 \end{matrix} | \end{matrix} |}{| \begin{matrix} | \begin{matrix} x_{1} & 1 \\ x_{2} & 1 \end{matrix} | & | \begin{matrix} y_{1} & 1 \\ y_{2} & 1 \end{matrix} | \\ | \begin{matrix} x_{3} & 1 \\ x_{4} & 1 \end{matrix} | & | \begin{matrix} y_{3} & 1 \\ y_{4} & 1 \end{matrix} | \end{matrix} |} P_{y} = \frac{| \begin{matrix} | \begin{matrix} x_{1} & y_{1} \\ x_{2} & y_{2} \end{matrix} | & | \begin{matrix} y_{1} & 1 \\ y_{2} & 1 \end{matrix} | \\ | \begin{matrix} x_{3} & y_{3} \\ x_{4} & y_{4} \end{matrix} | & | \begin{matrix} y_{3} & 1 \\ y_{4} & 1 \end{matrix} | \end{matrix} |}{| \begin{matrix} | \begin{matrix} x_{1} & 1 \\ x_{2} & 1 \end{matrix} | & | \begin{matrix} y_{1} & 1 \\ y_{2} & 1 \end{matrix} | \\ | \begin{matrix} x_{3} & 1 \\ x_{4} & 1 \end{matrix} | & | \begin{matrix} y_{3} & 1 \\ y_{4} & 1 \end{matrix} | \end{matrix} |}

Els determinants es poden escriure com:

\begin{matrix} (P_{x}, P_{y}) = ( & \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})}) \end{matrix}

Tinga's en conte que per a determinar el punt d'intersecció, s'estan considerant les rectes infinitament llargues definides per cada parell de punts, en lloc dels segments entre els punts, i pot produir un punt d'intersecció més allà de les llongituts dels citats segments. Si (en lloc de resoldre el punt en un sol pas), es troba primer la solució en térmens dels paràmetros de curves de Bézier de primer grau, llavors esta condició entre els segments pot verificar-se per a 0.0 ≤ t ≤ 1.0 i 0.0 ≤ o ≤ 1.0 (a on t i o són les variables directores).

Quan les dos rectes són paraleles o coincidentes, 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 casi paraleles, una solució informàtica pot trobar problemes numèrics en calcular la solució descrita anteriorment: el reconeiximent d'esta condició podria requerir una prova aproximada en una aplicació pràctica. Un enfocament alternatiu podria ser rotar els segments de recta de modo que un d'ells siga horisontal, per lo que la solució de la forma paramètrica rotatòria de la segona llínea s'obté fàcilment. Es requerix una discussió cuidadosa dels casos especials (rectes paraleles/coincidentes, intervals superposts/no superposts).

Donades les equacions de les rectes

Les coordenades $x$ i $y$ del punt d'intersecció de dos rectes no verticals es poden trobar fàcilment usant les següents substitucions i reordenamientos.

Suponga's que dos rectes tenen les equacions $y = a x + c$ i $y = b x + d$ , a on $a$ i $b$ són les pendents (gradient) de les rectes i a on $c$ i $d$ són els corts en l'eix i de les rectes. En el punt a on les dos rectes es creuen (si ho fan), abdós coordenades $y$ seran la mateixa, d'ahí la següent igualtat:

a x + c = b x + d

.

Es pot reorganisar esta expressió per a extraure el valor de $x$ ,

a x - b x = d - c

,

i llavors,

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

.

Per a trobar la coordenada i, tot lo que es té que fer és substituir el valor de x en una de les dos equacions, per eixemple, en la primera:

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

.

Per lo tant, el punt d'intersecció és

P (\frac{d - c}{a - b}, a \frac{d - c}{a - b} + c) = P (\frac{d - c}{a - b}, \frac{a d - b c}{a - b})

.

Observe's que si a = b, llavors les dos rectes són paraleles. Si també c ≠ d, les dos rectes són diferents i no hi ha intersecció. De lo contrari, les dos rectes són idèntiques.

Usant coordenades homogénees

En usar coordenades homogénees, el punt d'intersecció de dos rectes implícitament definides es pot determinar en prou facilitat. En 2D, cada punt es pot definir com una proyecció d'un punt 3D, donat com la trio ordenat $(x, y, w)$ . L'aplicació de coordenades 3D a 2D és $(x^{'}, y^{'}) = (x / w, y / w)$ . Es poden convertir punts 2D en coordenades homogénees definint-los com $(x, y, 1)$ .

Suponga's que es vol trobar l'intersecció de dos rectes infinites en l'espai bidimensional, definides com $a_{1} x + b_{1} y + c_{1} = 0$ i $a_{2} x + b_{2} y + c_{2} = 0$ . Es poden representar estes dos rectes en coordenades llineals com $U_{1} = (a_{1}, b_{1}, c_{1})$ i $U_{2} = (a_{2}, b_{2}, c_{2})$ ,

L'intersecció $P^{'}$ de dos rectes ve donada simplement per^[2]

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

Si $c_{p} = 0$ , les rectes no es tallen.

Intersecció de n rectes

Existència i expressió de l'intersecció

En dos dimensions

En dos dimensions, més de dos rectes casi segurament no es creuen en un únic punt. Per a determinar si ho fan i, de ser aixina, per a trobar el punt d'intersecció, n'hi ha prou en donar forma a les equacions per a cada valor i-ésimo (i = 1, ..., n) com $(a_{i 1} a_{i 2}) (x y)^{T} = b_{i},$ , i dispondre-les en forma de matriu com

A w = b,

a on la i-ésima fila de la matriu A d'orde n× 2 és $(a_{i 1}, a_{i 2})$ , w és el vector d'orde 2×1 (x, i)^T, i l'element i-ésimo del vector de columna b és b_i. Si A té columnes independents, la seua ranc és 2. Llavors, si i solament si el ranc de la matriu aumentada [A | b] també és 2, existix una solució de l'equació matricial i, per lo tant, un punt d'intersecció de les n rectes. El punt d'intersecció, si existix, ve dau per

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

a on $A^{g}$ és la matriu pseudoinversa de Moore-Penrose de $A$ (que té la forma mostrada perque A posseïx ranc de columna complet). Alternativament, la solució es pot trobar en resoldre conjuntament dos equacions independents. Pero si el ranc de A és solament 1, llavors, si el ranc de la matriu aumentada és 2, no existix solució, pero si el seu ranc és 1, llavors totes les rectes coincidixen entre sí.

En tres dimensions

L'enfocament anterior es pot estendre fàcilment a tres dimensions. En tres o més dimensions, inclús dos rectes casi en seguritat no es creuen; els parells de rectes no paraleles que no es intersecan es diuen rectes que es creuen. Pero si existix una intersecció, es pot trobar de la següent manera.

En tres dimensions, una recta està representada per l'intersecció de dos plans, cada u dels quals té una equació de la forma $(a_{i 1} a_{i 2} a_{i 3}) (x y z)^{T} = b_{i}$ . Aixina, un conjunt de n rectes es pot representar per mig de 2n equacions en l'espai tridimensional, en el vector de coordenades w = (x, i, z)^T:

A w = b

a on ara A és 2n× 3 i b és 2n×1. Com abans, existix un punt d'intersecció únic si i solament si A té ranc de columna complet i la matriu aumentada [A | b] no ho té. L'intersecció única, si existix, ve donada per

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

Punt més propenc de rectes que no es tallen

En dos o més dimensions, generalment es pot trobar un punt que siga el més propenc a dos o més rectes en térmens dels seus mínims quadrats.

En dos dimensions

En el cas bidimensional, primer, es representa la recta i com un punt $p_{i}$ en la recta i un vector normal unitari, ${\hat{n}}_{i}$ , perpendicular a eixa recta. És dir, si $x_{1}$ i $x_{2}$ són punts en la recta 1, llavors es té que $p_{1} = x_{1}$ i que

{\hat{n}}_{1} : = [\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}] (x_{2} - x_{1}) / ‖ x_{2} - x_{1} ‖

que és el vector unitari de la recta, girat 90 graus.

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

d (x, (p, n)) = ‖ (x - p) \cdot \hat{n} ‖ = ‖ (x - p)^{⊤} \hat{n} ‖ = \sqrt{(x - p)^{⊤} \hat{n} {\hat{n}}^{⊤} (x - p)} .

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

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

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

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

Açò pot reorganisar-se de la forma següent:

\begin{matrix} E (x) & = \sum_{i} x^{⊤} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} x - x^{⊤} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} p_{i} - p_{i}^{⊤} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} x + p_{i}^{⊤} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} p_{i} \\ = x^{⊤} (\sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤}) x - 2 x^{⊤} (\sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} p_{i}) + \sum_{i} p_{i}^{⊤} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} p_{i} . \end{matrix}

Per a trobar el mínim, es deriva sobre x i s'establix el resultat igual al vector zero:

\frac{\partial E (x)}{\partial x} = 0 = 2 (\sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤}) x - 2 (\sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} p_{i})

aixina que

(\sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤}) x = \sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} p_{i}

i llavors

x = {(\sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤})}^{- 1} (\sum_{i} {\hat{n}}_{i} {\hat{n}}_{i}^{⊤} p_{i}) .

En tres dimensions

Encara que ${\hat{n}}_{i}$ no està ben definit en més de dos dimensions, açò es pot generalisar a qualsevol cantitat de dimensions en observar que ${\hat{n}}_{i} {\hat{n}}_{i}^{⊤}$ és simplement la matriu (simètrica) en tots els autovalores unitat, llevat per un valor propi zero en la direcció a lo llarc de la recta que proporciona una norma sobre la distància entre $p_{i}$ i un atre punt donant la seua distància a la recta. En qualsevol cantitat de dimensions, si ${\hat{v}}_{i}$ és un vector unitari en la recta i, llavors

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

es convertix en

I - {\hat{v}}_{i} {\hat{v}}_{i}^{⊤}

a on I és la matriu identitat, i aixina

x = {(\sum_{i} I - {\hat{v}}_{i} {\hat{v}}_{i}^{⊤})}^{- 1} (\sum_{i} (I - {\hat{v}}_{i} {\hat{v}}_{i}^{⊤}) p_{i}) .

^{cita requerida}

Vore també

Referències

↑ «Weisstein, Eric W. "Line-Line Intersection." From MathWorld». A Wolfram Web Resource. Consultat el 10 de giner de 2008.
↑ «Homogeneous coordinates». Consultat el 18 d'agost de 2015.

Referències

Este artícul conté una traducció derivada de «Intersección de dos rectas» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[Wolfram-1] «Weisstein, Eric W. "Line-Line Intersection." From MathWorld». A Wolfram Web Resource. Consultat el 10 de giner de 2008.

[2] «Homogeneous coordinates». Consultat el 18 d'agost de 2015.

[1]

[2]