En geometría euclidiana , la intersección de una línea y una línea puede ser el conjunto vacío , un punto o una línea. Distinguir estos casos y encontrar el punto de intersección tiene uso, por ejemplo, en gráficos por computadora , planificación de movimiento y detección de colisiones .
La intersección de líneas.
En la geometría euclidiana tridimensional , si dos líneas no están en el mismo plano , se denominan líneas oblicuas y no tienen punto de intersección. 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 ellos); si son distintos pero tienen la misma pendiente, se dice que son paralelos y no tienen puntos en común; de lo contrario, tienen un solo punto de intersección.
Las características distintivas de la geometría no euclidiana son el número y la ubicación de posibles intersecciones entre dos líneas y el número de posibles líneas sin intersecciones (líneas paralelas) con una línea dada.
Una condición necesaria para que dos líneas se crucen es que estén en el mismo plano, es decir, que no sean líneas oblicuas. La satisfacción de esta condición es equivalente a que el tetraedro con vértices en dos de los puntos de una línea y dos de los puntos de la otra línea estén degenerados en el sentido de tener un volumen cero . Para conocer la forma algebraica de esta condición, consulte Líneas oblicuas § Prueba de asimetría .
Dados dos puntos en cada línea
Primero consideramos la intersección de dos rectas. y en espacio bidimensional, con línea siendo definido por dos puntos distintos y y línea siendo definido por dos puntos distintos y . [1]
La intersección desconectado y se puede definir mediante determinantes .
Los determinantes se pueden escribir como:
donde el denominador es:
Cuando las dos líneas son paralelas o coincidentes, el denominador es cero. Si las líneas son casi paralelas, entonces una solución informática puede encontrar problemas numéricos al implementar la solución descrita anteriormente: el reconocimiento de esta condición puede requerir una prueba aproximada en una aplicación práctica. Un enfoque alternativo podría ser rotar los segmentos de línea de modo que uno de ellos sea horizontal, de donde se obtenga fácilmente la solución de la forma paramétrica rotada de la segunda línea. Se requiere una discusión cuidadosa de los casos especiales (líneas paralelas / líneas coincidentes, intervalos superpuestos / no superpuestos).
Dados dos puntos en cada segmento de línea
Tenga en cuenta que el punto de intersección anterior es para 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 líneas y en términos de parámetros Bézier de primer grado :
(donde t y u son números reales). El punto de las líneas de intersección se encuentra con uno de los siguientes valores de t o u , donde
y
con:
El punto de intersección cae dentro del primer segmento de línea si 0.0 ≤ t ≤ 1.0, y cae dentro del segundo segmento de línea si 0.0 ≤ u ≤ 1.0. Estas desigualdades se pueden probar sin necesidad de división, lo que permite una determinación rápida de la existencia de cualquier intersección de segmento de línea antes de calcular su punto exacto. [2]
Dadas dos ecuaciones de línea
La y Las coordenadas del punto de intersección de dos líneas no verticales se pueden encontrar fácilmente utilizando las siguientes sustituciones y reordenamientos.
Suponga que dos rectas tienen las ecuaciones y dónde y son las pendientes (gradientes) de las líneas y donde y son las intersecciones en y de las líneas. En el punto donde las dos líneas se cruzan (si lo hacen), ambas las coordenadas serán las mismas, de ahí la siguiente igualdad:
Podemos reorganizar esta expresión para extraer el valor de ,
y entonces,
Para encontrar la coordenada y , todo lo que tenemos que hacer es sustituir el valor de x en cualquiera de las dos ecuaciones de línea, por ejemplo, en la primera:
Por tanto, el punto de intersección es
Tenga en cuenta que si a = b , las dos líneas son paralelas . Si c ≠ d también, las líneas son diferentes y no hay intersección; de lo contrario, las dos líneas son idénticas.
Usando coordenadas homogéneas
Utilizando 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. El mapeo de coordenadas 3D a 2D es. Podemos convertir puntos 2D en coordenadas homogéneas definiéndolos como.
Suponga que queremos encontrar la intersección de dos líneas infinitas en un espacio bidimensional, definido como y . Podemos representar estas dos líneas en coordenadas de línea como y ,
La intersección de dos líneas simplemente viene dado por, [3]
Si las líneas no se cruzan.
La intersección de dos líneas se puede generalizar para incluir líneas adicionales. La existencia de una expresión para el problema de intersección de n líneas es la siguiente.
En dos dimensiones
En dos dimensiones, es casi seguro que más de dos líneas no se crucen en un solo punto. Para determinar si lo hacen y, de ser así, para encontrar el punto de intersección, escriba la i -ésima ecuación ( i = 1,…, n ) como y apilar estas ecuaciones en forma de matriz como
donde la i -ésima fila de la matriz A n × 2 es, w es el vector 2 × 1 ( x, y ) T , y el i -ésimo elemento del vector columna b es b i . Si A tiene columnas independientes, su rango es 2. Entonces si y solo si el rango de la matriz 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 las n líneas. El punto de intersección, si existe, viene dado por
dónde es el inverso generalizado de Moore-Penrose de(que tiene el formulario que se muestra porque A tiene un 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í.
En tres dimensiones
El enfoque anterior se puede ampliar fácilmente a tres dimensiones. En tres o más dimensiones, es casi seguro que incluso dos líneas no se cruzan; los pares de líneas no paralelas que no se cruzan se llaman líneas oblicuas . Pero si existe una intersección, se puede encontrar de la siguiente manera.
En tres dimensiones, una línea está representada por la intersección de dos planos, cada uno de los cuales tiene una ecuación de la forma Por lo tanto, un conjunto de n líneas se puede representar mediante 2 n ecuaciones en el vector de coordenadas tridimensional w = ( x , y , z ) T :
donde ahora A es 2 n × 3 y b es 2 n × 1. Como antes, hay un punto de intersección único si y solo si A tiene rango de columna completo y la matriz aumentada [ A | b ] no, y la intersección única, si existe, viene dada por
En dos o más dimensiones, normalmente podemos encontrar un punto que se acerque mutuamente a dos o más líneas en el sentido de mínimos cuadrados .
En dos dimensiones
En el caso bidimensional, primero, represente la línea i como un punto,, En la línea y una unidad de vector normal ,, perpendicular a esa línea. Es decir, si y son puntos en la línea 1, luego y deja
que es el vector unitario a lo largo de la línea, girado 90 grados.
Tenga en cuenta que la distancia desde un punto, xa la línea es dado por
Y entonces la distancia al cuadrado de un punto, x , a una línea es
La suma de las distancias al cuadrado de muchas líneas es la función de costo :
Esto se puede reorganizar:
Para encontrar el mínimo, diferenciamos con respecto a xy igualamos el resultado al vector cero:
entonces
y entonces
En más de dos dimensiones
Tiempo no está bien definido en más de dos dimensiones, esto se puede generalizar a cualquier número de dimensiones señalando que es simplemente la matriz (simétrica) con la unidad de todos los valores propios excepto por un valor propio cero en la dirección a lo largo de la línea que proporciona una semormal en la distancia entrey otro punto que indica la distancia a la línea. En cualquier número de dimensiones, sies un vector unitario a lo largo de la i -ésima línea, entonces
- se convierte en
donde I es la matriz de identidad, por lo que [4]
Derivación general
Para encontrar el punto de intersección de un conjunto de líneas, calculamos el punto con la distancia mínima a ellas. Cada línea está definida por un origen y un vector de dirección unitaria, . El cuadrado de la distancia desde un punto. a una de las líneas se da de Pitágoras:
Dónde : es la proyección de en la línea . La suma de distancias al cuadrado a todas las líneas es:
Para minimizar esta expresión, la diferenciamos con respecto a .
Resulta:
Dónde es la matriz de identidad. Esta es una matriz, con solución , dónde es el pseudo-inverso de .