¿Cómo detectar la colisión 2D en línea?

13

Soy un desarrollador de juegos Flash ActionScript que está un poco atrasado con las matemáticas, aunque encuentro que la física es interesante y genial.

Como referencia, este es un juego similar al que estoy haciendo: juego flash desenredado

He hecho este juego desenredado casi hasta completar la lógica. Pero, cuando dos líneas se cruzan, necesito que esas líneas cruzadas o 'enredadas' muestren un color diferente; rojo.

Sería muy amable de su parte si pudieran sugerir un algoritmo para detectar colisiones de segmentos de línea . Básicamente soy una persona a la que le gusta pensar 'visualmente' que 'aritméticamente' :)

Editar: me gustaría agregar algunos diagramas para transmitir la idea más claramente

sin intersección sin intersección intersección sin intersección

PD Estoy tratando de hacer una función como

private function isIntersecting(A:Point, B:Point, C:Point, D:Point):Boolean

Gracias por adelantado.

Vishnu
fuente
66
Esta es una explicación decepcionantemente no visual del problema, pero es un algoritmo y tiene sentido si puede leer sus matemáticas: local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d Puede ser pesado si su matemática vectorial es débil. Entiendo, también prefiero explicaciones visuales. Trataré de encontrar tiempo más tarde para garabatear esto, pero si alguien con inclinación artística ve este enlace y tiene tiempo antes que yo, ¡póntelo!
Anko

Respuestas:

18

Utilizo el siguiente método, que es prácticamente solo una implementación de este algoritmo . Está en C #, pero traducirlo a ActionScript debería ser trivial.

bool IsIntersecting(Point a, Point b, Point c, Point d)
{
    float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));
    float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));
    float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

    // Detect coincident lines (has a problem, read below)
    if (denominator == 0) return numerator1 == 0 && numerator2 == 0;

    float r = numerator1 / denominator;
    float s = numerator2 / denominator;

    return (r >= 0 && r <= 1) && (s >= 0 && s <= 1);
}

Sin embargo, hay un problema sutil con el algoritmo, que es el caso en el que dos líneas coinciden pero no se superponen. El algoritmo aún devuelve una intersección en ese caso. Si le importa ese caso, creo que esta respuesta en stackoverflow tiene una versión más compleja que lo aborda.

Editar

No obtuve un resultado de este algoritmo, lo siento.

Es extraño, lo he probado y está funcionando para mí, excepto por el caso que describí anteriormente. Usando exactamente la misma versión que publiqué anteriormente, obtuve estos resultados cuando lo tomé para una prueba de manejo:

ingrese la descripción de la imagen aquí

David Gouveia
fuente
No obtuve un resultado de este algoritmo, lo siento.
Vishnu
44
@Vish ¿Qué problema tuviste? Probé esta copia exacta del algoritmo antes de publicar y funcionó a la perfección, excepto por el caso único descrito.
David Gouveia
Entonces, déjame intentarlo de nuevo, podría haber mezclado algunas matemáticas. Te lo haré saber pronto. Muchas gracias, nyways :)
Vishnu
1
Obtuve el resultado deseado de su algoritmo, gracias @DavidGouveia.
Vishnu
1
Bueno, pero ahora tengo otro problema :)! Necesito hacer las líneas intersectadas con color rojo y verde. La intersección funciona bien. Pero como he entendido ahora (aunque no matemáticamente), un simple if-else no funcionará para poner líneas rojas y verdes para líneas intersectadas y no intersectadas. El nodo que estoy arrastrando tiene una línea izquierda y derecha. Entonces, algo salió mal en algún lugar al cambiar el color de las líneas no intersectadas a verde. Supongo que también necesito otra condición. Hmmm, de todos modos muchas gracias, estoy marcando esto como la respuesta correcta.
Vishnu
4

Sin divisiones! Así que no hay problema con la precisión ni por división por cero.

El segmento de línea 1 es de A a B El segmento de línea 2 es de C a D

Una línea es una línea interminable, el segmento de línea es una parte definida de esa línea.

Compruebe si las dos cajas delimitadas se cruzan: si no hay intersección -> ¡Sin cruz! (cálculo realizado, devuelve falso)

Compruebe si la línea seg 1 se extiende a ambos lados de la línea seg 2 y si la línea seg 2 se extiende a ambos lados de la línea seg 1 (es decir, la línea Segmento 1 está a ambos lados de la Línea definida por la línea Segmento 2).

Esto se puede hacer traduciendo todos los puntos por -A (es decir, mueve las 2 líneas para que A esté en origo (0,0))

Luego verifica si los puntos C y D están en diferentes lados de la línea definida por 0,0 a B

//Cross Product (hope I got it right here)
float fC= (B.x*C.y) - (B.y*C.x); //<0 == to the left, >0 == to the right
float fD= (B.x*D.y) - (B.y*D.x);

if( (fc<0) && (fd<0)) //both to the left  -> No Cross!
if( (fc>0) && (fd>0)) //both to the right -> No Cross!

Si aún no tiene un "No Cross", continúe usando no A, B versus C, D sino C, D versus A, B (los mismos cálculos, simplemente cambie A y C, B y D), si no hay "¡No cruz!" entonces tienes una intersección!

Busqué los cálculos exactos para el producto cruzado y encontré esta publicación de blog que explica el método también.

Valmond
fuente
1
Lo siento, pero no soy muy bueno con las matemáticas vectoriales, implementé este algoritmo como tal, pero no obtuve ningún resultado, ¡lo siento!
Vishnu
1
Debería funcionar, así que tal vez si nos puede mostrar su código, ¿podemos ayudarlo?
Valmond
¡Agradable! sin embargo, el vínculo se rompe
clabe45
¿Hay algo que puede agregar a esto para obtener el punto de intersección?
SeanRamey
1

Solo quiero decir que lo necesitaba para mi juego Gamemaker Studio y funciona bien:

///scr_line_collision(x1,y1,x2,y2,x3,y3,x4,y4)

var denominator= ((argument2 - argument0) * (argument7 - argument5)) - ((argument3 - argument1) * (argument6 - argument4));
var numerator1 = ((argument1 - argument5) * (argument6 - argument4)) - ((argument0 - argument4) * (argument7 - argument5));
var numerator2 = ((argument1 - argument5) * (argument2 - argument0)) - ((argument0 - argument4) * (argument3 - argument1));

// Detect coincident lines
if (denominator == 0) {return (numerator1 == 0 && numerator2 == 0)}

var r = numerator1 / denominator;
var s = numerator2 / denominator;

return ((r >= 0 && r <= 1) && (s >= 0 && s <= 1));
Lukáš Čulen
fuente
Creo que esta respuesta realmente podría mejorar si explicaras lo que hace el código.
TomTsagk
1

La respuesta aceptada dio una respuesta incorrecta en este caso:

x1 = 0;
y1 = 0;
x2 = 10;
y2 = 10;

x3 = 10.1;
y3 = 10.1;
x4 = 15;
y4 = 15;

Estas líneas obviamente no se cruzan, pero de acuerdo con la función en la "respuesta correcta" las líneas se cruzan.

Esto es lo que uso:

function do_lines_intersect(px1,py1,px2,py2,px3,py3,px4,py4) {
  var ua = 0.0;
  var ub = 0.0;
  var ud = (py4 - py3) * (px2 - px1) - (px4 - px3) * (py2 - py1);


  if (ud != 0) {
    ua = ((px4 - px3) * (py1 - py3) - (py4 - py3) * (px1 - px3)) / ud;
    ub = ((px2 - px1) * (py1 - py3) - (py2 - py1) * (px1 - px3)) / ud;
        if (ua < 0.0 || ua > 1.0 || ub < 0.0 || ub > 1.0) ua = 0.0;
  }

  return ua;
}

devuelve 0 = las líneas no se cruzan

devuelve> 0 = las líneas se cruzan


Actualiza para responder la pregunta:

No creé este código yo mismo. Tiene más de 5 años y no sé cuál es la fuente original. Pero..

Creo que el valor de retorno es la posición relativa de la primera línea donde se cruzan (para explicarlo mal). Para calcular el punto de intersección, probablemente podría usar lerp de esta manera:

l = do_lines_intersect(...)
if (l > 0) {
    intersect_pos_x = l * (px2-px1);
    intersect_pos_y = l * (py2-py1);
} else {
    // lines do not cross
}

(NO PROBÉ ESTO)

Jorammer
fuente
¿Existe una versión de esto que devuelva el punto de intersección?
SeanRamey