Route Planning and Map Inference with Global Positioning Traces
Route Planning and Map Inference with Global Positioning Traces
复制标题
DOI：
10.1007/3-540-36477-3_10
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
S. Edelkamp;Stefan Schrödl
中科院分区：
文献类型：
--
作者：
S. Edelkamp;Stefan Schrödl
导航系统几乎可以帮助物理世界中的任何运动，包括航行，飞行，徒步旅行，驾驶和骑自行车。另一方面，全球定位系统（Global Positioning Systems，GPS）提供的轨迹可以跟踪运动目标的实际时间和绝对坐标，因此，本文提出了基于GPS数据的路径规划问题的有效算法和数据结构;给定一组轨迹和当前位置，推断出一个短句Bentley和Bermmann的算法是将GPS的几何信息直接转换成一个组合的加权有向图结构，而这反过来又可以通过应用经典的和细化的图遍历算法，如Dijkstras的单源最短路径算法或A* 查询。对于高精度的地图推理，特别是在汽车导航，算法的道路分割，地图匹配和车道聚类。
Navigation systems assist almost any kind of motion in the physical world including sailing, flying, hiking, driving and cycling. On the other hand, traces supplied by global positioning systems (GPS) can track actual time and absolute coordinates of the moving objects.Consequently, this paper addresses efficient algorithms and data structures for the route planning problem based on GPS data; given a set of traces and a current location, infer a short(est) path to the destination.The algorithm of Bentley and Ottmann is shown to transform geometric GPS information directly into a combinatorial weighted and directed graph structure, which in turn can be queried by applying classical and refined graph traversal algorithms like Dijkstras’ single-source shortest path algorithm or A*.For high-precision map inference especially in car navigation, algorithms for road segmentation, map matching and lane clustering are presented.