Определить, когда 2 движущихся объекта в 2-й плоскости находятся близко

Question

Представьте, что у нас есть 2D небо (10000x10000 координаты). В любом месте на этом небе у нас может быть самолет, идентифицированный по его положению (x, y). Любой самолет может начать движение по другим координатам (по прямой линии).

Существует один компонент, который управляет всем этим позиционированием и перемещением. Когда самолет хочет двигаться, он отправляет ему сообщение в виде (start_pos, speed, end_pos). Как я могу сказать в компоненте, когда одно воздушное судно будет двигаться в зоне прямой видимости другого (каждое воздушное судно имеет это как свойство в качестве радиуса обзора), чтобы уведомить об этом. Обратите внимание, что много самолетов могут двигаться одновременно. Кроме того, этот алгоритм хорош, чтобы быть эффективным, если он может обрабатывать ~ 1000 самолетов.

---

Если есть какое-то ограничение, которое ограничивает ваше решение - его, вероятно, можно удалить. Проблема не устранена.

Answer 1

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

Затем проблема становится вопросом нахождения точки, где линия пересекает (наклоненный) цилиндр.Нахождение всех возможных пересечений было бы тогда n ^ 2;не слишком уверен, что это достаточно эффективно.

Answer 2

• Используйте линию для обозначения траектории полета.
• Преобразуйте каждую строку в охватывающий ее прямоугольник. Ширина прямоугольника определяется вашим определением «близко» (чем больше безопасное расстояние, тем шире должен быть прямоугольник).
• Для каждого нового плана полета:
  • Проверьте, пересекается ли новый прямоугольник с другим прямоугольником.
    • Если это так, рассчитайте, когда каждая плоскость достигнет точки столкновения. Если разница во времени слишком мала (и вы должны определить слишком мало в соответствии со сценарием), откажитесь от нового плана полета.

Answer 3

См. Wikipedia: Quadtree для структуры данных, которая позволит легко определить, какие самолеты находятся близко к данному самолету.Это избавит вас от выполнения O (N ^ 2) тестов на близость.

Answer 4

У вас есть хорошие ответы, я буду комментировать только один аспект и, вероятно, не правильно

• вы говорите, что ваши самолеты движутся в форме (start_pos, speed, end_pos)
• если у всех самолетов есть такие, назовем их самолетами полета, тогда вы сможете рассчитывать непосредственно, когда и где они будут находиться на определенном расстоянии друг от друга, или когда они будут находиться ближе всего друг от друга, или если столкнуться / подойти слишком близко

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

Если вам нужно решить эти уравнения быстрее, вы можете использовать методы, описанные в других ответах

• с использованием эффективных структур, которые могут ускорить расчет расстояний (квадри, октре, kd-деревья),
• разбиение задачи для решения уравнений только для некоторого соответствующего будущего временного интервала
• установить приоритетность решения уравнений для пар, для которых расстояние изменяется наиболее быстро

Конечно, преобразование времени в третье измерение превращает самолеты из точек в линии, и вы в конечном итоге ищете самые близкие точки между двумя 3d линиями (вот некоторые математика )

Answer 5

Я действительно нашел ответ на этот вопрос.

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