我有一个由X，Y点数组表示的多边形（用PHP表示） . 我希望找到A点和B点之间多边形内的最短路径 . 实际上，我有一个任意区域，定义为一个简单的多边形，我希望知道距离（例如，将其视为表示多边形）一条小道 - 我想估计一条小道的长度） .
寻找伪代码或从哪里开始的一些提示 . 除了一些难以理解的关于三角测量和漏斗算法的论文之外，我已经浏览了互联网并且似乎运气不佳 .
谷歌搜索通过多边形的最短路径会产生许多有用的链接 . 一个算法的一个很好的描述是found here（完成了一个applet动画算法） . 许多算法都是针对一个更复杂的问题 - 一个允许多边形中的孔的问题 . 对于简单多边形的情况，可以不加改变地使用它们 . （实际上，您的问题可以被认为是通过一般多边形找到路径的特殊情况，其中所有孔（障碍物）与边缘共享一个点 . ）
我认为最好的方法是通过由多边形顶点的可见性图加上起点和终点（如果它们不是顶点）定义的空间进行A *搜索 .
一个简单的算法使用路径必须从反射顶点移动到反射顶点的事实（第一步和最后一步除外） . 因此，使用所有反射顶点以及起点和终点制作图形，并使用标准的最短路径算法来查找最短路径 . 我有很短的Mathematica代码可以做到这一切，很快就会在demos.wolfram.com网站上发布一个演示 . 如果您需要代码，请给我发消息 .
2 回答
谷歌搜索通过多边形的最短路径会产生许多有用的链接 . 一个算法的一个很好的描述是found here（完成了一个applet动画算法） . 许多算法都是针对一个更复杂的问题 - 一个允许多边形中的孔的问题 . 对于简单多边形的情况，可以不加改变地使用它们 . （实际上，您的问题可以被认为是通过一般多边形找到路径的特殊情况，其中所有孔（障碍物）与边缘共享一个点 . ）
我认为最好的方法是通过由多边形顶点的可见性图加上起点和终点（如果它们不是顶点）定义的空间进行A *搜索 .
一个简单的算法使用路径必须从反射顶点移动到反射顶点的事实（第一步和最后一步除外） . 因此，使用所有反射顶点以及起点和终点制作图形，并使用标准的最短路径算法来查找最短路径 . 我有很短的Mathematica代码可以做到这一切，很快就会在demos.wolfram.com网站上发布一个演示 . 如果您需要代码，请给我发消息 .