在多对点之间查找最近的8连通棋盘距离：最短的mpath

Question

我正在使用OpenCV在Python中处理二进制图像。我有两组点：PNodes和fnode。我想找到每个fnode最近的PNode（最短的m路径）；在8连通的棋盘距离方面最近。在

在下面的例子中，假设PNodes（由*捐赠）是：（6,1）、（6,5）和（5,8）。（索引从0开始，第一个元素是行号）。f节点（用#表示）有：（0,1）、（0,9）、（1,6）、（2,5）和（4,3）。在

import numpy as np 
In = np.array ((
      [ 0,  1#, 0,  0,  0,  0,  0,  0,  0,  1#, 0],
      [ 1,  0,  0,  0,  0,  0,  1#, 0,  1,  0,  0],
      [ 0,  1,  0,  0,  0,  1#, 0,  0,  1,  0,  0],
      [ 0,  0,  1,  0,  0,  0,  1,  0,  0,  1,  0],
      [ 0,  1,  1,  1#, 0,  1,  0,  0,  1,  0,  0],
      [ 0,  1,  0,  0,  0,  1,  0,  0,  1*, 0,  0],
      [ 0,  1*, 0,  0,  0,  1*, 0,  0,  1,  0,  0],
      [ 0,  1,  0,  0,  1,  0,  1,  1,  0,  0,  0],
      [ 0,  0,  1,  1,  0,  0,  0,  1,  0,  0,  0]), dtype = "uint8") 

Distance_Matrix =  np.array ((
      [ 0,  6#, 0,  0,  0,  0,  0,  0,  0,  5#, 0],
      [ 5,  0,  0,  0,  0,  0,  5#, 0,  4,  0,  0],
      [ 0,  4,  0,  0,  0,  4#, 0,  0,  3,  0,  0],
      [ 0,  0,  3,  0,  0,  0,  3,  0,  0,  2,  0],
      [ 0,  2,  2,  3#, 0,  2,  0,  0,  1,  0,  0],
      [ 0,  1,  0,  0,  0,  1,  0,  0,  **, 0,  0],
      [ 0, **,  0,  0,  0,  **, 0,  0,  1,  0,  0],
      [ 0,  1,  0,  0,  1,  0,  1,  1,  0,  0,  0],
      [ 0,  0,  1,  1,  0,  0,  0,  1,  0,  0,  0]), dtype = "uint8") 

我不关心距离的确切值，我只想找出最接近的一对。如下所示：FNode在（0,1）处最接近PNode在（6,1）。（4,3）处的FNode最接近（6,1）处的PNode。所有距离都是以8连棋盘距离表示的。在

整个过程的最终要求：基本上，我只想确保所有pnode至少有1个FNode，它们位于给定的距离范围内（沿着1s的路径）。在

假设PNode（PN_1）有一个FNode（FN_1），它位于所需的距离范围内，我还确保PN_1最接近FN_1，而不是任何其他PNode。在

为了更好的理解，我在下面附上了一张图片：fnode是矩形的，PNodes是圆形的。在

我不关心这个矩阵中的其他元素，除了PNodes和fnode，如图所示。在

Answer 1

我会用Dijkstra's algorithm来做这个。它通过先搜索较近的节点，再搜索距离较远的节点，从而找到源节点与其他节点之间的最短距离。在

在每个p节点上进行Dijkstra搜索，并在找到第一个F节点或超出距离限制时停止搜索。在

因为你不能使用邻域图生成偏移。例如，如果有一个单元格（x，y），则可以定义一些偏移量

dx = [-1,-1, 0, 1,1,1,0,-1]
dy = [ 0,-1,-1,-1,0,1,1, 1]

然后取（x+dx[i]，y+dy[i]）来生成给定细胞的邻域。在

您可以定义一个单独的二维数组/矩阵来跟踪单元格是否被访问过。在