Что лучший способ состоит в том, чтобы реализовать одномерное обнаружение коллизий?
Я пишу часть программного обеспечения моделирования и нуждаюсь в эффективном способе протестировать на коллизии вдоль строки.
Моделирование имеет поезд, пересекающий несколько переключателей на дорожке. Когда колесо прибывает в дюймах N переключателя, переключатель включает, затем выключает, когда колесо уезжает. Так как все колеса являются тем же размером, и все переключатели являются тем же размером, я могу представить их как единственную координату X вдоль дорожки. Расстояния переключателя и расстояния колеса не изменяются друг относительно друга, когда-то устанавливают.
Это - довольно тривиальная проблема при выполнении через грубую силу путем размещения X координат в списках и пересечения их, но мне нужен способ сделать так эффективно, потому что это должно быть чрезвычайно точно, даже когда поезд перемещается в высокие скорости. Существует тонна учебных руководств на 2D обнаружении коллизий, но я не уверен лучший способ пойти об этом уникальном 1D сценарий.
По-видимому, существует некоторый беспорядок о том, на что похожи мои данные.
Я моделирую единственный сайт, не весь регион. Поезда могут иметь любую длину с различными типами автомобилей, но существует только когда-либо один поезд. Мои данные поезда находятся в форме {48,96,508,556,626,674,...}, указание на расстояния от передней стороны поезда (0) к центру оси.
(Данные поезда более вероятно прибудут ко мне в форме заказанного списка Car объекты, каждый из которых имеет длину и список целых чисел, представляющих расстояния оси от передней стороны того автомобиля, но все это агрегировано в единственный список, начиная со всех осей, являются тем же мне.)
Мои переключатели - все в нескольких сотнях футов и будут часто полностью покрываться поездом, переключатели могут быть в любом интервале от сотен ног до на расстоянии в несколько дюймов, и находятся в той же форме как поезд: {0,8,512,520,...}, указание на расстояния с начала сайта к центру переключателя.
Наконец, я знаю расстояние, на котором колесо активирует переключатель в дюймах.
Например, с помощью вышеупомянутых демонстрационных данных, и расстояние активации 8 дюймов, первый переключатель в X=0 активировался бы, когда поезд врезается в X=40, означая, что поезд составляет 40 дюймов в сайт. Когда поезд врезается в X=48, переключатель в X=8 также активируется. В X=56 первый переключатель уходит, и в X=64, второй переключатель также уходит. Различные оси включают и выключают различные переключатели, поскольку это пересекает сайт.
Поезд обычно выполняет на скоростях менее чем 10 миль в час, но может стать намного выше. (Прямо сейчас наше моделирование ограничивается на уровне 30 миль в час, но выше было бы большим.)
4 ответа
Предварительно обработайте местоположение переключателей и диапазон чувствительности в список отрезков пути. Каждый сегмент имеет длину, а между каждым сегментом - набор событий "включения" или "выключения" переключателей.
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(no-of-axles). Большинство шагов будет включать одно или два изменения состояния переключателя и обновление позиции. При каждом событии одна ось вызывает включение или выключение одного переключателя (переключатели, которые по данным были бы одновременными, вызывают два события с нулевым временным интервалом), и необходимо сравнить время всех осей до конца их сегментов. Вы можете предположить, что все оси движутся с одинаковой скоростью, или нет; это не имеет значения для обработки событий, это только делает расчет времени до следующего выключателя специфичным для данной оси.
Если вы моделируете с фиксированным временным шагом, то обрабатывайте все события, которые произошли бы до времени в конце шага, затем одно событие для перемещения осей в точку, которую они достигнут в конце шага.
Сохраните список переключателей как двусвязный список, как указано Беном.
Удерживайте указатель в объекте колеса (или структуре, если он есть) на следующий переключатель и предыдущий переключатель относительно вашего текущего положения. Начните их инициализировать, когда колесо будет размещено на рельсе.
При перемещении по каждому переключателю меняйте местами переключатели «следующий» и «предыдущий» в объекте колеса на новые «следующий» и «предыдущий», которые можно быстро получить, изучив двусвязный список.
Это позволяет избежать всех поисков, кроме, возможно, первоначального размещения колеса.
Кроме того, структура «переключатель» может использоваться для удержания указателя приближения обратно ко всем колесам, которые перечисляют его как «предыдущее» или «следующее». (Здесь есть мьютекс, поэтому будьте осторожны с тем, кто его обновляет.) Это может обеспечить быстрое обновление информации о том, кто приближается к любому данному коммутатору, и их расстоянии от него.
Создайте отсортированный список координат всех переключателей и используйте двоичный поиск в списке, чтобы найти ближайший переключатель. Затем проверьте, насколько далеко он находится и не является ли это столкновением.
O (log n)
Другой вариант - использовать тот факт, что поезд движется по рельсам и может подойти только к двум стрелкам, одному сзади и одному впереди.
Создайте двусвязный список всех переключателей и разместите дополнительный узел, чтобы представить поезд в правильном месте связанного списка. Тогда только проверяйте близость к стрелке, к которой едет поезд.
O (1)
Для экономии памяти сохраните отсортированные координаты в массиве и просто отслеживайте, между какими индексами находится поезд.
Предполагая, что расстояние от оси до оси всегда больше расстояния активации, и что маршруты не часто меняются после входа в поезд, вы сможете ускорить процесс с помощью предварительного расчета. По сути, для каждого переключателя рассчитайте список расстояний движения поезда, на котором он будет переключаться, а затем просматривайте списки по мере продвижения поезда.
Псевдокод:
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]++;