Determinar exactamente si/cuando/donde una línea en movimiento interseca un punto en movimiento

noviembre 3, 2021

Determinar exactamente si/cuando/donde una línea en movimiento interseca un punto en movimiento
Destino
Intuición
Modelo
Solución
Generalizando
Resumen
Discute en Reddit
Archivo

posteado por Craig Gidney el 5 de febrero de 2013

Intento incluir proyectos de muestra cuando publico bibliotecas. En el caso de las colecciones perecederas, el proyecto de muestra era en realidad un sencillo juego basado en cortar líneas con el puntero del ratón:

Como parte de la escritura de la muestra, tuve que resolver el problema de determinar si el puntero del ratón era barrido por una línea, cuándo y dónde (o viceversa). Mi referencia habitual para algoritmos de geometría no contenía una solución, así que desarrollé una yo mismo.

En este post explicaré una solución analítica al problema. La solución está implementada en una pequeña cantidad de código fuente (unas 150 líneas, contando los comentarios y los métodos/tipos de apoyo), también disponible en github.

Destino

Resulta que «¿el puntero del ratón cortó la línea en movimiento?» es uno de esos problemas matemáticos mágicos que comienza con algunas restricciones relativamente simples, luego parece complicarse bastante a medida que lo resuelves, pero luego casi todo se cancela o combina en los últimos pasos y terminas con algo absurdamente simple. (Luego, cuando vuelves a revisar la solución, resulta que había un camino fácil todo el tiempo.)

Para referencia y motivación, voy a volcar la carne de la implementación aquí mismo, antes de explicarla. Las palabras subrayadas son enlaces al código correspondiente en github.

public static IEnumerable<Sweep> WhenLineSweepsPoint(LineSegment pathOfLineStartPoint, LineSegment pathOfLineEndPoint, Point point) {var a = point - pathOfLineStartPoint.Start;var b = -pathOfLineStartPoint.Delta;var c = pathOfLineEndPoint.Start - pathOfLineStartPoint.Start;var d = pathOfLineEndPoint.Delta - pathOfLineStartPoint.Delta;return from t in QuadraticRoots(b.Cross(d), a.Cross(d) + b.Cross(c), a.Cross(c)) where t >= 0 && t <= 1 let start = pathOfLineStartPoint.LerpAcross(t) let end = pathOfLineEndPoint.LerpAcross(t) let s = point.LerpProjectOnto(new LineSegment(start, end)) where s >= 0 && s <= 1 orderby t select new Sweep(timeProportion: t, acrossProportion: s);}

No sé vosotros, pero el hecho de que el código anterior resuelva el problema me sorprende. Parece demasiado sencillo y, a la vez, demasiado inconexo. ¿No debería haber, por ejemplo, casos de esquina? Además, ¿de dónde vienen esos productos cruzados simples? ¿Cómo ayuda el introducirlos en un polinomio cuadrático? Esto… va a necesitar ser explicado.

Intuición

Comencemos por considerar algunos de los casos que podríamos encontrar, para tener una sensación intuitiva del problema. La siguiente animación muestra varios movimientos posibles de la línea:

Simple: ambos extremos se mueven a la misma velocidad, y sólo a lo largo del vector normal de la línea.
Lateral: un caso degenerado en el que la línea se mueve a lo largo de su propia longitud.
Elevación: un extremo se mueve horizontalmente mientras el otro se mueve verticalmente (‘elevando’ y bajando la línea).
Inmersión: uno de los extremos se mueve en diagonal («inmersión» por el centro) mientras el otro se mueve verticalmente.

Varios casos de barrido

Nótese que una línea puede barrer un punto 0, 1 ó 2 veces ya que sus extremos se mueven a una velocidad constante de una posición a otra. El caso de «Levantar» contiene convenientemente las tres posibilidades. Esto, intuitivamente, es la razón por la que la solución implica una ecuación cuadrática (que puede tener 0, 1 o 2 raíces reales distintas).

Otra realización útil es que algunos de los casos, como la línea que se mueve a un ritmo constante o que se queda quieta, corresponderán a ecuaciones cuadráticas degeneradas donde el coeficiente de mayor orden es cero (es decir, o incluso ). Necesitamos incluir este tipo de casos en las pruebas.

Modelo

Para que un segmento de línea desde hasta contenga un punto , deben cumplirse dos condiciones. En primer lugar, el vector ‘offset’ de a debe ser paralelo al vector ‘delta’ de a . Podemos representar esto matemáticamente exigiendo que su producto cruzado sea cero: $(c-p) \N por (q-p) = 0$ . Esto garantiza que está en la línea que se obtiene al extender el segmento de línea en ambas direcciones (o que se tiene un segmento de línea degenerado de un solo punto). En segundo lugar, la proyección escalar del vector desplazamiento sobre el vector delta debe estar en el rango correcto: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Esto garantiza que no pasa por ninguno de los puntos finales del segmento.

Como el tiempo va de a , nuestro segmento de línea habrá barrido un punto si y sólo si hay un tiempo en el que el segmento de línea actual contiene . Como los puntos finales de nuestro segmento de línea se mueven a una velocidad constante, la trayectoria que siguen es también un segmento de línea. Un punto final que se mueva de a estará en el punto interpolado linealmente $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ en el tiempo . Ten en cuenta que voy a abreviar como para ahorrar espacio. Introduciendo nuestros puntos en movimiento en nuestras fórmulas de ‘segmento de línea contiene punto’ nos dice que debemos encontrar que satisfaga $0 \leq t \leq 1$ y $(c - (p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ y $0 \leq s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2} \leq 1$ .

Nota que «algún producto cruzado debe ser igual a 0″ no es la única forma de enmarcar el problema. También tiene sentido pensar en ello como encontrar un y , ambos en el rango , tal que es el resultado de lerpear ambos puntos finales a través de su camino por y luego lerpear entre los puntos finales por . Matemáticamente, esto significa . Las variables y corresponden aproximadamente a «cuándo» y «dónde» se produce una intersección. Sin embargo, es más difícil resolver el problema de esta forma, porque no está inicialmente aislado, así que usaré el encuadre del producto cruzado (a diferencia de lo que hice la primera vez…).

Solución

El producto cruzado y el producto punto tienen algunas propiedades muy buenas que harán más fácil aislar . En primer lugar, distribuyen la adición, lo que significa que $u \times (v + w) = u \times v + u \times w$ y $u \cdot (v + w) = u \cdot v + u \cdot w$ . En segundo lugar, el escalamiento puede hacerse antes o después de cualquiera de los dos productos, lo que significa que $(c \cdot u) \times v = c \cdot (u \cdot v)$ y $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , donde es un número real. Finalmente, el producto punto es conmutativo, es decir, $u \cdot v = v \cdot u$ , mientras que el producto cruz es anticomutativo, es decir, $u \cdot v = -v \cdot u$ .

Aplicando este conocimiento del producto, y utilizando un poco de retrospectiva para saber tratar sub-expresiones particulares como variables individuales, podemos transformar nuestra ecuación de producto cruzado-es-cero en una ecuación cuadrática:

begin{align*} 0 =(c – (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) \= ((c – p_0) – p_d \cdot t) \times ((q_0 – p_0) – (q_d – p_d) \cdot t) \= (a + b \cdot t) \times (c + d \cdot t) \\;\;\\cdot\N – donde;\N – a = c – p_0 \N – donde;\N – b = -p_d \N – donde;\N – c = q_0 – p_0 \N – donde;\N – d; d = -(q_d – p_d) \= a \times c + a \times d \cdot t + b \times c \cdot t + b \times d \cdot t \cdot t \= t^2 \cdot (b \times d) + t \cdot (a \(a) + (b) + (c).)

Ah, ahora está claro de dónde viene la forma de la solución del código. Empezamos con un producto cruzado igual a cero (afirmando que el vector de la recta al punto era paralelo a la recta) y tuvimos que dividir el producto para aislar las sumas de términos que implican diferentes potencias de . Esto, naturalmente, da lugar a una ecuación cuadrática con coeficientes que implican productos cruzados. Obsérvese que se trata de una ecuación muy «robusta», porque nunca asumimos nada sobre los vectores o escalares en el camino. Por ejemplo, nunca dividimos (o cancelamos implícitamente) por una variable, por lo que no hemos introducido ninguna condición acechante distinta de cero.

Con la ecuación simplificada, la determinación de los posibles valores de es simplemente una cosa estándar de «resolver un polinomio cuadrático». Tenemos que manejar los casos de esquina con ceros, lo que hace que el código un poco más complicado, pero es sólo aburrido caso por caso, así que sólo voy a enlazar a ella.

Una vez que sabemos un posible valor de , podemos averiguar exactamente donde se produjo la colisión mediante el plug-t-en la línea-segmento-punto de contención fórmula mencionó un camino de regreso: $s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}$ . Llamo a esta fórmula la «proyección lerp» de sobre la línea en el momento , porque devuelve la proporción por la que hay que lerpar, desde el punto inicial de la línea hasta su punto final, para recuperar . Es un pequeño método práctico para extraer:

public static double LerpProjectOnto(this Point point, LineSegment line) { var b = point - line.Start; var d = line.Delta; return (b * d) / (d * d); // when d == 0, result is +-infinity or NaN}

Por último, una vez que tenemos y , tenemos que comprobar que están en el rango . Si está fuera del rango, entonces la colisión no se producirá durante el paso de tiempo actual. Si está fuera del rango entonces la colisión ocurrirá en la línea extendida, pero no en el segmento de línea. Dado que y describen cuánto hay que lerpar para encontrar cuándo/donde se ha producido la colisión, también es una información útil para devolver al llamante.

Generalizando

Un detalle importante que no he mencionado todavía es que un puntero de ratón en movimiento obviamente no se corresponde con un punto. Por suerte, podemos anular el movimiento del puntero del ratón en el último paso de tiempo (suponiendo que sea lineal) deduciéndolo del movimiento del segmento de línea. Esto no sólo reduce el sistema a uno resoluble, sino que los valores y resultantes son válidos sin ningún tipo de transformación inversa. El uso se ve así:

// time goes from t0 to t1// line segment endpoint 1 moves from p0 to p1// line segment endpoint 2 moves from q0 to q1// point moves from c0 to c1var results = from hit in WhenLineSweepsPoint(new LineSegment(p0 - c0, p1 - c1), new LineSegment(q0 - c0, q1 - c1), new Point(0, 0)) let hitPos = new LineSegment(c0, c1).LerpAcross(hit.TimeProportion) let hitTime = t0 + (t1-t0)*hit.TimeProportion select new { p = hitPos, t = hitTime }foreach (var result in results) { System.Diagnostics.Debug.WriteLine(string.Format("Hit at p={0}, t={1}", result.p, result.t);}

Una complicación potencial son los segmentos de línea degenerados que no tienen longitud (donde ambos puntos finales son iguales). El código no maneja explícitamente este caso, pero actuará como si cortar una línea que es realmente un punto fuera imposible. El cálculo de , si se alcanza, se dividirá por cero. El resultado (ya sea -infinito, +infinito, o NaN) fallará la comprobación del rango.

Otro aspecto que no he cubierto es el ‘ángulo de corte’. En la animación que muestra los distintos casos, los cortes rojos se orientan lerpeando entre las velocidades de los dos extremos por (cuando la velocidad resultante es 0, se elige un ángulo aleatorio). Pero también he utilizado enfoques alternativos como «el ángulo de corte es la velocidad del punto». Básicamente, es un caso de usar lo que se ve bien y se siente natural en lugar de tratar de averiguar el verdadero significado de «ángulo de corte».

Resumen

Este problema se convierte en trivial tan pronto como usted aplica algunos conocimientos de álgebra lineal. Supongo que no es demasiado sorprendente, ya que el álgebra lineal (y los polinomios) aparecen en todas partes, especialmente en geometría.

Una generalización natural de este problema es incluir los grosores. Las líneas dibujadas en las pantallas no son infinitamente delgadas, después de todo. Tener un grosor es también una buena manera de reducir el efecto de los errores de punto flotante redondeando en diferentes direcciones durante diferentes pasos de tiempo. Otro cambio útil sería la capacidad de manejar trayectorias parabólicas, ya que los objetos del juego están a menudo en caída libre. Por otro lado, supongo que probablemente sea más fácil tratar las ‘líneas gruesas’ como polígonos con pasos de tiempo de velocidad constante.

–

Discute en Reddit

–

Twisted Oak Studios ofrece consultoría y desarrollo en proyectos interactivos de alta tecnología. Echa un vistazo a nuestro portafolio, o danos un grito si tienes algo con lo que crees que algunos ingenieros realmente rad deberían ayudarte.

Savage Rose

Determinar exactamente si/cuando/donde una línea en movimiento interseca un punto en movimiento | Blog de Twisted Oak Studios