python - 找到多对点之间最近的 8 连通棋盘距离 : shortest m-path

Question

我正在使用 OpenCV 在 Python 中处理二进制图像。我有两组点:PNodes 和 FNodes。我想找到最接近每个 FNode 的 PNode(最短的 m 路径)；就 8 连通棋盘距离而言最接近。

在下面的示例中，假设 PNodes(由 * 捐赠)是:(6,1)、(6,5) 和 (5,8)。 (索引从 0 开始，第一个元素是行号)。 FNodes(用#表示)是:(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") 

我不关心距离的精确值，我只想找出最接近的一对。像这样:在 (0,1) 处的 FNode 最接近在 (6,1) 处的 PNode。 (4,3) 处的 FNode 最接近 (6,1) 处的 PNode。所有距离均以 8 连通棋盘距离表示。

整个过程的最终要求:基本上，我只是想确保所有 PNode 至少有 1 个 FNode 位于给定的距离范围内(沿着 1s 的路径)。

假设 PNode (PN_1) 有一个 FNode (FN_1) 在要求的距离范围内，我还要确保 PN_1 最接近 FN_1，而不是任何其他 PNode。

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

除了如图所示的 PNodes 和 FNodes 之外，我不关心此矩阵中的其他元素。

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]

然后对 i∈[0,7] 取 (x+dx[i], y+dy[i]) 生成给定的邻居单元格。

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