algorithm - 用于移动设备的 j2me 中的导航算法实现

Question

作为我大学项目的一部分，我正在开发一个定制的移动导航应用程序。我正在使用 J2ME。

自定义是指应用程序只能在用户希望使用的地方使用。现在，“定制”区域是我的大学校园。因此，如果任何学生需要指示才能到达他的教室或街区，他将被引导到那个位置。

我不能使用谷歌地图，因为校园没有完全被它们覆盖。所以我获取所有街区和道路的坐标并存储在我的 landmarkstore 中并创建一个迷你坐标 map 。

现在真正的问题是“我如何实现应用程序的导航部分”？ 这就是我目前的实现行动计划。

我决定使用 Dijkstra 算法来寻找最短路径。我将把用户的当前位置添加到图中并将其称为源。 成本邻接矩阵将在程序中填充。

现在算法可以工作了，最短路径是用第一条指令生成的，例如。向正北移动 100 米。

用户照此进行，但犯了错误并走错了方向。我如何不断检查用户是否在朝着正确的方向前进？ 如果我每 10 秒检查一次他的位置并在他走错路线时提醒他(我也不知道该怎么做!即检查他是否走在正确的路线上)并再次生成新的方向，我不会正在减慢应用程序的速度？

有没有更好的实现方式？

PS:请帮助我了解坐标必须如何存储在我的数据库中(landmarkstore) 我应该存储每个小距离(例如 5 米)的坐标，还是应该使用更长的距离，以便减少图中的节点数量并使算法运行得更快。

Answer 1

首先，可以很容易地检测到“走错了路”:到达目的地的最短路径的长度在增加。或者，如果您在最佳路径上有一些“检查点”，那么用户就会离开下一个检查点。

对于复杂性，不要每 5 米或其他距离使用一个点:您需要在 map 中有一些主要点(每扇门、走廊交叉口...)，这样您就可以给您大致的方向。你甚至可以想象预先计算每栋建筑之间的最短路径，然后再计算每栋建筑内的最短路径；你首先需要离开大楼去另一栋楼。

无论如何，一旦你有了这些要点，你只需要在 map 上添加一个点(用户位置)并将其连接到邻近的“要点”。

你的图中现在有多少个节点？

---

编辑:

基本上这个想法是这样的:给定所有的道路，很容易预先计算出从道路的任何一点到任何建筑物的最短路径。无需为每条道路都这样做，只需将每个交叉路口或建筑物视为图中的一个节点。然后给定道路上的一个点，你只有两种可能性来读取一个节点:左或右。 (这当然假设人们留在路上但可以很容易地适应;))。

现在给定一个人的位置找到最近的道路，并找到到这些道路的最短路径。您现在在不同的道路上有几个位置，很容易计算到目的地的最短路径。由于几乎所有内容都在预先计算，因此每秒更新您的信息多次。

您可以向此人发出指示，如果您注意到到目的地的距离正在增加，您可以警告他走错了方向。