Каков наилучший способ реализации одномерного обнаружения столкновений?

Question

Я пишу часть программного обеспечения для моделирования, и мне нужен эффективный способ проверки на столкновения вдоль линии.

Имитация поезда, пересекающего несколько стрелок на пути. Когда колесо находится в пределах N дюймов от переключателя, переключатель включается, а затем выключается, когда колесо отключается. Поскольку все колеса имеют одинаковый размер, а все переключатели одинакового размера, я могу представить их как одну координату X вдоль пути. Расстояния переключения и расстояния между колесами не изменяются относительно друг друга, после установки.

Это довольно тривиальная проблема, когда она выполняется грубой силой, помещая координаты X в списки и обходя их, но мне нужен способ сделать это эффективно, потому что он должен быть чрезвычайно точным, даже когда поезд движется на высоких скоростях. Существует множество обучающих программ по обнаружению столкновений в 2D, но я не уверен, что это лучший способ реализовать этот уникальный 1D сценарий.

---

Видимо, есть некоторая путаница в том, как выглядят мои данные.

Я моделирую один сайт, а не целый регион. Поезда могут быть любой длины, с разными типами вагонов, но есть только один поезд. Мои данные о поездах имеют вид {48,96,508,556,626,674,...}, указывающий расстояния от передней части поезда (0) до центра оси.

(Данные поезда, скорее всего, придут ко мне в виде упорядоченного списка Car объектов, каждый из которых имеет длину и список целых чисел, представляющих расстояния от оси до передняя часть этой машины, но все это объединено в один список, поскольку все оси для меня одинаковы.)

Все мои переключатели находятся в пределах нескольких сотен футов, и часто будут полностью покрыты поездом. Переключатели могут находиться на любом интервале от сотен футов до нескольких дюймов друг от друга и находятся в той же форме, что и поезд: * с указанием расстояния от начала площадки до центра коммутатора.

Наконец, я знаю расстояние, на котором колесо активирует переключатель, в дюймах.

Например, используя приведенные выше примеры данных и расстояние активации 8 дюймов, первый переключатель при X = 0 активируется, когда поезд достигает X = 40, что означает, что поезд находится на площадке в 40 дюймов. Когда поезд достигает X = 48, переключатель при X = 8 также активируется. При X = 56 первый выключатель отключается, а при X = 64 второй выключатель также выключается. Различные оси включают и выключают разные переключатели, когда они пересекают площадку.

Поезд обычно движется со скоростью менее 10 миль в час, но может идти намного выше. (Прямо сейчас наша симуляция ограничена 30 милями в час, но выше было бы здорово.)

Answer 1

Иметь отсортированный список всех координат коммутаторов и использовать двоичный поиск в списке, чтобы найти ближайший коммутатор.Затем проверьте, насколько это далеко и является ли это столкновением.

O (log n)

Другой вариант - использовать тот факт, что поезд движется по путии может когда-либо приближаться только к двум переключателям, один сзади и один впереди.

Составьте двусвязный список всех переключателей и расположите дополнительный узел, чтобы представить поезд в правильномрасположение в связанном списке.Затем проверяйте только близость к тому переключателю, к которому направляется поезд.

O (1)

Чтобы сохранить память, сохраните отсортированные координаты в массиве и просто следитеиз которых индексы поезд между.

Answer 2

Предварительно обработайте ваши местоположения переключателей и диапазон чувствительности в список сегментов дорожки. Каждый сегмент имеет длину, а между каждым сегментом - набор событий включения или выключения.

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 ),
...

Для каждой оси также указывается ее текущее местоположение вместе с сегментом пути, на котором она находится.

Если вы выполняете симуляцию на основе событий, следующее событие должно быть запланировано на минимальное значение расстояния от оси до конца текущего сегмента дорожки. Это не зависит от скорости поезда и точно (вы не пропустите переключатели, если поезд едет быстрее). При необходимости сохраняйте события в куче (часто это не стоит того, чтобы меньше 30 или около того, при необходимости профилируйте планирование событий).

Обработка события будет O (без осей). Большинство шагов будет включать одно или два изменения состояния переключателя и обновление положения. В каждом событии одна ось заставит один переключатель включиться или выключиться (переключатели, которые будут одновременными в соответствии с данными, вызывают два события, с нулевым интервалом времени), и все времена оси до конца их сегментов необходимо сравнить. Вы можете предположить, что все оси движутся с одинаковой скоростью или нет; это не имеет значения, поскольку обработка событий, это только вычисление времени, чтобы достигнуть следующего выключателя, определенного для рассматриваемой оси.

Если вы выполняете симуляцию с фиксированным временным шагом, то обрабатываете все события, которые произошли бы до времени в конце шага, затем одно событие, чтобы переместить оси в точку, которой они достигают в конце шаг.

Answer 3

Предполагая, что расстояния от оси до оси всегда больше расстояния активации, и что маршруты не часто меняются после того, как поезд входит, вы должны быть в состоянии ускорить процесс с предварительным расчетом.По сути, для каждого переключателя рассчитайте список расстояний движения поезда, на которых он будет переключаться, а затем просмотрите списки по мере продвижения поезда.

Псевдокод:

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]++;

Answer 4

Сохраните список переключателей в виде двусвязного списка, как указано Беном.

Держите указатель в объекте колеса (или структуре, если он есть) к следующему переключателю и предыдущему переключателю относительно вашей текущей позиции. Внедрите их, когда колесо находится на дорожке.

Перемещаясь по каждому переключателю, поменяйте местами переключатели «следующий» и «предыдущий» в объекте колеса на новые «следующий» и «предыдущий», которые можно быстро получить, просмотрев двусвязный список.

Это позволяет избежать всех поисков, кроме, возможно, первоначального размещения колеса.

Кроме того, структура «switch» может использоваться для удержания указателя приближения обратно ко всем колесам, которые перечисляют его как «предыдущий» или «следующий». (Здесь есть мьютекс, поэтому будьте осторожны с тем, кто его обновляет.) Это может обеспечить быстрое обновление информации о том, кто приближается к тому или иному коммутатору, и их расстоянии от него.