Как эффективно определить сближения траекторий с учетом времени?

Question

[Александр Кунин]

Всем привет,

возникла достаточно интересная задача, но затрудняюсь с тем с какой стороны к ней подступиться.
Задача звучит следующим образом - дано 20-50 траекторий (~5 мин с частотой 5 Гц, длина до 10 км), необходимо найти фрагменты траектории, где было сближение ближе чем на 250 метров. Сближение необходимо учитывать с учетом времени, то есть, не просто фрагменты, которые находятся близко.
Ограничение - сервер 1 ядро, 1Гб RAM

Картинка:


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

Comments

[xmoonlight]

Это вообще для каких целей нужно?

[Александр Кунин]

Приложение используется для проведения соревнований по пилотированию в вингсьюте, новые правила FAI включают пункт:
At no time from exit to opening shall competitor(s) come within 250m of any other competitor(s). Violation of this rule, as determined by the panel of judges, will result in a score of zero for that jump. This decision is not grounds for protest.

Правила полностью: www.fai.org/downloads/ipc/wf_rule_changes

[xmoonlight]

Александр Кунин: понял.
Кратко: находим расстояние в 3D-пространстве между всеми точками в один момент времени. При нахождении сближения - фиксируем "перелом" (триггер) и указываем в доп. массиве временную засечку и связки объектов (по-парно), находящихся рядом на расстоянии меньшем, чем 250м.

Answer 1

[Сергей Соколов]

Двигаться по оси времени, считать взаимные расстояния во всех комбинациях. Для пар, где расстояние оказалось меньше 250 м записать пару и timestamp

{
    timestamp1: [ [id1, id2], [id35,id42], ... ],
    timestamp2: [ [id1, id2], [id23,id24], ... ],
}

Потом по этим данным можно снова вытащить нужные координаты и отобразить участки сближений.

Оптимизировать можно с учётом доп. условий – напр. известно, что это воздушные шары и их скорость не может превышать некое значение. И тогда если какой-то шар удалён на значительное расстояние, его можно не проверять следующие X секунд, например.

Comments

[Александр Кунин]

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

Answer 2

[Константин Степанов]

Нужны текстовые "сырые" данные в виде: "точка" = "пользователь, время, координаты" (означает что в этот момент такой-то пользователь был по таким координатам)

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

Далее - выводим результаты как удобно.

Comments

[Александр Кунин]

В таком случае на 20 траекторий содержащих в сумме 40000 точек получится 160_000_000 итераций, что будет непозволительно долго не зависимо от выбранного языка программирования

[Константин Степанов]

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

[Александр Кунин]

Спасибо огромное за отличную идею! Так можно с учетом известных пределов скорости выполнять поиск сначала на большее расстояние, например на 500 метров с интервалом в 200 точек и далее выполнить более детальный поиск при необходимости

[Константин Степанов]

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

Answer 3

[x67]

Ничего сложного для вашего сервера тут нет. Все считается очень быстро. Формализуете условия(сближение на 250 метров к примеру в течении минимум секунды и 4 тактов из 5, ибо шум, ошибки и тп), а потом прогоняете все данные. Уж как расстояние найти между двумя точками, вы наверное знаете. Еще важным фактором в решении задачи будет то, в каком виде представлены данные. Это координаты? Если так, то в какой системе координат? Может это скорости? Тогда нужно будет их еще и проинтегрировать и определиться с возможными ошибками и способами их нейтрализации.
На каком языке будете реализовывать?

Comments

[Александр Кунин]

Спасибо большое. Координаты берутся с gps трекера, то есть широта, долгота, высота. Расстояние между точками планировал вычислять как great circle distance, далее корень из квадрата расстояния и разницы высот.
Язык в порядке убывания предпочтительности:
- Ruby (приложение на нем)
- Crystal (схож с Ruby)
- Rust (интересен)

[x67]

Александр Кунин: язык я для интереса спросил. Если координаты GPS, то нужна фильтрация от случайных артефактов, в остальном все как есть.

[x67]

Александр Кунин: хотя наверное в первую очередь надо будет перевести градусы в метры, это и будет самой большой проблемой. Тут я вам не помощник, ибо после институтского курса про навигационные системы, все уже выветрилось)
Ну и естественно нужно будет оценить точность приемника и в зависимости от задачи поставить условия. Если точность 10-30метров, то это критично

Answer 4

[xmoonlight]

Кратко: находим расстояние в 3D-пространстве между всеми точками в один момент времени. При нахождении сближения - фиксируем "перелом" (триггер) и указываем в доп. массиве временную засечку и связки объектов (по-парно), находящихся рядом на расстоянии меньшем, чем 250м.
Бонус (формула расстояния для lat/lon): Calculate distance, bearing and more between Latit...