¿Determinando si dos segmentos de línea se cruzan?

Posible duplicado:
¿Cómo se detecta dónde se cruzan dos segmentos de línea?

¿Puede alguien proporcionar un algoritmo o código C para determinar si dos segmentos de línea se cruzan?

Eso realmente depende de cómo se representan las líneas. Voy a suponer que los tienes representados en la forma paramétrica

x 0 (t) = u 0 + t v 0

x 1 (t) = u 1 + t v 1

Aquí, las x ‘s, u ‘ s y v ‘s son vectores (más en negrita) en 2 y t ∈ [0, 1].

Estos dos puntos se cruzan si hay algún punto que esté en ambos segmentos de línea. Por lo tanto, si hay algún punto p para que haya en donde

p = x 0 (t) = u 0 + t v 0

y una s tal que

p = x 1 (s) = u 1 + s v 1

Y, además, tanto s, t ∈ [0, 1], entonces las dos líneas se cruzan. De lo contrario, no lo hacen.

Si combinamos las dos igualdades, obtenemos

u 0 + t v 0 = u 1 + s v 1

O equivalente,

u 0u 1 = s v 1 – t v 0

u 0 = (x 00 , y 00 )

u 1 = (x 10 , y 10 )

v 0 = (x 01 , y 01 )

v 1 = (x 11 , y 11 )

Si reescribimos la expresión anterior en forma de matriz, ahora tenemos eso

| x00 - x10 | | x11 | | x01 | | y00 - y10 | = | y11 | s - | y01 | t 

Esto a su vez es equivalente a la expresión de la matriz

 | x00 - x10 | | x11 x01 | | s| | y00 - y10 | = | y11 y01 | |-t| 

Ahora, tenemos dos casos para considerar. Primero, si este lado izquierdo es el vector cero, entonces hay una solución trivial: simplemente establezca s = t = 0 y los puntos se crucen. De lo contrario, hay una solución única solo si la matriz de la derecha es invertible. Si dejamos

  | x11 x01 | d = det(| y11 y01 |) = x11 y01 - x01 y11 

Entonces el inverso de la matriz

 | x11 x01 | | y11 y01 | 

es dado por

  | y01 -x01 | (1/d) | -y11 x11 | 

Tenga en cuenta que esta matriz no se define si el determinante es cero, pero si eso es cierto, significa que las líneas son paralelas y, por lo tanto, no se cruzan.

Si la matriz es invertible, entonces podemos resolver el sistema lineal anterior multiplicando a la izquierda por esta matriz:

  | s| | y01 -x01 | | x00 - x10 | |-t| = (1/d) | -y11 x11 | | y00 - y10 | | (x00 - x10) y01 - (y00 - y10) x01 | = (1/d) | -(x00 - x10) y11 + (y00 - y10) x11 | 

Entonces esto significa que

 s = (1/d) ((x00 - x10) y01 - (y00 - y10) x01) t = (1/d) -(-(x00 - x10) y11 + (y00 - y10) x11) 

Si ambos valores están en el rango [0, 1], los dos segmentos de línea se intersectan y puede calcular el punto de intersección. De lo contrario, no se cruzan. Además, si d es cero, las dos líneas son paralelas, lo que puede o no ser de su interés. Codificar esto en C no debería ser tan malo; solo debe asegurarse de tener cuidado de no dividir por cero.

¡Espero que esto ayude! Si alguien puede verificar las matemáticas, sería genial.

Puedes construir una ecuación para dos líneas, encontrar el punto de intersección y luego verificar si pertenece a esos segmentos.