我必须获得二维两点之间的（最短）/（最佳）距离。我必须避免可能连接在一起的线条形状。关于如何表示我可以行驶的节点有什么建议吗？我曾想过制作一个网格，但这听起来不太准确或优雅。如果一条线的任何点位于正方形内（该节点是正方形的中心），我会认为该节点不可行走。
一个例子是从 A 点到 B 点。
网格是解决这个问题的推荐方法吗？提前非常感谢！
我认为这本质上是拉斯曼斯的答案，更加算法化：
图的节点是障碍物顶点。每个内部顶点实际上代表两个节点：凹侧和凸侧。
- 使用欧氏启发式距离将起始节点推入优先级队列。
- 从优先级队列中弹出顶部节点。
- 进行从节点到目标的线相交测试（可能使用光线追踪数据结构技术来加速）。如果失败了，
- 考虑从当前节点到每个其他顶点的射线。如果当前节点与所考虑的顶点之间不存在交集，并且该顶点从当前节点的角度来看是凸的，则将该顶点添加到优先级队列中，使用当前节点中的累积距离加上距当前节点的距离进行排序节点到顶点加上启发式距离。
- 返回2。
如果障碍物中存在诸如“T”字形交叉点之类的东西，您必须做额外的预处理工作，并且我不会惊讶地发现它在许多情况下会破裂。通过仅考虑位于当前节点和目标之间的连接组件的顶点，您也许能够使事情变得更快。
所以在你的例子中，在第一次尝试之后A,B，你会推A,8, A,5, A,1, A,11, and A,2。首先要考虑的节点是A,8, A,1, and A,5，但他们出不去，而且他们能到达的节点已经被推到了累积距离较短的队列上。A,2 and A,11将被考虑，事情将从那里开始。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
