dijkstra - 二值图像/ map 中的真实最短路径

Question

如何在二进制图像/ map 中找到真正的最短路径？

我研究了不同的算法，例如Dijkstra 和 A*，但它们仅产生最短路径的近似值，因为所有像素仅以“8 连接”方式连接。

我可以使用什么算法来获得真正的最短路径 - 下图中的红线？

Answer 1

嗯，使用 8 个连接的网格意味着您只能找到沿 8 个邻居给出的方向前进的路径(0、+/-45、+/-90、+/-135、180) 。正如所附图片所示。

如果您需要使用 A*、Dijkstra 或类似方法来解决此问题，则解决此问题的唯一方法是增加路径的角度范围，增加网格的连接性(16 或 32 连接) 。即使如此，您的路径方向仍然有限。

为了解决您在问题中描述的问题，使用了其他类型的算法，例如 Theta*、Field D* 或 Block A*。这些算法能够找到任何角度的路径(根据您的问题的需要)，甚至使用 8 个连接的网格作为搜索的基础。看看Wikipedia entry: Any-angle path planning了解有关此类搜索的更多信息。

希望我的回答有帮助。