Найти ближайшее 8-связное расстояние шахматной доски между несколькими парами точек: кратчайший m-путь

Question

Я работаю над бинарными изображениями в Python, используя OpenCV. У меня есть два набора точек: PNodes и FNodes. Я хочу найти ближайший PNode к каждому из FNodes (кратчайший m-путь); Ближайший с точки зрения 8-связной шахматной дистанции.

В приведенном ниже примере предположим, что PN-коды (подаренные *): (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") 

Меня не интересует точное значение расстояния, я просто хочу найти ближайшую пару. Примерно так: FNode в (0,1) ближе всего к PNode в (6,1). FNode в (4,3) ближе всего к PNode в (6,1). Все расстояния указаны с точки зрения расстояния между 8 шахматными досками.

Конечное требование всего этого процесса: в основном, я просто хочу убедиться, что все PNodes имеют как минимум 1 FNode, которые находятся в пределах заданного диапазона расстояний (вдоль пути 1 с).

Предположим, что PNode (PN_1) имеет FNode (FN_1), который находится в требуемом диапазоне расстояний, я также удостоверяюсь, что PN_1 является ближайшим к FN_1, а не любой другой PNode.

Для лучшего понимания я прикрепил изображение ниже; FNodes являются прямоугольными, а PNodes являются круглыми.

Меня не волнуют другие элементы в этой матрице, кроме элементов PNodes и FNodes, как изображено.

Answer 1

Я бы использовал алгоритм Дейкстры для этого. Он находит кратчайшее расстояние между узлом источника и каждым другим узлом, исследуя более близкие узлы перед более дальними узлами.

Запустите поиск Dijkstra в каждом из ваших P-узлов и остановите поиск, когда вы либо найдете первый 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]) для i∈[0,7], чтобы сгенерировать соседей данной ячейки.

Вы можете определить отдельный 2D-массив / матрицу для отслеживания посещений ячеек.