最短路径/伪代码

Question

我有一个多边形（在PHP），通过X，Y点的数组来表示。我希望能够找到点A和点B.在实际应用中的多边形，我有一个任意区域，定义为一个简单的多边形内部的最短路径，我想知道通过的距离（例如，把它作为代表一个多边形一条线索 - 我想估计线索的时间长短）。

寻找伪代码或者从哪里开始的一些技巧。除了一些关于三角测量和漏斗算法的难以理解的论文之外，我浏览互联网似乎并不走运。

Answer 1

谷歌搜索最短路径通过多边形变成了很多有用的链接。一个算法的一个很好的描述是found here（完成一个applet动画演示算法）。许多算法是针对允许在多边形中出现空洞的更复杂的问题—。对于简单的多边形，它们可以不加修改地使用。 （其实，你的问题可以被认为是通过一般多边形寻找路径的特殊情况，其中所有的洞（障碍物）与边缘共享一个点。）

我认为最好的方法是A *搜索多边形顶点的可见性图形加上开始点和结束点（如果它们不是顶点）所定义的空间。

Answer 2

一个简单的算法使用的事实是，路径必须从反射顶点到反射顶点（除了第一步和最后一步）。因此，使用所有反射顶点和起点和终点来绘制图形，并使用标准最短路径算法找到最短路径。我有相当短的Mathematica代码，可以完成所有这些工作，并且很快将在网站的演示demo.wolfram.com上发布演示。如果你想要的代码给我一个消息。