algorithm - Determinar si dos rayos se intersecan
math geometry (7)
Tengo dos rayos en un plano 2D que se extienden hasta el infinito, pero ambos tienen un punto de partida. Ambos están descritos por un punto de partida y un vector en la dirección del rayo que se extiende hasta el infinito. Quiero saber si los dos rayos se intersecan, pero no necesito saber dónde se intersecan (es parte de un algoritmo de detección de colisión).
Todo lo que he visto hasta ahora describe cómo encontrar el punto de intersección de dos líneas o segmentos de línea. ¿Hay un algoritmo rápido para resolver esto?
Dados: dos rayos a, b con puntos de inicio (vectores de origen) como, bs y vectores de dirección ad, bd.
Las dos líneas se intersecan si hay un punto de intersección p:
p = as + ad * u
p = bs + bd * v
Si este sistema de ecuaciones tiene una solución para u> = 0 y v> = 0 (la dirección positiva es lo que hace que los rayos), los rayos se intersecan.
Para las coordenadas x / y de los vectores 2d, esto significa:
p.x = as.x + ad.x * u
p.y = as.y + ad.y * u
p.x = bs.x + bd.x * v
p.y = bs.y + bd.y * v
Más pasos:
as.x + ad.x * u = bs.x + bd.x * v
as.y + ad.y * u = bs.y + bd.y * v
Resolviendo contra v:
v := (as.x + ad.x * u - bs.x) / bd.x
Insertando y resolviendo contra u:
as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x)
u := (as.y*bd.x + bd.y*bs.x - bs.y*bd.x - bd.y*as.x ) / (ad.x*bd.y - ad.y*bd.x)
Calcule u, luego calcule v, si ambos son positivos, los rayos se intersecan, de lo contrario no.
Lamento no estar de acuerdo con la respuesta de Peter Walser. Resolviendo las ecuaciones da en mi escritorio:
u = ((bs.y - as.y) * bd.x - (bs.x - as.x) * bd.y) / (bd.x * ad.y - bd.y * ad.x)
v = ((bs.y - as.y) * ad.x - (bs.x - as.x) * ad.y) / (bd.x * ad.y - bd.y * ad.x)
Factorizando los términos comunes, esto viene a:
dx = bs.x - as.x
dy = bs.y - as.y
det = bd.x * ad.y - bd.y * ad.x
u = (dy * bd.x - dx * bd.y) / det
v = (dy * ad.x - dx * ad.y) / det
Cinco restas, seis multiplicaciones y dos divisiones.
Si solo necesita saber si los rayos se intersecan, los signos de uyv son suficientes, y estas dos divisiones pueden reemplazarse por num * denomin <0 o (sign (num)! = Sign (denom)), dependiendo de lo que Es más eficiente en su máquina de destino.
Tenga en cuenta que el caso raro de det == 0 significa que los rayos no se intersecan (una comparación adicional).
Las líneas están representadas por un punto p y un vector v :
línea = p + a * v (para todos a)
Los rayos son (la positiva) la mitad de esa línea:
ray = p + a * v (para todos a> = 0)
Para determinar si dos líneas se intersecan, haz que sean iguales y resuelve:
la intersección ocurre donde p 1 + a 1 * v 1 = p 2 + a 2 * v 2
(note que hay dos incógnitas, una 1 y una 2 , y dos ecuaciones, ya que las p y v son multidimensionales)
Resuelva para un 1 y un 2 - si ambos no son negativos, se intersecan. Si uno es negativo, no se cruzan.
Sólo quiero comprobar si los dos rayos se cruzan. Lo haré al calcular la dirección de rotación de dos "triángulos" creados a partir de los dos rayos. No son realmente triángulos, pero desde un punto de vista matemático, si solo quisiera calcular la rotación del triángulo, solo necesito dos vectores con un punto de partida común, y el resto no importa.
El primer triángulo estará formado por dos vectores y un punto de partida. El punto de partida será el punto de partida del primer rayo. El primer vector será el vector de dirección del primer rayo. El segundo vector será el vector desde el punto de inicio del primer rayo hasta el punto de inicio del segundo rayo. Desde aquí tomamos el producto cruzado de los dos vectores y observamos el signo.
Hacemos esto de nuevo para el segundo triángulo. De nuevo, el punto de partida es el punto de partida del segundo rayo. El primer vector es la dirección del segundo rayo y el segundo vector es desde el punto inicial del segundo rayo hasta el punto inicial del primer rayo. Tomamos nuevamente el producto cruzado de los vectores y notamos el signo.
Ahora simplemente tomamos las dos señales y verificamos si son iguales. Si son iguales, no tenemos intersección. Si son diferentes tenemos una intersección. ¡Eso es!
Aquí hay un código de psudo:
sign1 = cross(vector1, point1 - point2)
sign2 = cross(vector2, point2 - point1)
if (sign1 * sign2 < 0) // If signs are mismatched, they will multiply to be negative
return intersection
Resulta ser cinco multiplicaciones, seis restas y una comparación.
Si las líneas son de longitud infinita, entonces siempre se intersectarán, a menos que sean paralelas. Para verificar si son paralelos, encuentra la pendiente de cada línea y compáralas. La pendiente será (y2-y1) / (x2-x1).
Un rayo se puede representar mediante el conjunto de puntos A + Vt , donde A es el punto de inicio, V es un vector que indica la dirección del rayo y t >= 0 es el parámetro. Por lo tanto, para determinar si dos rayos se intersecan, haz esto:
bool DoRaysIntersect(Ray r1, Ray r2)
{
// Solve the following equations for t1 and t2:
// r1.A.x + r1.V.x * t1 == r2.A.x + r2.V.x * t2
// r1.A.y + r1.V.y * t1 == r2.A.y + r2.V.y * t2
if(no solution) // (e.g. parallel lines)
{
if(r1 == r2) // same ray?
return true;
else
return false; // parallel, non-intersecting
}
else // unique solution
{
if(t1 >= 0 && t2 >= 0)
return true;
else
return false; // they would intersect if they are lines, but they are not lines
}
}
GeomAlgorithms.com tiene algunos algoritmos bastante dulces que tratan con líneas en 3D ... Sin embargo, en términos generales, la probabilidad de que dos líneas se crucen en el espacio 3D es bastante baja.
En 2D, hay que comprobar la pendiente. Si la pendiente no es igual, entonces se intersecan. Si la pendiente es igual, se intersecan si un punto en ellos tiene la misma coordenada x o la misma coordenada y.