4

I want to find a list of points that are within range 1 (or exactly diagonal) of a point in my numpy matrix:

For example say my matrix m is:

[[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]]

I would like to obtain a list of tuples or something representing all the coordinates of the 9 points with X's below:

[[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]]

Here is another example with the target point on the edge:

[[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]]

In this case there would only 6 points within distance 1 of the target point:

[[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]]

EDIT:

Using David Herrings answer/comment about chebyshev distance here is my attempt to solve example 2 above assuming I know the coordinates of the target point:

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]]

This seems a little inefficient for a bigger array as I only need to check a small set of cells really not the whole martix.

simonsaysgetlit
  • 43
  • 4

3 Answers3

1

There is no algorithm of interest here. If you don’t already know where the 1 is, first you have to find it, and you can’t do better than searching through every element. (You can get a constant-factor speedup by having numpy do this at C speed with argmax; use divmod to separate the flattened index into row and column.) Thereafter, all you do is add &pm;1 (or 0) to the coordinates unless it would take you outside the array bounds. You don’t ever construct coordinates only to discard them later.

Davis Herring
  • 36,443
  • 4
  • 48
  • 76
  • I need to use the number of valid coordinates to calculate a probability (I need to assign each of the valid coordinates 0.9/num_valid_coordinates) and I need to assign the rest of the coordinates (the non valid ones in the matrix: 0.1/num_non_valid_coordinates). – simonsaysgetlit Oct 21 '18 at 23:56
  • @simonsaysgetlit: Then you want to find the coordinates, count the neighborhood (always 4, 6, or 9 on a large enough grid), and then form the probabilities. The last can be done easily with broadcasting—did you want to edit that into your question? – Davis Herring Oct 22 '18 at 00:44
1

I think you're making it a little too complicated - no need to rely on complicated functions

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)]
Cory Nezin
  • 1,551
  • 10
  • 22
0

A simple way would be to get all possible coordinates with a cartesian product

Setup the data:

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

You know that the coordinates will be +/- 1 of your location:

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)]
Simon
  • 9,762
  • 15
  • 62
  • 119