Strava - Групповой маршрут Близость с широтой, долготой и временем

Question

Вопрос: Что представляет собой наиболее эффективный с точки зрения вычислительной мощности способ определения того, ездили ли два велосипедиста вместе с потоком данных со временем, широтой и долготой?

Справочная информация: Я являюсь активным велосипедистом и хочу обратить внимание на то, как Strava объединяет велосипедистов. Вот их метод, чтобы определить, ездят ли велосипедисты (они используют время и лат/lon езды): https://support.strava.com/hc/en-us/articles/216919497-Why-don-t-I-get-grouped-in-Activities-when-I-rode-ran-with-others-

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

Rider 1 Маршрут:

Rider 2 Маршрут:

Вы можете увидеть Rider 1 и 2 ехали вместе, но Rider 2 начался с другим места и присоединился к Rider 1 позже.

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

Я думаю, что подход Стравы хорош - в основном устанавливают зону близости (150 метров) вокруг каждой точки маршрута и сравнивают маршруты гонщика, чтобы увидеть, провели ли всадники 70% своего времени в 150 метрах друг от друга.

Rider 1 - Расположение:
2016-03-27T11: 47: 45Z 42,113059 -87,736485
2016-03-27T11: 47: 46Z 42,113081 -87,736511
2016-03-27T11: 47: 47Z 42.113105 -87,736538
2016-03-27T11: 47: 48Z 42,113142 -87,736564
2016-03-27T11: 47: 49Z 42,113175 -87,736587

Rider 2 - Расположение:
- 2016-03-27T11 : 47: 45Z 42.113049 -87.736394 < = Найти время всадника 1 и определить, находится ли он в пределах 150 метров. Если < 150 метров назначить 1, если> 150 назначить 0.

Я бы перебирал каждую точку Райдера 2 против каждой точки Райдера 1. Затем подведите итоги 1 и 0. Если (сумма 1s и 0s)/(общая сумма) больше 70%, то гонщики группируются вместе.

Я думаю, что этот метод, как правило, работает, но, кажется, очень интенсивно вычисляется, особенно если есть тысячи гонщиков для оценки. Кроме того, данные не всегда имеют широту и долготу каждую секунду. Одним из способов было бы усреднить местоположение каждую минуту и ​​сравнить среднее местоположение по минуте. По крайней мере, это уменьшило бы итерации в 60 раз.

Я надеялся, что существует некоторый статистический или ГИС-метод, чтобы установить «подпись» маршрута и сравнить сигнатуры, а не сравнение по точкам.

Любые мысли о том, как правильно вычислить сравнение маршрутов?

Примечание: Я опубликовал аналогичный вопрос на форуме ГИС, но никто еще не ответил. Хотя, я думаю, вопрос, написанный здесь, более ясен.
https://gis.stackexchange.com/questions/187019/strava-activity-route-grouping

Answer 1

Я собираюсь предположить, что верно следующее:

• для каждого велосипедиста C, существует поток данных времени Т, долготы и широты X Y (мы используем проецируемого X и Y для упрощения, не заботясь о проецировании, однако мы должны)
• поток данных может быть записан в базу данных или другой вид постоянного хранилища данных
• поток данных для C отбирается со скоростью 1 с, не гарантирует, что каждый образец взят; мы должны предположить, что образец взят более чем в 50% случаев (предпочтительно> 95%, 99,7% будет идеальным)

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

╔════╦════╦════╦════╦════╦═══════╗ 
║ T ║ X1 ║ Y1 ║ X2 ║ Y2 ║ D ║ 
╠════╬════╬════╬════╬════╬═══════╣ 
║ 1 ║ 10 ║ 15 ║ - ║ - ║  - ║ 
║ 2 ║ 11 ║ 16 ║ - ║ - ║  - ║ 
║ 3 ║ 11 ║ 17 ║ 19 ║ 11 ║ 10,00 ║ 
║ 4 ║ 12 ║ 18 ║ 18 ║ 11 ║ 9,22 ║ 
║ 5 ║ 12 ║ 17 ║ 17 ║ 12 ║ 7,07 ║ 
║ 6 ║ - ║ - ║ 15 ║ 12 ║  - ║ 
║ 7 ║ 13 ║ 16 ║ 14 ║ 13 ║ 3,16 ║ 
║ 8 ║ 13 ║ 15 ║ 13 ║ 14 ║ 1,00 ║ 
║ 9 ║ 14 ║ 14 ║ 13 ║ 14 ║ 1,00 ║ 
║ 10 ║ 14 ║ 13 ║ 14 ║ 13 ║ 0,00 ║ 
║ 11 ║ 14 ║ 14 ║ 14 ║ 14 ║ 0,00 ║ 
║ 12 ║ 14 ║ 15 ║ 14 ║ 14 ║ 1,00 ║ 
║ 13 ║ 15 ║ 15 ║ 15 ║ 15 ║ 0,00 ║ 
║ 14 ║ 15 ║ 16 ║ 15 ║ 16 ║ 0,00 ║ 
║ 15 ║ 16 ║ 16 ║ 16 ║ 17 ║ 1,00 ║ 
║ 16 ║ 17 ║ 18 ║ 16 ║ 16 ║ 2,24 ║ 
╚════╩════╩════╩════╩════╩═══════╝ 

Это сравнение может быть легко осуществлено с использованием, например, SELECT в базе данных, присоединяется к таблице для двух велосипедистов. Для разумного количества строк (например, < 10E5, < 10E6) и правильно настроенных индексов это вычисление вообще не является ресурсоемким. Особенно, если принять во внимание, что запрос базы данных может быть записан таким образом, что значение D не выводится для каждой позиции, а вычисляемое значение, чтобы агрегировать (подсчитать) значение. В этом случае все, что вам нужно, это отношение количества строк, где D меньше, чем ваше предпочтительное значение D0 против общего количества строк. Если это соотношение равно или превышает ваш лимит (скажем, 70%), велосипедисты ездили вместе.

Давайте посмотрим пример. Если есть такая таблица в базе данных, названный CyclistPosition:

• CyclistId - идентификатор велосипедиста
• SamplingTime - время UTC образца (положение), принятое
• Long - долгота
• Lat - широта

... со следующими данными:

╔═══════════╦═══════════════════════╦═══════════╦════════════╗ 
║ CyclistId ║  SamplingTime  ║ Long ║ Lat  ║ 
╠═══════════╬═══════════════════════╬═══════════╬════════════╣ 
║   1 ║ 2016-03-27T11:47:45Z ║ 42,113059 ║ -87,736485 ║ 
║   1 ║ 2016-03-27T11:47:46Z ║ 42,113081 ║ -87,736511 ║ 
║   1 ║ 2016-03-27T11:47:47Z ║ 42,113105 ║ -87,736538 ║ 
║   1 ║ 2016-03-27T11:47:48Z ║ 42,113142 ║ -87,736564 ║ 
║   1 ║ 2016-03-27T11:47:49Z ║ 42,113175 ║ -87,736587 ║ 
║   2 ║ 2016-03-27T11:47:45Z ║ 42,113059 ║ -87,736394 ║ 
║   2 ║ 2016-03-27T11:47:46Z ║ 42,113085 ║ -87,736481 ║ 
║   2 ║ 2016-03-27T11:47:47Z ║ 42,113103 ║ -87,736531 ║ 
║   2 ║ 2016-03-27T11:47:48Z ║ 42,113139 ║ -87,736572 ║ 
║   2 ║ 2016-03-27T11:47:49Z ║ 42,113147 ║ -87,736595 ║ 
╚═══════════╩═══════════════════════╩═══════════╩════════════╝ 

... тогда мы можем извлечь данные для велосипедистов 1 и 2 с помощью:

SELECT SamplingTime, Long, Lat FROM CyclistPosition WHERE CyclistId = 1 
SELECT SamplingTime, Long, Lat FROM CyclistPosition WHERE CyclistId = 2 

... и перекрестные ссылки, что данные, используя этот запрос ...

SELECT 
    cp1.SamplingTime, 
    Long1 = cp1.Long, 
    Lat1 = cp1.Lat, 
    Long2 = cp2.Long, 
    Lat2 = cp2.Lat 
FROM 
    CyclistPosition cp1 
    JOIN CyclistPosition cp2 
    ON cp2.SamplingTime = cp1.SamplingTime 
WHERE 
    cp1.CyclistId = 1 
    AND cp2.CyclistId = 2 

Теперь у нас есть этот вид продукции, и если мы включаем rougly вычисленный X и Y (с помощью проекции Меркатора), получим:

╔═══════════════════════╦═══════════╦════════════╦═══════════╦════════════╦══════════════╗ 
║  SamplingTime  ║ Long1 ║ Lat1 ║ Long2 ║ Lat2 ║  Dm  ║ 
╠═══════════════════════╬═══════════╬════════════╬═══════════╬════════════╬══════════════╣ 
║ 2016-03-27T11:47:45Z ║ 42,113059 ║ -87,736485 ║ 42,113059 ║ -87,736394 ║ 10,118517 ║ 
║ 2016-03-27T11:47:46Z ║ 42,113081 ║ -87,736511 ║ 42,113085 ║ -87,736481 ║ 3,334919  ║ 
║ 2016-03-27T11:47:47Z ║ 42,113105 ║ -87,736538 ║ 42,113103 ║ -87,736531 ║ 0,777079  ║ 
║ 2016-03-27T11:47:48Z ║ 42,113142 ║ -87,736564 ║ 42,113139 ║ -87,736572 ║ 0,890572  ║ 
║ 2016-03-27T11:47:49Z ║ 42,113175 ║ -87,736587 ║ 42,113147 ║ -87,736595 ║ 0,900635  ║ 
╚═══════════════════════╩═══════════╩════════════╩═══════════╩════════════╩══════════════╝ 

Обратите внимание, что для грубого расчета расстояния в метрах вы должны найти формулу; Я использовал один здесь:

http://bluemm.blogspot.hr/2007/01/excel-formula-to-calculate-distance.html

Теперь мы должны объединить данные и считать.Мы должны ограничить данные временем начала и окончания (T1 и T2) и установить максимальное расстояние (D0), чтобы сказать, что велосипедисты едут вместе. Простой способ сделать это в SQL будет:

DECLARE @togetherPositions int 
DECLARE @allPositions int 
DECLARE @ratio decimal(18,2) 

SELECT @togetherPositions = count(*) 
FROM 
    CyclistPosition cp1 
    JOIN CyclistPosition cp2 
    ON cp2.SamplingTime = cp1.SamplingTime 
WHERE 
    cp1.SamplingTime BETWEEN @T1 AND @T2 
    AND {formula to get distance in meters} <= @D0 

SELECT @allPositions = count(*) 
FROM 
    CyclistPosition cp1 
    JOIN CyclistPosition cp2 
    ON cp2.SamplingTime = cp1.SamplingTime 
WHERE 
    cp1.SamplingTime BETWEEN @T1 AND @T2 

SET @ratio = @togetherPositions/@allPositions * 1.0 

Теперь вы просто должны решить, если соотношение составляет 0,7, 0,8, 0,85 ...

HTH