我正在尝试在由凸多边形组成的系列上进行路径查找，而不是使用路径点。这还进一步复杂化了，因为这些多边形是由用户创建的，顶点可能不一致。例如：

我们知道物体宽X深Y，并且多边形的顶点位于特定位置。如果我理解正确，A*算法仅适用于路径点，那么是否有特定的算法可以找到到达目标的最快路径，同时保持整个物体在多边形内？如何处理顶点不是同一对象但位于相同位置的情况？

编辑：多边形是凸的；这是两个独立的多边形，边缘在同一条线上。此外，如何实现A*路径查找，因为基于节点的系统在’无限’分辨率的多边形中无法工作？

回答：

一般来说，所有最短路径的段都将以多边形顶点或起点和目标点作为端点。如果你构建一个包含所有这些段的图（从起点到每个“可见”的多边形顶点，从目标到每个“可见”的多边形顶点，从起点到目标，以及从每个多边形顶点到每个其他多边形顶点），并在该图上运行A*，你就有了最优路径。构建A*图的成本是：

• 对于每个顶点，进行可见性测试以查找可见顶点：简单算法（对于每对顶点，查看从一个到另一个的段是否位于多边形内）是O(n^3)。构建凸多边形并独立处理它们，或使用更智能的“径向扫描”算法可以大大降低这个成本，但我怀疑它仍然大约是O(n^2)。
• 对于每个查询（从起点到目标点），O(n)用于可见性测试以查找所有它可以看到的顶点。

如果你只打算应用一次A*，那么为单次遍历构建A*图的固定部分的成本可能会有些高。一个替代方案是随着使用逐步构建图：

实现上述方法的Java代码可以在这里找到。