Intersección línea-línea - Line–line intersection

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 .

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.

Fórmulas

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 líneas y en un espacio bidimensional, donde la línea está definida por dos puntos distintos y , y la línea está definida por dos puntos distintos y . ${\ Displaystyle L_ {1}}$${\ Displaystyle L_ {2}}$${\ Displaystyle L_ {1}}$${\ Displaystyle (x_ {1}, y_ {1})}$${\ Displaystyle (x_ {2}, y_ {2})}$${\ Displaystyle L_ {2}}$${\ Displaystyle (x_ {3}, y_ {3})}$${\ Displaystyle (x_ {4}, y_ {4})}$

La intersección de la línea y se puede definir mediante determinantes . ${\ Displaystyle P}$${\ Displaystyle L_ {1}}$${\ Displaystyle L_ {2}}$

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

Los determinantes se pueden escribir como:

${\ Displaystyle {\ begin {alineado} (P_ {x}, P_ {y}) = {\ Biggl (} 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})} {D}}, \\ & {\ 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})} {D}} {\ Biggr)} \ end {alineado}}}$

donde el denominador es:

${\ Displaystyle D = (x_ {1} -x_ {2}) (y_ {3} -y_ {4}) - (y_ {1} -y_ {2}) (x_ {3} -x_ {4}) }$

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 de Bézier de primer grado : ${\ Displaystyle L_ {1}}$${\ Displaystyle L_ {2}}$

${\ 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 las líneas de intersección 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_ {3} & x_ {1} -x_ {2} \\ y_ {1} -y_ {3} & y_ {1} -y_ { 2} \ 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_ {1} -y_ {2}) - (y_ {1} -y_ {3}) (x_ {1} -x_ {2})} {(x_ {1} -x_ {2}) (y_ {3} -y_ {4}) - (y_ {1} -y_ {2}) (x_ {3} -x_ {4})}},}$

con:

${\ Displaystyle (P_ {x}, P_ {y}) = (x_ {1} + t (x_ {2} -x_ {1}), \; y_ {1} + t (y_ {2} -y_ { 1})) \ quad {\ text {o}} \ quad (P_ {x}, P_ {y}) = (x_ {3} + u (x_ {4} -x_ {3}), \; y_ { 3} + u (y_ {4} -y_ {3}))}$

Habrá una intersección si 0.0 ≤  t  ≤ 1.0 y 0.0 ≤  u  ≤ 1.0. 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.

Dadas dos ecuaciones de línea

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

Suponga que dos rectas tienen las ecuaciones y donde y son las pendientes (gradientes) de las rectas y donde y son las intersecciones en y de las rectas. En el punto donde las dos líneas se cruzan (si lo hacen), ambas coordenadas serán las mismas, de ahí la siguiente igualdad: ${\ Displaystyle y = ax + c}$${\ Displaystyle y = bx + d}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle c}$${\ Displaystyle d}$${\ Displaystyle y}$

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

Podemos reorganizar esta expresión para extraer el valor de , ${\ Displaystyle x}$

${\ Displaystyle ax-bx = dc,}$

y entonces,

${\ Displaystyle x = {\ frac {dc} {ab}}.}$

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:

${\ Displaystyle y = a {\ frac {dc} {ab}} + c.}$

Por tanto, el punto de intersección es

${\ Displaystyle P \ left ({\ frac {dc} {ab}}, a {\ frac {dc} {ab}} + c \ right).}$

Tenga en cuenta que si a = b, entonces 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

Mediante el uso de 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 . ${\ Displaystyle (x, y, w)}$${\ Displaystyle (x ', y') = (x / w, y / w)}$${\ Displaystyle (x, y, 1)}$

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 , ${\ Displaystyle a_ {1} x + b_ {1} y + c_ {1} = 0}$${\ Displaystyle a_ {2} x + b_ {2} y + c_ {2} = 0}$${\ Displaystyle U_ {1} = (a_ {1}, b_ {1}, c_ {1})}$${\ Displaystyle U_ {2} = (a_ {2}, b_ {2}, c_ {2})}$

La intersección de dos líneas está dada simplemente por, ${\ Displaystyle P '}$

${\ 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 las líneas no se cruzan. ${\ Displaystyle c_ {p} = 0}$

Más de dos líneas

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 cruzan 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 apile estas ecuaciones en forma de matriz como ${\ displaystyle {\ begin {bmatrix} a_ {i1} & a_ {i2} \ end {bmatrix}} {\ begin {bmatrix} x & y \ end {bmatrix}} ^ {\ mathsf {T}} = b_ {i}, }$

${\ Displaystyle Aw = b,}$

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 ${\ Displaystyle (a_ {i1}, a_ {i2})}$

${\ Displaystyle w = A ^ {g} segundo = \ left (A ^ {\ mathsf {T}} A \ right) ^ {- 1} A ^ {\ mathsf {T}} b,}$

donde es la inversa generalizada de Moore-Penrose de (que tiene la forma mostrada porque A tiene rango 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í. ${\ Displaystyle A ^ {g}}$${\ Displaystyle A}$

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 denominan 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.Así, un conjunto de n líneas se puede representar mediante 2 n ecuaciones en el vector de coordenadas tridimensional w = ( x , y , z ) ^T : ${\ displaystyle {\ begin {bmatrix} a_ {i1} & a_ {i2} & a_ {i3} \ end {bmatrix}} {\ begin {bmatrix} x & y & z \ end {bmatrix}} ^ {\ mathsf {T}} = b_ {I}.}$

${\ Displaystyle Aw = b}$

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

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

Puntos más cercanos para sesgar líneas

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 de dos dimensiones, primero, represento 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, entonces deja y deja ${\ Displaystyle p_ {i}}$ ${\ Displaystyle {\ hat {n}} _ {i}}$${\ Displaystyle x_ {1}}$${\ Displaystyle x_ {2}}$${\ Displaystyle p_ {1} = x_ {1}}$

${\ displaystyle {\ hat {n}} _ {1}: = {\ begin {bmatrix} 0 & -1 \\ 1 & 0 \ end {bmatrix}} {\ frac {x_ {2} -x_ {1}} {\ | x_ {2} -x_ {1} \ |}}}$

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 está dada por ${\ Displaystyle (p, {\ hat {n}})}$

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

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

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

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

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

Esto se puede reorganizar:

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

Para encontrar el mínimo, diferenciamos con respecto a xy igualamos el resultado al vector cero:

${\ Displaystyle {\ frac {\ E (x) parcial} {\ x} parcial = 0 = 2 \ izquierda (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n} } _ {i} ^ {\ top} \ right) x-2 \ left (\ sum _ {i} {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ arriba} p_ {i} \ right)}$

asi que

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

y entonces

${\ Displaystyle 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 más de dos dimensiones

Si bien no está bien definido en más de dos dimensiones, esto se puede generalizar a cualquier número de dimensiones observando que es simplemente la matriz (simétrica) con la unidad de todos los valores propios excepto un valor propio cero en la dirección a lo largo de la línea que proporciona una seminorma en la distancia entre y otro punto que da la distancia a la línea. En cualquier número de dimensiones, si es un vector unitario a lo largo de la i -ésima línea, entonces ${\ Displaystyle {\ hat {n}} _ {i}}$${\ Displaystyle {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top}}$${\ Displaystyle p_ {i}}$${\ Displaystyle {\ hat {v}} _ {i}}$

${\ Displaystyle {\ hat {n}} _ {i} {\ hat {n}} _ {i} ^ {\ top}}$ se convierte en ${\ Displaystyle I - {\ hat {v}} _ {i} {\ hat {v}} _ {i} ^ {\ top}}$

donde yo es la matriz de identidad, y así

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

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á definido por un origen y una dirección de vector unidad, . El cuadrado de la distancia de un punto a una de las líneas viene dado por Pitágoras: ${\ Displaystyle a_ {i}}$${\ Displaystyle n_ {i}}$${\ Displaystyle p}$

${\ Displaystyle d_ {i} ^ {2} = \ left \ | p-a_ {i} \ right \ | ^ {2} - \ left [\ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * n_ {i} \ right] ^ {2} = \ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * \ left (p-a_ {i} \ right) - \ left [\ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * n_ {i} \ right] ^ {2}}$

Donde: es la proyección de en la línea . La suma de distancias al cuadrado a todas las líneas es: ${\ Displaystyle {\ left (p-a_ {i} \ right)} ^ {\ mathsf {T}} * n_ {i}}$${\ Displaystyle \ left (p - {{a} _ {i}} \ right)}$${\ Displaystyle i}$

${\ Displaystyle \ sum _ {i} d_ {i} ^ {2} = \ sum _ {i} \ left [{\ left (p-a_ {i} \ right) ^ {\ mathsf {T}}} * \ left (p-a_ {i} \ right) - {\ left [\ left (p-a_ {i} \ right) ^ {\ mathsf {T}} * n_ {i} \ right] ^ {2}} \Derecha]}$

Para minimizar esta expresión, la diferenciamos con respecto a . ${\ Displaystyle p}$

${\ Displaystyle \ sum _ {i} \ left [2 * \ left (p-a_ {i} \ right) -2 * \ right [{{\ left (p-a_ {i} \ right)} ^ {\ " mathsf {T}}} * n_ {i}] * n_ {i}] = 0}$

${\ Displaystyle \ sum _ {i} \ left (p-a_ {i} \ right) = \ sum _ {i} \ left [n_ {i} * n_ {i} ^ {\ mathsf {T}} \ right ] * \ left (p-a_ {i} \ right)}$

Resulta:

${\ Displaystyle \ left [\ sum _ {i} \ left [I- {n_ {i}} * {n_ {i}} ^ {\ mathsf {T}} \ right] \ right] * p = \ sum _ {i} \ left [I- {n_ {i}} * {n_ {i}} ^ {\ mathsf {T}} \ right] * {a_ {i}}}$

¿Dónde está la matriz de identidad? Esta es una matriz , con solución , donde es el pseudo-inverso de . ${\ Displaystyle I}$${\ Displaystyle S * p = C}$${\ Displaystyle p = {S ^ {+}} * C}$${\ Displaystyle {S} ^ {+}}$${\ Displaystyle S}$

Ver también

• Intersección de segmento 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 línea-plano
• Postulado paralelo
• Triangulación (visión por computadora)
• Intersección (geometría euclidiana) § Dos segmentos de línea

Referencias

enlaces externos

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