Intersección de línea con línea

En la geometría euclidiana , la intersección de una línea y otra recta puede ser el conjunto vacío , un punto u otra línea . Distinguir estos casos y encontrar la intersección tiene utilidad, por ejemplo, en gráficos por ordenador , planificación de movimiento y detección de colisiones .

En geometría euclidiana tridimensional , si dos líneas no están en el mismo plano , no tienen punto de intersección ^{[ cita requerida ]} y se denominan líneas oblicuas . Sin embargo, si están en el mismo plano, hay tres posibilidades: si coinciden (no son líneas distintas), tienen una infinidad de puntos en común (es decir, todos los puntos de cualquiera de ellas); si son distintas pero tienen la misma pendiente , se dice que son paralelas y no tienen puntos en común; en caso contrario, tienen un único punto de intersección.

Las características distintivas de la geometría no euclidiana son el número y las ubicaciones de las posibles intersecciones entre dos líneas y el número de posibles líneas sin intersecciones (líneas paralelas) con una línea dada. ^{[ se necesita más explicación ]}

Una condición necesaria para que dos rectas se intersequen es que estén en el mismo plano, es decir, que no sean rectas oblicuas. El cumplimiento de esta condición es equivalente a que el tetraedro con vértices en dos de los puntos de una recta y dos de los puntos de la otra recta sea degenerado en el sentido de tener volumen cero . Para la forma algebraica de esta condición, véase Rectas oblicuas § Prueba de oblicuidad .

Primero consideramos la intersección de dos líneas L ₁ y L ₂ en el espacio bidimensional, donde la línea L ₁ está definida por dos puntos distintos ( x ₁ , y ₁ ) y ( x ₂ , y ₂ ) , y la línea L ₂ está definida por dos puntos distintos ( x ₃ , y ₃ ) y ( x ₄ , y ₄ ) . ^[1]

La intersección P de las líneas L ₁ y L ₂ se puede definir utilizando determinantes .

${\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{vmatri x}}{\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{vmat rix}}{\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}}}\,\!}$

Los determinantes se pueden escribir como:

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

Cuando las dos rectas son paralelas o coincidentes, el denominador es cero.

El punto de intersección anterior corresponde a las líneas infinitamente largas definidas por los puntos, en lugar de los segmentos de línea entre los puntos, y puede producir un punto de intersección que no esté contenido en ninguno de los dos segmentos de línea. Para encontrar la posición de la intersección con respecto a los segmentos de línea, podemos definir las líneas L ₁ y L ₂ en términos de parámetros de Bézier de primer grado :

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

(donde t y u son números reales). El punto de intersección de las líneas se encuentra con uno de los siguientes valores de t o u , donde

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

y

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

con

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

Habrá una intersección si 0 ≤ t ≤ 1 y 0 ≤ u ≤ 1 . El punto de intersección cae dentro del primer segmento de línea si 0 ≤ t ≤ 1 , y cae dentro del segundo segmento de línea si 0 ≤ u ≤ 1 . Estas desigualdades se pueden probar sin la necesidad de división, lo que permite la determinación rápida de la existencia de cualquier intersección de segmento de línea antes de calcular su punto exacto. ^[2]

Las coordenadas x e y del punto de intersección de dos líneas no verticales se pueden encontrar fácilmente utilizando las siguientes sustituciones y reordenamientos.

Supongamos que dos rectas tienen las ecuaciones y = ax + c e y = bx + d , donde a y b son las pendientes (gradientes) de las rectas y donde c y d son las intersecciones con el eje y de las rectas. En el punto en el que las dos rectas se intersecan (si lo hacen), ambas coordenadas y serán las mismas, de ahí la siguiente igualdad:

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

Podemos reorganizar esta expresión para extraer el valor de x ,

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

y entonces,

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

Para encontrar la coordenada y , todo lo que necesitamos hacer es sustituir el valor de x en cualquiera de las dos ecuaciones de línea, por ejemplo, en la primera:

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

Por lo tanto, el punto de intersección es

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

Nótese que si a = b entonces las dos líneas son paralelas y no se intersecan, a menos que c = d también, en cuyo caso las líneas son coincidentes y se intersecan en cada punto.

Al utilizar coordenadas homogéneas , el punto de intersección de dos líneas definidas implícitamente se puede determinar con bastante facilidad. En 2D, cada punto se puede definir como una proyección de un punto 3D, dado como el triple ordenado ( x , y , w ) . La aplicación de coordenadas 3D a 2D es ( x ′, y ′) = ( ⁠incógnita/el⁠ , ⁠y/el⁠ ) ​​. Podemos convertir puntos 2D en coordenadas homogéneas definiéndolos como ( x , y , 1) .

Supongamos que queremos encontrar la intersección de dos líneas infinitas en un espacio bidimensional, definidas como a ₁ x + b ₁ y + c ₁ = 0 y a ₂ x + b ₂ y + c ₂ = 0. Podemos representar estas dos líneas en coordenadas lineales como U ₁ = ( a ₁ , b ₁ , c ₁ ) y U ₂ = ( a ₂ , b ₂ , c ₂ ) . La intersección P ′ de dos líneas se da simplemente por ^[3]

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

Si c _p = 0 , las rectas no se intersecan.

La intersección de dos líneas se puede generalizar para incluir líneas adicionales. La existencia y la expresión para el problema de intersección de n líneas son las siguientes.

En dos dimensiones, es casi seguro que más de dos líneas no se intersecan en un único punto. Para determinar si lo hacen y, en caso afirmativo, encontrar el punto de intersección, escriba la i -ésima ecuación ( i = 1, …, n ) como

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

y apila estas ecuaciones en forma de matriz como

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

donde la i- ésima fila de la matriz n × 2 A es [ a _{i 1} , a _{i 2} ] , w es el vector 2 × 1 [^x
_y] , y eliésimo elemento del vector columna b es b _i . Si A tiene columnas independientes, surangoes 2. Entonces, si y solo si el rango de lamatriz aumentada [ A | b ]también es 2, existe una solución de la ecuación matricial y, por lo tanto, un punto de intersección de lasnlíneas. El punto de intersección, si existe, está dado por

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

donde A ^g es la inversa generalizada de Moore-Penrose de A (que tiene la forma que se muestra porque A tiene rango de columna completo). Alternativamente, la solución se puede encontrar resolviendo conjuntamente dos ecuaciones independientes cualesquiera. Pero si el rango de A es solo 1, entonces si el rango de la matriz aumentada es 2 no hay solución, pero si su rango es 1, entonces todas las líneas coinciden entre sí.

El enfoque anterior se puede extender fácilmente a tres dimensiones. En tres o más dimensiones, es casi seguro que ni siquiera dos líneas se intersecan; los pares de líneas no paralelas que no se intersecan se denominan líneas oblicuas . Pero si existe una intersección, se puede encontrar de la siguiente manera.

En tres dimensiones, una línea se representa mediante la intersección de dos planos, cada uno de los cuales tiene una ecuación de la forma

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

Así, un conjunto de n líneas se puede representar mediante 2 n ecuaciones en el vector de coordenadas tridimensional w :

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

donde ahora A es 2 n × 3 y b es 2 n × 1. Como antes, hay un único punto de intersección si y solo si A tiene rango de columna completo y la matriz aumentada [ A | b ] no, y la única intersección, si existe, está dada por

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

En dos o más dimensiones, generalmente podemos encontrar un punto que sea mutuamente más cercano a dos o más líneas en un sentido de mínimos cuadrados .

En el caso bidimensional, primero, represente la recta i como un punto p _i sobre la recta y un vector normal unitario n̂ _i , perpendicular a esa recta. Es decir, si x ₁ y x ₂ son puntos sobre la recta 1, entonces sea p ₁ = x ₁ y sea

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

que es el vector unitario a lo largo de la línea, rotado en un ángulo recto.

La distancia desde un punto x a la línea ( p , n̂ ) está dada por

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

Y entonces la distancia al cuadrado desde un punto x a una línea es

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

La suma de las distancias al cuadrado de muchas líneas es la función de costo :

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

Esto se puede reorganizar:

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

Para encontrar el mínimo, diferenciamos con respecto a x y establecemos el resultado igual al vector cero:

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

entonces

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

y entonces

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

Si bien n̂ _i no está bien definido en más de dos dimensiones, esto se puede generalizar a cualquier número de dimensiones notando que n̂ _i n̂ _i ^T es simplemente la matriz simétrica con todos los valores propios unitarios excepto por un valor propio cero en la dirección a lo largo de la línea que proporciona una seminorma en la distancia entre p _i y otro punto que da la distancia a la línea. En cualquier número de dimensiones, si v̂ _i es un vector unitario a lo largo de la línea i ésima, entonces

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

donde I es la matriz identidad , y por lo tanto ^[4]

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

Para hallar el punto de intersección de un conjunto de rectas, calculamos el punto que se encuentra a una distancia mínima de ellas. Cada recta está definida por un origen a _i y un vector de dirección unitario n̂ _i . El cuadrado de la distancia desde un punto p a una de las rectas viene dado por Pitágoras:

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

donde ( p − a _i ) ^T n̂ _i es la proyección de p − a _i sobre la recta i . La suma de las distancias al cuadrado de todas las rectas es

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

Para minimizar esta expresión, la diferenciamos con respecto a p .

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

Lo que resulta en

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

donde I es la matriz identidad . Esta es una matriz Sp = C , con solución p = S ⁺ C , donde S ⁺ es la pseudo-inversa de S .

En geometría esférica , dos círculos máximos cualesquiera se intersecan. ^[5]

En geometría hiperbólica , dada cualquier línea y cualquier punto, hay infinitas líneas que pasan por ese punto y que no intersecan la línea dada. ^[5]

• Intersección de segmentos de línea
• Intersección de líneas en el espacio proyectivo
• Distancia entre dos líneas paralelas
• Distancia de un punto a una línea
• Intersección de línea y plano
• Postulado paralelo
• Triangulación (visión por computadora)
• Intersección (Geometría euclidiana) § Dos segmentos de línea

• Distancia entre líneas y segmentos con su punto de aproximación más cercano, aplicable a dos, tres o más dimensiones.