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

Question

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

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

Это довольно тривиальная проблема, если выполнить грубую силу, разместив координаты X в списках и пройдя их, но мне нужен способ сделать это эффективно, потому что он должен быть предельно точным, даже если поезд движущихся с высокой скоростью. Существует тонна учебников по обнаружению двумерных столкновений, но я не уверен, что лучший способ сделать этот уникальный 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 миль в час, но выше, было бы здорово.)

Answer 1

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

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 или около того, при необходимости профилируйте планирование событий).

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

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

Answer 2

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

O (журнал N)

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

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

O (1)

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

Answer 3

Храните список коммутаторов в виде списка с двойной связью, как указано Беном.

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

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

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

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

Answer 4

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

псевдокод:

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