我正在編寫一個應用程序，它利用GPS信息確定用戶所在的道路/軌跡（或OpenStreetMaps術語中的「路徑」）。 OSM中的方法不包括寬度信息，只是一系列連接在一起的點，所以它不是一個計算GPS座標所在多邊形框的問題。根據GPS位置確定路徑用戶
我所擁有的信息是在彎曲時定義線索（如果它只是一條直線，可能相隔2英里）。這些路徑通常由樹狀線（相隔50至300米）分隔開來，並且在公園內可以有很多這樣的路徑，所以在邊緣情況下沒有寬度信息的精度可能會非常棘手。通常，路徑定義沿着路徑的中心。
看來我需要計算一條路上的所有單個向量，然後找到最近的向量。我擔心這種情況會與每次新的GPS更新（每隔1-4秒？）密切相關。我至少可以嘗試在每條路線上填寫點數（每x米強制一個點），然後在GPS更新時取得最近點。
是否有任何結構可以將點數據預先調整爲輔助計算？任何其他已知的算法來解決這個問題，這是移動的，違反友好？似乎這應該是一個已經解決的問題。
這個解決了，它被稱爲地圖匹配。
我已經寫了這樣的收費系統。存在與實時匹配相關的變體，如在導航系統中，或者像我的非實時類似的後處理GPS數據。
但是在任何情況下，至少有一個月的時間都在努力發展。
如果你有兩條路徑分叉，事情就會變得困難起來。
如果在這種情況下錯誤路徑匹配時沒有問題，則可以簡單地搜索最近的路徑。
爲了避免CPU佔用太多，可以使用地理空間索引，如四叉樹或k-d樹。
大概你正在使用地圖渲染API，它從一些數據格式繪製地圖。這實質上是一個稱爲空間數據庫的專用數據庫。在一個理想的世界裏，它應該有一個有效的功能來找到一定距離內的所有道路和路徑，比如50米。
一旦你有附近的道路和路徑的列表，即使在高度建成的區域中，緊鄰路口，也不會超過低十幾個，你可以逐個查看它們並找到最接近你的GPS定位。有標準的方法來找到一條線的最近點;這裏有一個討論：get closest point to a line。
這個系統應該（從我的經驗來看）對於每秒GPS更新來說足夠快。
如果您遵循預定的路線，速度會更快，因爲您只需要檢查路線的各個部分 - 當然，如果用戶離路線太遠而被視爲在上面，然後創建一個新的路線。這就是衛星導航系統所做的。