Strava - 带纬度、经度和时间的团体路线接近度

Question

问题：给定包含时间、纬度和经度的数据流，确定两个骑自行车的人是否一起骑行的计算效率最高的方法是什么？

背景： 我是一名狂热的自行车手，想对 Strava 如何将骑自行车的人分组在一起进行逆向工程。这是他们确定骑车人是否一起骑行的方法（他们使用时间和 lat/lon 骑行）：https://support.strava.com/hc/en-us/articles/216919497-Why-don-t-I-get-grouped-in-Activities-when-I-rode-ran-with-others-

骑完自行车后，我每秒都有一个经纬度文件。

骑手 1 路线：

骑士2路线：

可以看到骑手1和骑手2一起骑，但是骑手2从不同的地方出发，后来加入了骑手1。

尽管从不同的位置出发，但我想提出计算强度最低的方法来确定这两个骑手一起骑行。

我觉得Strava的做法很好——基本上在路线上的每个点周围建立一个邻近区域（150米），比较骑手的路线，看看骑手是否有70%的时间都在彼此150米的范围内度过.

骑手 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

骑手 2 - 地点：
-2016-03-27T11:47:45Z 42.113049 -87.736394 <= 查找Rider 1 的相同时间并确定是否在150 米内。如果 < 150 米分配 1，如果 > 150 分配 0。

我会针对 Rider 1 的每个点迭代 Rider 2 的每个点。然后将 1 和 0 相加。如果（1 和 0 的总和）/（总分）大于 70%，车手将被分组。

我认为这种方法通常可行，但计算量似乎很大，尤其是当有成千上万的车手要评估时。此外，数据并不总是每秒都有纬度和经度。一种方法是每分钟对位置进行平均，然后按分钟比较平均位置。至少它会减少60次迭代。

我希望有一些统计或 GIS 方法来建立路线的 "signature" 并比较签名而不是逐点比较。

关于如何以最有效的方式计算路由比较有什么想法吗？

注意：我在GIS论坛上发过一个类似的问题，但是还没有人回复。虽然，我确实认为这里写的问题更清楚。
https://gis.stackexchange.com/questions/187019/strava-activity-route-grouping

Answer 1

我假设以下内容为真：

对于每个骑车人 C，都有时间 T、经度 X 和纬度 Y 的数据流（我们使用投影 X 和 Y 来简化，不关心投影；但是，我们应该）
数据流可以写入数据库或其他类型的持久数据存储
C 的数据流以 1s 的速率采样，因为不能保证每个样本都被采集；我们必须假设样本是在超过 50% 的情况下被抽取的（最好 > 95%；99.7% 将是完美的）

在这种情况下，数据库中的一个 table 包含分析所需的所有数据。让我们看看两个骑自行车的人 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 在数据库中，为两个骑自行车的人自行加入 table。对于合理数量的行（例如 <10E5、<10E6）和正确设置的索引，此计算根本不是资源密集型的。特别是如果我们考虑到数据库查询可以这样写，即不是为每个位置输出值 D，而是为了聚合（计数）值而计算。在这种情况下，您所需要的只是行数的比率，其中 D 小于等于您的首选阈值 D0 与总行数。如果该比率等于或大于您的限制（例如 70%），则骑自行车的人会一起骑行。

让我们看一个例子。如果数据库中有这样的table，命名为CyclistPosition:

CyclistId - 骑车人的标识符
SamplingTime - 采样（位置）的 UTC 时间
经度-经度
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

我们现在有这种输出，如果我们包括粗略计算的 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

Strava - 带纬度、经度和时间的团体路线接近度

Strava - Group Route Proximity with Latitude, Longitude & Time

gis

comparison

maps

latitude-longitude