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

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

0 голосов
/ 22 октября 2018

Я хочу найти список точек, которые находятся в пределах диапазона 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]]

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

Ответы [ 3 ]

0 голосов
/ 22 октября 2018

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

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)]
0 голосов
/ 22 октября 2018

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

Настройка данных: 

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)]
0 голосов
/ 22 октября 2018

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

...