从GPS轨迹中识别常见的路径段

Question

9

我有一堆记录的GPS轨迹数据，其中有些是重复的路线，有些是完全不同的路线，还有一些是不同路线但有一些相同的路段。

基于这些数据，我想要：

1. 识别重复的路线 2. 识别多个路线共享的路段

我想第一项实际上是第二项的一个特例。

举个具体的例子：假设你有大量自行车通勤者每天的GPS轨迹数据。从这些数据中提取出基于实际骑行情况的最受欢迎的自行车通勤路线，而不是根据当地政府制作的自行车地图。

是否有已公开的算法来实现此功能？它们如何工作？欢迎提供相关论文和/或代码。

- gregspurrier

有街道数据可以将路径对齐，这样会容易得多。你能用那个吗？ - Nick Johnson

2个回答

1

您可以使用3D直方图找到地图上最常访问的点。通过这样，您可以推导出最常用的路径。

详细信息：保持2D矩阵计数并将其初始化为0，X [i，j] = 0。对于每个轨迹，在路径上递增X [i，j]。一旦您处理完所有轨迹，请将此矩阵阈值设置为最小阈值（它是重复行程所需的最小轨迹数是多少？）。

一些实际细节：假设您有一组路径经过的点。您可以使用http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm 找到两个这样的点之间路径上的点集。您可能需要画一个“更粗的线”来考虑数据的嘈杂性。

- ElKamina

地理坐标（纬度、经度）是连续值，所以 X[i,j] 可能不适用。 - stackoverflowuser2010

@stackoverflowuser2010 离散化。 - ElKamina

如果路径不是相当直的线路，那么你的方法将行不通。例如，假设从骑行数据中你找到了流行的点A、B、C，其中dist(A,B) < dist(A,C)。然而，自行车道可能实际上是A、C，然后是B（就像一个“U”形的路径）。你需要跟踪序列，而不仅仅是点。 - stackoverflowuser2010

@stackoverflowuser2010 我相当确定GPS数据也包含时间。毕竟，GPS卫星所做的就是传输时间。这应该可以缓解问题。 - ElKamina

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Federico · Accepted Answer

这似乎是一个与许多GIS问题相关的普遍性问题。

经过一些搜索，似乎您需要应用一些算法来计算任意两条路线之间的相似度。 Wang et al. (2013) 分析了许多这样的度量标准。然而，所有这些度量标准都是通过动态规划实现的，时间复杂度为O(N1N2)，其中N1和N2是两条路线中的点数。

Mariescu-Istodor et al. (2017) 提供了一种更有效的解决方案，其中每条路线都被转换为预定义网格系统中的一组单元格。该论文还定义了包含度量作为一个路线包含在另一个路线内的数量，这似乎与您问题中的第二点有关。