1

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

在下面的示例中，假设 PNode（由 * 捐赠）是：(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，如图所示。

在此处输入图像描述

4

1 回答 1

0

我会为此使用Dijkstra 的算法。它通过在更远的节点之前探索更近的节点来找到源节点和每个其他节点之间的最短距离。

在每个 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]) for i∈ [0,7]生成给定单元格的邻居。

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

于 2018-01-24T18:45:53.937 回答