3

我对 OSM 很陌生。我必须为我的理学硕士项目构建一个 Java 应用程序。在这个项目中，我的应用程序需要从 OSM（XML 格式）下载原始数据，解析以将其显示在我的应用程序上。之后，我必须在我的应用程序上部署路由服务。老实说，我以前从未这样做过，所以我现在很困惑。你们有什么想法或源代码可以帮助我吗？请你帮助我好吗？

非常感谢。

4

2 回答 2

16

您可以使用piccolo2d之类的 2d 绘图框架来渲染地图。对于路线，您需要构建一个图表来描述地图上的道路/方式，它们如何连接以及表示的距离。在地图上选择了起点和终点后，A 星等算法将帮助您找到两点之间的最短路径。

更多细节：

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="highway" 等）。
  • 过滤掉所有节点，但其余相关方式引用的节点除外。

仅隔离了您需要的信息后，您需要从 OSM 格式转换为更适合路由的格式。尽管所描述的 OSM 图可用于路由，但将地图表示为每个路径的起点和终点的一组节点以及路径之间的任何交叉点和表示交叉点之间路径的一组边会更有效，以及它们的长度。

例如，您可能想要转换以下内容（使用交叉方式 ab、cd、ef）：

OSM节点和方式

更像是：

路由图

仅保留末端节点和相交节点的位置。在此表示中，您将在路由图中从 3 种方式转换为 8 条边（ax、cx、xe、ed、xy、ey、yf、yb），每条边都有一个关联距离，您通过沿着节点中的节点步进计算方式，随着你去累积距离：（例如ax：200m，ey：350m等）。请注意，您需要计算经度/纬度空间中相邻点之间的距离，您可以在此处找到公式。

您可以使用自己的数据结构或使用第三方图形库（例如JGraphT或Jung ）来表示这些数据。从这里开始，路由是（粗略地，并且为简单起见，假设您剩余的节点集足够细粒度以表示所有必需的起点/终点）选择代表旅程开始的节点的问题，节点代表最后并使用诸如A-star（如上所述）之类的算法来计算最短路径。

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

为了让这一切变得更有趣：您可以根据估计的旅行时间（考虑道路上的平均速度）而不是使用距离。或者您可以根据路线的需要修改距离：例如，对于骑自行车，在交通较少的道路上降低距离，以便选择更长但更安全的路线。或者，对于徒步旅行，减少穿过特别风景区或靠近地标（如古代纪念碑或酒吧）的路径的距离。

鉴于 OSM 数据有不错的现有路由服务（例如来自Cloudmade），您想要做这样的事情的主要原因是为了使用您自己的自定义距离度量......

于 2012-06-20T20:50:15.583 回答
8

亚历克斯的答案包含重要部分。尤其是将节点减少到只有必要的节点！

如果你有兴趣：我在我的GraphHopper项目中用 Java 开发了所有这些东西，并带有一个非常粗糙的 Swing UI。

还实现了 Dijkstra、双向 dijkstra 和 astar。在我的测试中，当强制它不返回路线的近似值时，星星比 dijkstra 慢 30%。将来我会尝试允许近似值，但与此同时，您可以使用双向 dijkstra，它比普通 dijkstra 快约 50% ;) 并像这样工作：

在此处输入图像描述

于 2012-06-29T12:49:25.937 回答