341 votos

¿Cómo se detecta donde se cruzan dos segmentos de línea?

¿Cómo puedo determinar si dos rectas se intersecan, y si lo hacen, en lo que x, y punto.

400voto

Gareth Rees Puntos 31350

Hay un buen enfoque a este problema que utiliza el vector de productos cruzados. Definir la 2-dimensional vector producto vectorial v × w a vxwy z - vywx (esta es la magnitud de las 3 dimensiones de la cruz del producto).

Supongamos que los dos segmentos de línea de ejecución de p a p + r y desde q a p + s. Entonces cualquier punto en la primera línea es representable como p + t r (para un parámetro escalar t) y cualquier punto de la segunda línea como q + u s (por un escalar parámetro u).

Two line segments intersecting

Se cruzan las dos líneas si podemos encontrar t y u tales que:

p + t r = p + u s

Formulae for the point of intersection

Cruz de ambos lados con s, llegar

(p + t r) × s = (q + u s) × s

Y puesto que s × s = 0, esto significa

t (r × s) = (q - p) × s

Y por lo tanto, la solución para t:

t = (q - p) × s / (r × s)

De la misma manera, podemos resolver para la u:

(p + t r) × r = (q + u s) × r

u (s × r) = (p - q) × r

u = (p - q) × r / (s x r)

Para reducir el número de computación pasos, es conveniente reescribir de la siguiente manera (recordando que s × r = - r × s):

u = (q - p) × r / (r × s)

Ahora hay cinco casos:

  1. Si r × s = 0 y (p - p) × r = 0, entonces las dos líneas son colineales. Si además, con 0 ≤ (p - p) · rr · r o 0 ≤ (p - q) · ss · s, las dos líneas se superponen.

  2. Si r × s = 0 y (p - p) × r = 0, pero ni el 0 ≤ (p - p) · rr · r ni 0 ≤ (p - q) · ss · s, las dos líneas son colineales, pero distinto.

  3. Si r × s = 0 y (p - p) × r ≠ 0, entonces las dos rectas son paralelas y no de intersección.

  4. Si r × s ≠ 0 y 0 ≤ t ≤ 1 y 0 ≤ u ≤ 1, los dos segmentos de línea que se reúnen en el punto p + t r = p + u s.

  5. De lo contrario, los dos segmentos de línea no son paralelas, pero no se cruzan.

(Crédito: este método es el 2-dimensional de la especialización de las 3D de la línea de intersección algoritmo en el artículo "la Intersección de dos líneas en el espacio de tres" por Ronald Goldman, la publica en los Gráficos de las Gemas, página 304. En tres dimensiones, en el caso habitual es que las líneas son desfase (ni paralelo ni de intersección), en cuyo caso el método da los puntos de mayor acercamiento de las dos líneas).

144voto

Gavin Puntos 3871

FWIW, la siguiente función (en C) ambos detecta las intersecciones y determina el punto de intersección. Se basa en un algoritmo de Andre LeMothe "Trucos de Windows de la Programación del Juego Gurús". Es muy parecida a la de algunos de los del algoritmo en otras respuestas (por ej. Gareth). LeMothe, a continuación, utiliza la Regla de Cramer (no me pregunten) para resolver las ecuaciones de sí mismos.

Puedo dar fe de que funciona en mi débil asteroides clon, y parece tratar correctamente con el borde de los casos descritos en otras respuestas, por Elemental, Dan y Wodzu. Es también, probablemente, más rápido que el código publicado por KingNestor porque es todo de la multiplicación y la división, sin raíces cuadradas!

Supongo que hay cierto potencial para dividir por cero allí, pese a que no ha sido un problema en mi caso. Bastante fácil de modificar para evitar el choque de todos modos.

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision
}

Por CIERTO, debo decir que en LeMothe del libro, a pesar de que aparentemente se presenta el algoritmo de derecho, el ejemplo concreto que se muestra en los enchufes mal los números y hace cálculos equivocados. Por ejemplo:

(4 * (4 - 1) + 12 * (7 - 1)) / (17 * 4 + 12 * 10)

= 844/0 .88

= 0.44

Que me confundió por horas. :(

54voto

Jason Cohen Puntos 36475

El problema se reduce a esta pregunta: ¿dos líneas de a a B y de C a D se cruzan? Entonces usted puede hacer es cuatro veces (entre la línea y cada uno de los cuatro lados del rectángulo).

Aquí está el vector de matemáticas para hacerlo. Estoy suponiendo que la línea entre a y B es la línea en cuestión y la línea de C a D es una de las rectángulo de líneas. Mi notación es que Ax es la "coordenada x de Un" y Cy es la "coordenada y de la C." Y "*" medio punto del producto, así por ejemplo. A*B = Ax*Bx + Ay*By.

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

Este h número es la clave. Si h entre 0 y 1, las líneas se cruzan, de lo contrario no. Si F*P es cero, por supuesto no se puede hacer el cálculo, pero en este caso, las rectas son paralelas y por lo tanto sólo se cruzan en los casos obvios.

El punto exacto de intersección es C + F*h.

Más Diversión:

Si h es exactamente 0 o 1 de las líneas se toquen en un punto final. Se puede considerar esto como una "intersección" o no se como le parezca.

Específicamente, h es cuánto hay que multiplicar la longitud de la línea en el orden exactamente a tocar a la otra línea.

Por lo tanto, Si h<0, significa que el rectángulo de línea está "detrás" de la línea (con la "dirección" ser "de la a a la B"), y si h>1 el rectángulo de línea "en el frente" de la línea dada.

Derivación:

A y C son vectores que apuntan al inicio de la línea; E y F son los vectores de los extremos de a y C que forman la línea.

Para cualquiera de las dos líneas no paralelas en el plano, debe haber exactamente un par de escalares g y h tal que esta ecuación se tiene:

A + E*g = C + F*h

¿Por qué? Debido a que dos líneas no paralelas han de cruzarse, lo que significa que usted puede cambiar la escala de ambas líneas por cierta cantidad cada tocar a otro.

(Al principio, esto parece a una sola ecuación con dos incógnitas! Pero no lo es cuando se considera que esta es una ecuación vectorial 2D, lo que significa que es en realidad un par de ecuaciones en x y y.)

Tenemos que eliminar una de estas variables. Una manera fácil es hacer la E plazo de cero. Para hacer eso, tomar las dot-producto de ambos lados de la ecuación, utilizando un vector que va de punto a cero con E. Que el vector llamé P arriba, y me hizo la evidente transformación de E.

Ahora usted tiene:

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h

40voto

Elemental Puntos 4997

He tratado de aplicar el algoritmo, por lo que elegantemente se describe por Jason arriba; por desgracia, mientras que el trabajo a pesar de la matemática en la depuración he encontrado muchos casos en los que no funciona.

Por ejemplo, considere los puntos a(10,10) B(20,20) C(10,1) D(1,10) da h=.5 y, sin embargo, es claro por el examen que estos segmentos son no-donde cerca unos de otros.

Graficar esto deja claro que 0 < h < 1 criterios sólo se indica que el punto de intercepción se encuentran en el CD si es que existían, pero dice nada de si el punto se encuentra en AB. Para asegurarse de que la cruz es un punto que debe hacer el simétrico de cálculo para la variable g y el requisito para la interceptación es: 0 < g < 1 Y 0 < h < 1

30voto

iMalc Puntos 181

Aquí es una mejora a Gavin la respuesta. marcp la solución es similar también, pero ni posponer la división.

Esta realidad resulta ser una aplicación práctica de Gareth Rees' contestar, porque el intercambio de productos equivalentes en 2D es el asesino-punto-producto, que es lo que este código utiliza tres. El cambio a 3D y el uso de la cruz-producto, interpolando tanto s como t al final, los resultados en los dos puntos más cercanos entre líneas en 3D. De todos modos, la solución de 2D:

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

Básicamente se pospone la división hasta el último momento, y mueve la mayoría de las pruebas hasta antes de ciertos cálculos se hacen, con lo que la adición de principios-outs. Por último, también se evita la división por cero en caso que se produce cuando las líneas son paralelas.

Es posible que también desee considerar el uso de un epsilon prueba en lugar de la comparación contra cero. Las líneas que están muy cerca del paralelo puede producir resultados que son un poco fuera. Este no es un bug, es una limitación con aritmética de punto flotante.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X