OpenStreetMap路由 - Java Swing应用程序

Question

我是OSM的新手.我必须为我的MSc项目构建一个Java App.在这个项目中,我的应用程序需要从OSM(XML格式)下载原始数据,解析以在我的应用程序上显示它.之后,我必须在我的应用程序上部署路由服务.说实话,我以前从未这样做过,所以现在我很困惑.你们有什么想法或源代码可以帮助我吗？请你帮助我好吗？

非常感谢.

Answer 1

您可以使用像piccolo2d这样的2D绘图框架来渲染地图.对于路由,您需要构建一个图表,描述地图上的道路/方式,他们如何加入以及所代表的距离.在地图上选择起点和终点后,诸如A star之类的算法将帮助您找到点之间的最短路径.

更多细节:

OSM XML转储由三类实体组成(比这更复杂:查看完整细节的官方文档):

• 节点:表示地图上的单个点,由经度和纬度定义.这些要么代表着显着的特征(种类繁多,但是,例如:商店,古代纪念碑,道路上的大门等)或者是一种方式的一部分.
• 方法:在地图上表示多边形.它们由有序的节点列表(由id引用)构成,可以表示线性事物,例如道路和路径(与路由问题相关),但也可以表示有界区域,例如田地或森林边界,城市区域的形状,湖泊,河流等
• 关系:我不会在这里讨论,但你可以在官方文档中找到更多相关信息.

上述三种节点类型中的每一种都将以"标签"的形式具有与它们相关联的附加数据,"标签"是指定由节点/方式表示的实体类型的键值(字符串)对.一般的列表可以发现这里和路由列表在这里.从代表一条小型本地道路的OSM网站(在本例中为德国)中提取的示例:

<!-- The nodes representing points along the way -->
<node id="298884269" lat="54.0901746" lon="12.2482632" ... />
<node id="261728686" lat="54.0906309" lon="12.2441924" ... />
...
<node id="298884272" lat="54.0901447" lon="12.2516513" ... />

<!-- A way, built of the points above, with a tag
     declaring it to be an unclassified road -->
<way id="26659127" ...>
    <nd ref="292403538"/>
    <nd ref="298884289"/>
    ...
    <nd ref="261728686"/>
    <tag k="highway" v="unclassified"/>
</way>

在两种方式相交的情况下(例如,当两条道路交叉时),它们将在交叉点共享一个共同的节点.

要过滤到生成路由图所需的数据,您需要:

• 阅读感兴趣区域的XML,至少读取节点和方法.
• 过滤掉,只根据他们的标签留下您想要的方式(例如,k ="高速公路"等).
• 过滤掉所有节点,但剩余相关方式引用的节点.

只隔离了所需的信息,然后需要从OSM格式转换为更适合路由的格式.虽然所描述的OSM图可以用于路由,但是将地图表示为每条路的起点和终点的一组节点以及路和表示交叉点之间的路径的一组边的任何交叉点更有效. ,以及他们的长度.

例如,您可能希望转换以下内容(使用交叉方式ab,cd,ef):

更喜欢的东西:

只有末端节点和交叉节点保留的位置.在此表示中,您将在路由图(ax,cx,xe,ed,xy,ey,yf,yb)中从3个方向转换为8个边缘,每个边缘具有通过沿着节点中的节点步进计算的相关距离.方式,你去的地方累积距离:(例如斧头:200米,眼睛:350米等).请注意,您需要计算经度/纬度空间中相邻点之间的距离,您可以在此处找到公式.

您可以使用自己的数据结构或使用第三方图形库(如JGraphT或Jung)来表示此数据.从这里开始,路由是(粗略地,并且为了简单起见,假设您剩余的节点集合足够精细以表示所有必需的起点/终点),选择代表您的旅程开始的节点,节点代表结束并使用诸如A-star(如上所述)之类的算法来计算最短路径.

唯一的问题是,据我所知,我提到的两个图书馆都没有实现A-star.但是你可以通过以较低的速度运行Dijkstra的最短路径(存在于两个库中)来获得正确的结果 - 然后当你对这些概念更有信心时自己实现A-star.

为了使所有这些变得更有趣:不是使用距离,而是可以根据估计的旅行时间(考虑到道路上的平均速度)进行路线选择.或者您可以根据路线的需要来修改距离:例如,对于骑行,减少交通量较少的道路上的距离,以选择更长但更安全的路线.也可以徒步旅行,减少通过特别风景区或靠近古迹或酒吧等地标的路径的距离.

鉴于OSM数据存在合适的现有路由服务(例如来自Cloudmade),您想要做这样的事情的主要原因是为了使用您自己的自定义距离度量...

Answer 2

Alex答案包含重要部分.特别是要将节点减少到必要的节点!!

如果你有兴趣:我已经在我的GraphHopper项目中用Java开发了所有这些东西,并且使用了非常粗糙的Swing UI.

Dijkstra,双向dijkstra和astar也已实施.在我的测试中,当强制它没有返回路线的近似值时,恒星比dijkstra慢30%.在将来我会尝试允许近似,但同时你可以使用比正常dijkstra快〜50%的双向dijkstra;)并且工作方式如下: