¿Cuál es la mejor manera de implementar la detección de colisiones unidimensionales?

Question

Estoy escribiendo una pieza de software de simulación, y necesito una manera eficiente de probar las colisiones a lo largo de una línea.

La simulación es de un tren que cruza varios interruptores en una pista. Cuando una rueda entra a N pulgadas del interruptor, el interruptor se enciende, luego se apaga cuando la rueda se va. Como todas las ruedas son del mismo tamaño y todos los interruptores tienen el mismo tamaño, puedo representarlos como una sola coordenada X a lo largo de la pista. Las distancias de conmutación y las distancias de las ruedas no cambian una con relación a la otra, una vez establecidas.

Este es un problema bastante trivial cuando se hace a través de la fuerza bruta al colocar las coordenadas X en listas y atravesarlas, pero necesito una forma de hacerlo de manera eficiente, porque tiene que ser extremadamente precisa, incluso cuando el tren está moviéndose a altas velocidades. Hay un montón de tutoriales sobre detección de colisiones en 2D, pero no estoy seguro de cuál es la mejor manera de abordar este escenario 1D único.

---

Aparentemente hay cierta confusión sobre cómo se ven mis datos.

Estoy simulando un solo sitio, no una región completa. Los trenes pueden ser de cualquier longitud, con diferentes tipos de automóviles, pero solo hay un tren. Los datos de mi tren tienen el formato {48,96,508,556,626,674,...}, que indican las distancias desde la parte delantera del tren (0) al centro del eje.

(Los datos del tren es más probable que venir a mí en forma de una lista ordenada deCarobjetos, cada uno de los cuales tiene una longitud y una lista de números enteros que representan las distancias del eje de la parte delantera de ese coche, pero todo se agrega en una sola lista, ya que todos los ejes son iguales para mí.)

Mis interruptores están todos dentro de varios cientos de pies, y con frecuencia estarán completamente cubiertos por el tren. Los interruptores pueden estar en cualquier intervalo desde cientos de pies a varias pulgadas de distancia, y está en la misma forma que el tren: {0,8,512,520,...}, que indica las distancias desde el comienzo del sitio hasta el centro de la conmutación h.

Finalmente, sé la distancia a la que la rueda activa el interruptor, en pulgadas.

Por ejemplo, utilizando los datos de muestra anteriores, y una distancia de activación de 8 pulgadas, el primer interruptor en X = 0 se activaría cuando el tren golpee X = 40, lo que significa que el tren está 40 pulgadas en el sitio. Cuando el tren golpea X = 48, el interruptor en X = 8 también se activa. En X = 56, el primer interruptor se apaga, y en X = 64, el segundo interruptor también se apaga. Diferentes ejes encienden y apagan diferentes interruptores a medida que cruzan el sitio.

El tren suele circular a velocidades inferiores a 10 mph, pero puede llegar mucho más lejos. (En este momento nuestra simulación tiene un tope de 30 mph, pero mayor sería grande.)

Answer 1

Preprocesa las ubicaciones de los interruptores y el rango de sensibilidad en una lista de segmentos de pistas. Cada segmento tiene una longitud, y entre cada segmento un conjunto de eventos 'encender' o 'apagar'.

switch_on (0), (length: 8), switch_on (1), // x = zero here 
segment (length: 8), switch_off (0), 
segment (length: 8), switch_off (1), 
segment (length: 488), switch_on (2), 
segment (length: 8), switch_on (3), 
segment (length: 8), switch_off (2), 
segment (length: 8), switch_off (3), 
... 

Para cada eje, tenga su ubicación actual también representada junto con el segmento de la pista en la que se encuentra.

Si está realizando una simulación basada en eventos, el próximo evento debe programarse para el valor mínimo de la distancia desde un eje hasta el final de su segmento de pista actual. Esto es independiente de la velocidad del tren, y precisa (no te perderás interruptores si el tren va más rápido). Almacene los eventos en un montón si es necesario (a menudo no vale la pena por menos de 30 o más, el perfil de la programación del evento si es necesario).

El procesamiento de un evento será O (no-de-ejes). La mayoría de los pasos implicarán uno o dos cambios en el estado del interruptor y una actualización de posición. En cada evento, un eje hará que un interruptor se encienda o apague (los interruptores que serían simultáneos de acuerdo con los datos causan dos eventos, con cero tiempo de separación), y todos los tiempos de los ejes hasta el final de sus segmentos necesitan ser comparados. También puede suponer que todos los ejes viajan a la misma velocidad o no; no importa en cuanto al procesamiento de los eventos, solo hace el cálculo del tiempo para alcanzar el siguiente interruptor específico para el eje en cuestión.

Si está en una simulación de paso en tiempo fijo, entonces procese todos los eventos que habrían ocurrido hasta el momento al final del paso, luego un evento para mover los ejes al punto que alcanzan al final de el paso.

Answer 2

tener una lista ordenada de las coordenadas de todos los interruptores y utilizando búsqueda binaria en la lista para encontrar el interruptor más cercano. Luego verifica qué tan lejos está y si es o no una colisión.

O (log n)

Otra opción es explotar el hecho de que el tren se mueve a lo largo de la pista y tan sólo puede venir cerca de dos interruptores, uno detrás y otro delante.

Construya lista doblemente vinculada de todos los conmutadores y coloque un nodo adicional para representar el tren en la ubicación correcta en la lista vinculada. Luego, solo controle la proximidad del interruptor al que se dirige el tren.

O memoria (1)

Para guardar, almacenar las coordenadas ordenados en una matriz y simplemente hacer un seguimiento de los índices que el tren es el medio.

Answer 3

Almacene la lista de cambios como una lista doblemente enlazada como lo indica Ben.

Mantenga un puntero en el objeto de la rueda (o estructura, suponiendo que haya uno) para el siguiente interruptor y el interruptor anterior en relación con su posición actual. Inicializar estos como la rueda se coloca en la pista.

Mientras se mueve sobre cada interruptor, cambie los interruptores "siguiente" y "anterior" en su objeto de rueda por el nuevo "siguiente" y "anterior" que pueden obtenerse rápidamente examinando la lista de doble enlace.

Esto evita todas las búsquedas, excepto posiblemente la colocación inicial de la rueda.

Además, la estructura del "interruptor" podría utilizarse para mantener un puntero de proximidad de nuevo a todas las ruedas que lo enumeran como "anterior" o "siguiente". (Aquí hay un mutex, así que tenga cuidado de quién actualiza esto.) Esto puede proporcionar una actualización rápida de quién se acerca a un interruptor determinado y su distancia de él.

Answer 4

Suponiendo que las distancias de eje a eje sean siempre mayores que la distancia de activación, y que las rutas no cambien frecuentemente después de que entre el tren, usted debería poder acelerar las cosas con el cálculo previo. Básicamente, para cada interruptor, calcule una lista de las distancias de recorrido del tren en el que se alternará, luego recorra las listas a medida que avanza el tren.

Pseudocódigo:

axles = {48,96,508,556,626,674,...} 
switches ={0,8,512,520,...} 
activate = 8 
float toggledist[num_switches] 
boolean switchState[num_switches]={false,false,false,...} 
int idx[num_switches] 

for (i in switches) 
    n = 0 
    for (a in axles) 
    toggledist[n++] = switches[i]+axles[a]-activate 
    toggledist[n++] = switches[i]+axles[a]+activate 

travel= 0.0f; 

each (cycle) 
    travel += TrainVelocity*time; 
    for (i in switches) 
    while (trigger>=toggledist[idx[i]]) 
     switchState[i]=!switchState[i]; 
     //additional processing for switch change here, if needed 
     idx[i]++;