Intersección de línea

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de octubre de 2020; las comprobaciones requieren 2 ediciones .

En geometría euclidiana, la intersección de dos líneas puede ser un conjunto vacío , un punto o una línea. Distinguir estos casos y encontrar el punto de intersección se usa, por ejemplo, en gráficos por computadora , en planificación de movimiento y en detección de colisiones .

En geometría euclidiana tridimensional , si dos líneas no están en el mismo plano , se denominan sesgadas y no tienen puntos de intersección. Si las líneas están en el mismo plano, hay tres posibilidades. Si coinciden, tienen infinitos puntos en común (es decir, todos los puntos de estas líneas). Si las rectas son distintas pero tienen la misma pendiente , son paralelas y no tienen puntos en común. De lo contrario, tienen un punto de intersección.

En geometría no euclidiana, dos líneas pueden intersecarse en varios puntos, y el número de otras líneas (paralelas) que no intersecan con una línea dada puede ser mayor que uno.

Intersección de dos líneas

Una condición necesaria para la intersección de dos rectas es que pertenezcan al mismo plano, es decir, que estas rectas no se corten. El cumplimiento de esta condición es equivalente a la degeneración del tetraedro , en el que dos vértices se encuentran en una línea recta y los otros dos se encuentran en la otra (es decir , el volumen de este tetraedro es igual a cero). La forma algebraica de esta condición se puede encontrar en el artículo " Comprobando el cruce ".

Dados dos puntos en cada línea

Considere la intersección de dos líneas y en el plano, donde la línea está definida por dos puntos diferentes y , y la línea está definida por puntos diferentes y [1] . ${\ estilo de visualización L_ {1} \,}$ ${\ estilo de visualización L_ {2} \,}$ ${\ estilo de visualización L_ {1} \,}$ ${\ estilo de visualización (x_ {1}, y_ {1}) \,}$ ${\ estilo de visualización (x_ {2}, y_ {2}) \,}$ ${\ estilo de visualización L_ {2} \,}$ ${\ estilo de visualización (x_ {3}, y_ {3}) \,}$ ${\ estilo de visualización (x_ {4}, y_ {4}) \,}$

La intersección de las líneas y se puede encontrar usando los determinantes . $PAGS\,$ ${\ estilo de visualización L_ {1} \,}$ ${\ estilo de visualización L_ {2} \,}$

P_{x}={\frac {\begin{vmatriz}{\begin{vmatriz}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatriz))&{\ comenzar{vmatriz}x_{1}&1\\x_{2}&1\end{vmatriz}}\\\\{\begin{vmatriz}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{vmatriz}}&{\begin{vmatriz}y_{1}&1\\y_{2}&1\end{vmatriz}}\\\\{\begin{ vmatriz}x_{3}&1\\x_{4}&1\end{vmatriz}}&{\begin{vmatriz}y_{3}&1\\y_{4}&1\end{vmatriz}}\end{vmatriz} }}\,\!\qquad P_{y}={\frac {\begin{vmatriz}{\begin{vmatriz}x_{1}&y_{1}\\x_{2}&y_{2}\end{vmatriz }}&{\begin{vmatriz}y_{1}&1\\y_{2}&1\end{vmatriz}}\\\\{\begin{vmatriz}x_{3}&y_{3}\\x_{4 }&y_{4}\end{vmatriz}}&{\begin{vmatriz}y_{3}&1\\y_{4}&1\end{vmatriz}}\end{vmatriz}}{\begin{vmatriz}{\ comenzar{vmatrix}x_{1}&1\\x_{2}&1\end{vmatrix}}&{\begin{vmatrix}y_{1}&1\\y_{2}&1\end{vmatrix}}\\\ \{\begin{vmatriz}x_{3}&1\\x_{4}&1\end{vmatriz}}&{\begin{vmatriz}y_{3}&1\\y_{4}&1\end{vmatriz}} \end{vmatriz}}}\,\!

Los determinantes se pueden reescribir como:

{\begin{alineado}(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{alineado}}

Tenga en cuenta que el punto de intersección se refiere a las líneas infinitas, no a los segmentos de línea entre los puntos, y puede estar fuera de los segmentos de línea. Si (en lugar de resolver en un solo paso) buscamos una solución en términos de curvas de Bezier de primer orden , entonces podemos verificar los parámetros de estas curvas 0.0 ≤ t ≤ 1.0 y 0.0 ≤ u ≤ 1.0 ( t y u son parámetros) .

Si dos rectas son paralelas o coinciden, el denominador se anula:

{\ estilo de visualización (x_{1}-x_{2})(y_{3}-y_{4})-(y_{1}-y_{2})(x_{3}-x_{4})=0 .}

Si las líneas están muy cerca del paralelo (casi paralelas), pueden surgir problemas numéricos en el cálculo de la computadora, y reconocer tal condición puede requerir una prueba de "incertidumbre" apropiada para la aplicación. Se puede obtener una solución más estable y general al rotar los segmentos de tal manera que uno de ellos quede horizontal, y luego la solución paramétrica de la segunda recta es fácil de obtener. Al resolver, es necesario considerar cuidadosamente los casos especiales (paralelismo/coincidencia de líneas rectas, superposición de segmentos).

Si se dan ecuaciones de rectas

Las coordenadas y los puntos de intersección de dos líneas no verticales se pueden encontrar fácilmente usando las siguientes sustituciones y transformaciones. $X$ $y$

Suponga que dos rectas tienen ecuaciones y , donde y son las pendientes de las rectas, y y son las intersecciones de las rectas con el eje y . En el punto de intersección de las rectas (si se cortan), ambas coordenadas coincidirán, de lo que obtenemos la igualdad: $y=ax+c$ ${\ estilo de visualización y = bx + d}$ $a$ $b$ $C$ $d$ $y$

hacha+c=bx+d

Podemos transformar esta igualdad para resaltar , $X$

ax-bx=dc

y entonces

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

Para encontrar la coordenada y , todo lo que tenemos que hacer es introducir el valor de x en una de las fórmulas de línea, como la primera:

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

De aquí obtenemos el punto de intersección de las rectas

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

Tenga en cuenta que para a = b las dos líneas son paralelas. Si al mismo tiempo c ≠ d , las rectas son diferentes y no tienen intersecciones, de lo contrario las rectas coinciden [2] .

Uso de coordenadas homogéneas

Cuando se usan coordenadas homogéneas , el punto de intersección de dos líneas dadas explícitamente se puede encontrar de manera bastante simple. En el espacio de 2 dimensiones, cualquier punto se puede definir como una proyección de un punto de 3 dimensiones dado por un triple . El mapeo de coordenadas tridimensionales a bidimensionales ocurre de acuerdo con la fórmula . Podemos convertir puntos en un espacio bidimensional en coordenadas homogéneas igualando la tercera coordenada a uno - . ${\ estilo de visualización (x, y, w)}$ ${\ estilo de visualización (x', y') = (x/w, y/w)}$ ${\ estilo de visualización (x, y, 1)}$

Supongamos que queremos encontrar la intersección de dos líneas infinitas en un espacio bidimensional, que vienen dadas por las fórmulas y . Podemos representar estas dos líneas en coordenadas lineales como , $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})$

La intersección de dos rectas viene simplemente dada por las fórmulas [3] $PAGS'$

$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 , las rectas no se cortan. ${\ estilo de visualización c_ {p} = 0}$

Intersección de n líneas

Expresión de existencia e intersección

En dos dimensiones

En el espacio bidimensional, las líneas con más de dos casi con certeza no se cruzan en un punto. Para determinar si se intersecan en un punto, y si se intersecan, para encontrar el punto de intersección, escribimos la i -ésima ecuación ( i = 1, ..., n ) como y organizamos estas ecuaciones en forma de matriz $(a_{i1}\quad a_{i2})(x\quad y)^{T}=b_{i},$

{\ estilo de visualización Aw = b,}

donde la i-ésima fila de la matriz A de n × 2 es , w es un vector de 2 × 1 ( x, y ) T , y el i-ésimo elemento del vector columna b es b i . Si las columnas de la matriz A son independientes, entonces el rango de la matriz es 2. Si y solo si el rango de la matriz extendida es [ A | b ] también es igual a 2, hay una solución a la ecuación matricial, y luego también hay un punto de intersección de n líneas. El punto de intersección, si existe, está dado por ${\ estilo de visualización (a_ {i1}, a_ {i2})}$

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

donde es la pseudoinversa de la matriz . Alternativamente, la solución se puede encontrar resolviendo dos ecuaciones independientes cualesquiera. Pero si el rango de la matriz A es 1 y el rango de la matriz aumentada es 2, no hay soluciones. En el caso de que el rango de la matriz extendida sea igual a 1, todas las líneas coinciden. ${\ estilo de visualización A ^ {g}}$ $A$

En el espacio 3D

El enfoque presentado anteriormente se extiende fácilmente al espacio tridimensional. En espacios tridimensionales y superiores, es casi seguro que incluso dos líneas no se cruzan. Los pares de líneas no paralelas que no se cruzan se llaman sesgados . Pero cuando existe una intersección, se puede encontrar de la siguiente manera.

En el espacio tridimensional, una línea recta se representa mediante la intersección de dos planos, cada uno de los cuales viene dado por la fórmula Entonces, el conjunto de n líneas rectas se puede representar como 2 n ecuaciones a partir de un vector de coordenadas tridimensional w = ( x , y , z ) T : $(a_{i1}\quad a_{i2}\quad a_{i3})(x\quad y\quad z)^{T}=b_{i}.$

{\ estilo de visualización Aw = b}

donde A es una matriz de 2n × 3 yb es una matriz de 2n × 1. Como antes, existe un único punto de intersección si y solo si A tiene rango de columna completo y la matriz aumentada [ A | b ] no lo es. El único punto de intersección, si existe, viene dado por

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

Punto más cercano a líneas que no se cruzan

En las dimensiones dos y superiores, uno puede encontrar el punto más cercano a estas dos (o más) líneas en el sentido de la mínima suma de cuadrados .

En dos dimensiones

En el caso de un espacio bidimensional, represente la línea i como un punto en la línea y una unidad normal perpendicular a la línea. Es decir, si y son puntos en la línea 1, entonces sea y $Pi}$ ${\sombrero {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}\|

que es el vector unitario a lo largo de la recta rotada 90º.

Tenga en cuenta que la distancia desde el punto x a la línea está dada por la fórmula ${\ estilo de visualización (pag, {\ sombrero {n)))}$

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

Por lo tanto, el cuadrado de la distancia de x a la recta es

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

La suma de las distancias al cuadrado a un conjunto de rectas es la función objetivo :

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

La expresión se puede convertir:

{\begin{alineado}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} {\sombrero {n}}_{i}^{\arriba}\derecha)x-2x^{\arriba}\izquierda(\sum_{i}{\sombrero {n}}_{i}{\sombrero {n}}_{i}^{\top }p_{i}\right)+\sum _{i}p_{i}^{\top }{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}.\end{alineado}}

Para encontrar el mínimo, derivamos con respecto ax y igualamos el resultado a cero:

{\frac {\parcial E(x)}{\parcial x}}=0=2\left(\sum_{i}{\hat {n}}_{i}{\hat {n} }_{i}^{\arriba}\right)x-2\left(\sum_{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\ arriba }p_{i}\right)

De este modo,

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

dónde

x=\left(\sum_{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top}\right)^{-1}\ izquierda(\sum_{i}{\hat {n}}_{i}{\hat {n}}_{i}^{\top }p_{i}\right).

En el espacio 3D

Aunque la normal no se puede definir en dimensiones superiores a dos , se puede generalizar a cualquier dimensión si se observa que es simplemente una matriz (simétrica) con todos los valores propios iguales a uno, excepto el valor propio cero en la dirección de la línea. , que da una seminorma entre un punto y otro punto . En un espacio de cualquier dimensión, si es un vector unitario a lo largo de la recta i -ésima, entonces ${\sombrero {n}}_{i}$ ${\sombrero {n}}_{i}{\sombrero {n}}_{i}^{\arriba}$ $Pi}$ ${\sombrero {v}}_{i}$

{\sombrero {n}}_{i}{\sombrero {n}}_{i}^{\arriba}

se convierte en

E-{\sombrero {v}}_{i}{\sombrero {v}}_{i}^{\arriba}

donde E es la matriz identidad, y luego

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

Véase también

Notas

↑ Weisstein, Eric W. "Intersección de línea a línea". De Mathworld . Un recurso web de Wolfram . Consultado el 10 de enero de 2008. Archivado desde el original el 10 de octubre de 2007. (indefinido)
↑ Se pueden encontrar cálculos similares en el libro de Delaunay y Raikov (págs. 202-203)
↑ Coordenadas homogéneas . robótica.stanford.edu . Consultado el 18 de agosto de 2015. Archivado desde el original el 23 de agosto de 2015. (indefinido)

Literatura

B. N. Delaunay, D. A. Raikov. Geometría analítica. - M., L.: OGIZ, Editorial estatal de literatura técnica y teórica, 1948. - T. 1.

Enlaces

Distancia entre Líneas y Segmentos con su Punto de Aproximación Más Cercano , aplicable a dos, tres o más dimensiones.