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

Question

Duplicar posible:
How do you detect where two line segments intersect?

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

Answer 1

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

Answer 2

Eso realmente depende de cómo se representan las líneas. Voy a suponer que usted ha representado ellas en forma paramétrica

x (t) = u + t v

x (t) = u + t v

Aquí, los x 's, u' s, y v 's son vectores (denotado más en negrita) en ℜ yt ∈ [0, 1].

Estos dos puntos se cruzan si hay algún punto en ambos segmentos de línea. Así, si hay algún momento p de modo que hay al donde

p = x (t) = u + t v

y una s tal que

p = x (s) = u + s v

Y por otra parte, ambos s, t ∈ [0, 1], entonces las dos líneas se cruzan. De lo contrario, no lo hacen.

Si combinamos las dos igualdades, obtenemos

u + t v = u + s v

o, equivalentemente,

u - u = s v - t v

u = (x , y)

u = (x , y)

v = (x , y)

v = (x , y)

Si volvemos a escribir la expresión anterior en forma de matriz, ahora tenemos que

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

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

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

Ahora, tenemos dos casos 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 que

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

A continuación, la inversa de la matriz

| x11 x01 | 
| y11 y01 | 

está dada por

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

Tenga en cuenta que esta matriz no está definido 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 por encima de izquierda-multiplicando 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 | 

Así que esto significa que

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

Si ambos valores son en el rango [0, 1], los dos segmentos de línea se cruzan 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.