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.

CodePudding user response：

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.