多边形内最短路径算法/伪代码

Question

我有一个由X,Y坐标点数组表示的多边形（PHP）。我希望在点A和点B之间找到多边形内最短的路径。实际上，我有一个任意区域，定义为简单多边形，我想知道其中的距离（例如，将其视为代表小径的多边形-我想估计小径有多长）。

寻找伪代码或一些提示从哪里开始。我搜索了互联网，除了一些难以理解的三角剖分和漏斗算法论文外，似乎运气不佳。

- user690750

---

听起来像是作业...在谷歌上查找插入排序、归并排序。 - Lawrence Cherone

@Lawrence Cherone：这些排序算法与路径查找有什么关系？ - Christian Severin

问题的核心是优化。给定单位/值，寻找最短路径/最短时间进行排序。你真的认为你的导师想看到代码测量一个点到另一个点吗？ - Lawrence Cherone

你的多边形有任何特定的特征，还是一个完全一般的凸多边形？ - Dr. belisarius

@belisarus - 要么凸起要么凹陷，但始终简单（不重叠，没有环，没有孔）。 - user690750

Answer 1

在谷歌上搜索多边形最短路径会出现很多有用的链接。其中一个算法的详细描述可以在这里找到（包括一个演示该算法的应用程序）。许多算法都是针对更复杂的问题，即允许多边形中存在孔洞的问题。它们可以直接用于简单多边形的情况下（实际上，您的问题可以被视为在一般多边形中寻找路径的特殊情况，其中所有孔洞（障碍）与边缘共享一个点）。

我认为最好的方法是通过多边形顶点的可见性图以及起点和终点（如果它们不是顶点）定义的空间进行A*搜索。

- Ted Hopp

Answer 2

一个简单的算法利用了路径必须从凸顶点到凸顶点（除了第一步和最后一步）的事实。因此，使用所有凸顶点和起始点和终止点制作图形，并使用标准的最短路径算法找到最短路径。我有相当短的Mathematica代码可以做到这一点，并将很快在网站demonstrations.wolfram.com上发布演示版。如果您需要代码，请给我发消息。

- stan wagon