How to find the distance between two elements in a 2D array

Question

Let's say you have the grid:

list = [[-,O,-,-,O,-,],
        [O,-,-,-,-,O],
        [O,O,-,-,X,-],
        [-,-,O,-,-,-]]

How would you get the coordinates of all O's that are within a distance of 3 from X? From what I saw in other answers, using scipy.spatial.KDTree.query_ball_point seemed like a common approach but I was unable to figure out how to adapt it to my use case. One possible idea I had was to store every coordinate of the list such as coords=[[0,0],[0,1]...] and then use the scipy method and pass in the coordinate of the X and the searching distance. And then once I received the list of possible coordinates, I then iterate through the list and check which ones are equal to O. I was wondering, however, if there was a more efficient or more optimized solution I could use. Any help would be greatly appreciated.

Answer 1

You don't need to make it too complicate by using Scipy. This problem can easily done by help of mathematics.

Equation of coordinate inside circle is x^2 + y^2 <= Radius^2, so just check coordinate that inside the circle.

list = [[-,O,-,-,O,-,],
        [O,-,-,-,-,O],
        [O,O,-,-,X,-],
        [-,-,O,-,-,-]]
X_coor = #Coordinate of X, in this case y = 2, x = 4
d = #Maximum distance from X in this case d = 3
total = 0
O_coor = [] #Store coordinate of all O near X
for y in range(max(0, X_coor.y - d), min(list.length - 1, X_coor.y + d)):
    for x in range(max(0, X_coor.x - sqrt(d**2 - (y - X_coor.y)**2)), min(list.length - 1, X_coor.x + sqrt(d**2 - (y - X_coor.y)**2))):
        if list[y][x] == "O":
            total++
            O_coor.append([x, y])
print(total)
print(O_coor)

It a long code, but you can ask me parts that you don't understand.

Note: This solution check only coordinate in circle area not entire list, so even if you have large list this still very fast.