algorithm - 根据GPS位置确定用户所在的路径

Question

我正在编写一个应用程序，它利用 GPS 信息来确定用户所在的道路/小径(或 OpenStreetMaps 术语中的“方式”)。 OSM 中的方法不包含宽度信息，只是一系列连接在一起的点，因此无需弄清楚 GPS 坐标在哪个多边形框内。

我掌握的信息是定义路径弯曲时的点列表(如果它只是一条直线路径，可能是相距 1/2 英里的 2 个点)。这些小径通常由树线隔开(比如相隔 50-300 米)，公园内可能有很多小径，因此在边缘情况下，没有宽度信息的准确性可能会很棘手。通常路径定义沿着路径的中心运行。

看来我需要计算路径上的所有单个向量，然后找到最近的向量。我担心这对于每次新的 GPS 更新(每 1-4 秒？)都相当密集。我至少可以尝试提前填写每条路径上的点(强制每 x 米一个点)，然后在 GPS 更新时获取最近的点。

是否有任何结构可以预先调整点数据以协助计算？解决此问题的任何其他已知算法都是移动约束友好的？看起来这应该是一个已经解决的问题。

Answer 1

这就解决了，叫做 map 匹配。
我已经为收费目的编写了这样一个系统。有与实时匹配相关的变体，例如在导航系统中，或者像我的用于后处理 GPS 数据的非实时匹配。
但在每种情况下，至少需要一个月的开发努力。

如果你有一条 fork 成两条路径的小径，事情就会开始变得困难。
如果在这种情况下匹配到错误的路径没有问题，您可以简单地搜索最近的路径。

为避免过多的 CPU 处理能力，请使用地理空间索引，例如四叉树或 k-d 树。