python - 如何在可步行的路径上找到两点之间的路径

Question

在类似上面的图像中，也假设二值化（1 代表白色，0 代表黑色）。白色区域代表可步行区域，2个红点只是为了告诉你起点和终点在哪里（但实际上2个红点的像素值仍然是1）。

如何找到从起点（可能是这两个红点中的任何一个）到另一个红点的路径？

搜索了一段时间，发现很多文章只谈论找到 2 个点之间的最短路径，但没有运气在可步行区域加入这些点。

我对这个问题的最初想法是使用所谓的“注水”方法来找出路径，但它需要递归调用，这很慢且内存密集。路径需要非常快速地绘制，因为它位于 RPi 上的视频流中，因此计算能力并不强。

欢迎任何想法和代码。

更新

为了更清楚：

1. 作为起点的一个点将始终是底部的一个（固定位置）并且

2. 另一点在同一个分支迷宫中。

3. 让我们假设必然存在一条现有路径。

4. 可以有多个路径，但我正在寻找最短路径

5. 路径不是太靠近可步行区域的边缘，这意味着路径在边缘有一个边距 X（宽度）。（可选）

标签： pythonalgorithmopencvimage-processingopencv-python

Answer 1

您可以使用路径规划算法的任何实现，如 A*，并在搜索矩阵时使用每个像素，其中 0 是可步行路径，1 是不可步行（墙壁）

这是实施的要点 https://gist.github.com/ryancollingwood/32446307e976a11a1185a5394d6657bc

以及您需要根据需要导入和子类化的通用解决方案 https://github.com/jrialland/python-astar