algorithm - 寻找2个对象之间最短路径的算法

Question

我有一个平面图，上面有很多代表展位的 d3.js 多边形对象。我想知道在不与其他对象重叠的 2 个对象之间找到路径的最佳方法是什么。这里的用例是我们有摊位，想向用户展示如何步行以最有效地从 a 点到达 b 点。我们可以假设路径必须只包含 90 或 45 度转弯。

我们尝试使用 Dijkstra，但它的规模似乎正在远离我们。

我们系统的示例快照：

我们的限制是这需要在浏览器中运行。如果它与 d3.js 配合得很好，那就太好了。

Answer 1

由于布局是一个矩阵（或嵌套矩阵），这不是 Dijkstra 问题，它比这更简单。该问题的技术名称是“曼哈顿路由”。我将在下图中向您展示最佳路线（蓝线）的示例，而不是给出代码算法。从这里应该很明显算法是什么： 注意这里有一个微妙的细微差别，那就是你总是想要最大化慢跑的数量，因为即使整体形状是一个矩阵，在每个角落，人实际上都会斜着走（想象一个人斜着穿过四路交叉口）。因此，简单地向北走，然后向西走是错误的，因为你只能走一个弯，但在所示路线上你可以走 5 个弯。

Answer 2

这个问题被称为寻找具有多边形障碍物的两点之间的最短路径，并且在文献中进行了很多研究。请参见此处的一个示例。用于此的所有算法都是通过将问题转换为图论问题然后运行 ​​Dijkstra。为此：

1. 任何多边形中的每个顶点都是图中的顶点。
2. 起点和终点也是图中的顶点。
3. 两个顶点之间有一条边，如果它们彼此可见，我们可以使用三角测量算法来实现这一点。
4. 每条边的权重是其在欧几里得空间中的两个端点之间的距离。

现在我们准备运行任何最短路径算法。困难的部分是三角测量，我认为三角形库适合您的要求。同样更简单的方法是通过我在第一行中所说的关键字搜索网络以找到实现。我没有链接到任何实现，因为我认为最好以算法方式说出来，以便对未来的读者有用。