我正在编写一个应用程序，它利用 GPS 信息来确定用户所在的道路/小径（或 OpenStreetMaps 术语中的“方式”）。OSM 中的方式不包括宽度信息，只是一系列连接在一起的点，因此无需确定 GPS 坐标在哪个多边形框中。
我拥有的信息是定义路径弯曲时的点列表（如果它只是一条直线路径，则可能相距 2 个点 1/2 英里）。这些小径通常由树线隔开（例如相距 50-300 米），公园内可能有很多这样的小径，因此在边缘情况下没有宽度信息的准确性可能会很棘手。通常定义沿着路径的中心运行的方式。
似乎我需要计算轨迹上的所有单个向量，然后找到最近的向量。我担心这对于每次新的 GPS 更新（每 1-4 秒？）都相当密集。我至少可以尝试提前填写每条路径上的点（每 x 米强制一个点），然后在 GPS 更新时获取最近的点。
是否有任何结构可以预先调整点数据以帮助计算？解决此问题的任何其他已知算法对移动约束友好吗？似乎这应该是一个已经解决的问题。
这个解决了，叫做Map Matching。
我为收费目的编写了这样一个系统。有一些与实时匹配相关的变体，比如在导航系统中，或者像我的用于后处理 GPS 数据的非实时。
但在每种情况下，至少需要几个月的开发努力。
如果您有一条分叉两条路径的小路，事情就会开始变得困难。
如果在这种情况下匹配错误的路径没有问题，您可以简单地搜索最近的路径。
为了避免过多的 CPU 功率，请使用地理空间索引，如四叉树或 kd 树。
大概您正在使用从某种数据格式绘制地图的地图渲染 API。这本质上是一个特殊用途的数据库，称为空间数据库。在理想的世界中，它应该具有查找一定距离内的所有道路和路径的有效功能，例如 50 米。
一旦你有附近道路和路径的列表，即使在一个密集的区域，就在一个路口旁边，也不会超过低位的十个，你可以一个一个地遍历它们并找到最近的一个您的 GPS 定位。有一些标准方法可以找到离线最近的点；这里有一个讨论：得到最接近线的点。
这个系统（根据我的经验）应该足够快，足以每秒更新 GPS。
如果您遵循预定路线，它会更快，因为您只需要检查路线的路段 - 当然，如果他或她离路线太远而无法被视为在路线上，请通知用户，然后创建一条新路线。这就是卫星导航系统所做的。