Найти все точки на расстоянии 1 от конкретной точки в двумерной матрице

Question

Я хочу найти список точек, которые находятся в пределах диапазона 1 (или точно диагонали) от точки в моей матовой матрице:

Например скажи мою матрицу m является:

[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 1 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]] 

Я хотел бы получить список кортежей или что-то, представляющее все координаты 9 точек с X ниже:

[[0 0 0 0 0]
 [0 X X X 0]
 [0 X X X 0]
 [0 X X X 0]
 [0 0 0 0 0]]

Вот еще один пример с целевой точкой на краю:

[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 1]
 [0 0 0 0 0]
 [0 0 0 0 0]] 

В этом случае на расстоянии 1 от целевой точки будет только 6 точек:

[[0 0 0 0 0]
 [0 0 0 X X]
 [0 0 0 X X]
 [0 0 0 X X]
 [0 0 0 0 0]] 

---

РЕДАКТИРОВАТЬ:

Используя ответ / комментарий Дэвида Херринга о расстоянии по Чебышеву, я пытаюсь решить пример 2 выше, предполагая, что я знаю координаты целевой точки:

from scipy.spatial import distance

point = [2, 4]
valid_points = []
for x in range(5):
  for y in range(5):
    if(distance.chebyshev(point, [x,y]) <= 1):
      valid_points.append([x,y])

print(valid_points) # [[1, 3], [1, 4], [2, 3], [2, 4], [3, 3], [3, 4]]

Это кажется немного неэффективным для большого массива, так как мне нужно проверить только небольшой набор ячеек, а не весь мартикс.

Answer 1

Я думаю, что вы делаете это слишком сложным - не нужно полагаться на сложные функции

import numpy as np

# set up matrix
x = np.zeros((5,5))
# add a single point
x[2,-1] = 1 

# get coordinates of point as array
r, c = np.where(x)
# convert to python scalars
r = r[0]
c = c[0]
# get boundaries of array
m, n = x.shape

coords = []
# loop over possible locations
for i in [-1, 0, 1]: 
    for j in [-1, 0, 1]: 
        # check if location is within boundary
        if 0 <= r + i < m and 0 <= c + j < n:
            coords.append((r + i, c + j)) 

print(coords)

>>> [(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)]

Answer 2

Здесь нет алгоритма интереса здесь. Если вы еще не знаете, где находится 1, сначала вам нужно найти его, и вы не сможете добиться большего успеха, чем поиск по каждому элементу. (Вы можете получить ускорение с постоянным коэффициентом, имея numpy сделать это на скорости C с argmax; использование divmod разделить сплющенный индекс на строку и столбец.) После этого все, что вы делаете, это добавляете ±1 (или 0) к координатам, если это не приведет вас за пределы массива. Вы никогда не строите координаты только для того, чтобы отбросить их позже.

Answer 3

Простой способ - получить все возможные координаты с помощью декартового произведения.

Настройте данные:

x = np.array([[0,0,0], [0,1,0], [0,0,0]])
x
array([[0, 0, 0],
       [0, 1, 0],
       [0, 0, 0]])

Вы знаете, что координаты будут +/- 1 вашего местоположения:

loc = np.argwhere(x == 1)[0]  # unless already known or pre-specified
v = [loc[0], loc[0]-1, loc[0]+1]
h = [loc[1], loc[1]-1, loc[1]+1]

output = []
for i in itertools.product(v, h):
    if not np.any(np.array(i) >= x.shape[0]) and not np.any(np.array(i) < 0): output.append(i)

print(output)
[(1, 1), (1, 0), (1, 2), (0, 1), (0, 0), (0, 2), (2, 1), (2, 0), (2, 2)]