php – 多边形算法/伪代码中的最短路径

发布时间:2022-04-30 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了php – 多边形算法/伪代码中的最短路径脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
我有一个由X,Y点数组表示的多边形(用 PHP表示).我希望找到A点和B点之间多边形内的最短路径.实际上,我有一个任意区域,定义为一个简单的多边形,我希望知道距离(例如,将其视为表示多边形)一条小道 – 我想估计这条路有多长).

寻找伪代码或从哪里开始的一些提示.除了一些难以理解的关于三角测量和漏斗算法的论文之外,我已经浏览过互联网并且似乎运气不佳.

解决方法

谷歌搜索通过多边形的最短路径会产生许多有用的链接.一个算法的一个很好的描述是 found here(完成了一个applet动画算法).许多算法都是针对更复杂的问题 – 允许多边形中的孔.对于简单多边形的情况,可以不加改变地使用它们. (实际上,您的问题可以被认为是通过一般多边形找到路径的特殊情况,其中所有孔(障碍物)与边缘共享一个点.)

我认为最好的方法是通过由多边形顶点的可见性图加上起点和终点(如果它们不是顶点)定义的空间进行A *搜索.

脚本宝典总结

以上是脚本宝典为你收集整理的php – 多边形算法/伪代码中的最短路径全部内容,希望文章能够帮你解决php – 多边形算法/伪代码中的最短路径所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。