Search in a grid in a radial fashion, making circles around the central point going out once cell further on every iteration on a numpy matrix

radial_search_in_matrix.py

from itertools import product

# Author: Sammy Pfeiffer <Sammy.Pfeiffer at student.uts.edu.au>

# Note:
# the coords could be created taking into account the matrix
# bounds and stop exploring a direction when the bounds are hit
# but it is not implemented here as this good enough for now


def create_radial_offsets_coords(radius):
    """
    Creates an ordered by radius (without repetition)
    generator of coordinates to explore around an initial point 0, 0

    For example, radius 2 looks like:
    [(-1, -1), (-1, 0), (-1, 1), (0, -1),  # from radius 1
    (0, 1), (1, -1), (1, 0), (1, 1),  # from radius 1
    (-2, -2), (-2, -1), (-2, 0), (-2, 1),
    (-2, 2), (-1, -2), (-1, 2), (0, -2),
    (0, 2), (1, -2), (1, 2), (2, -2),
    (2, -1), (2, 0), (2, 1), (2, 2)]
    """
    # We store the previously given coordinates to not repeat them
    # we use a Dict as to take advantage of its hash table to make it more efficient
    coords = {}
    # iterate increasing over every radius value...
    for r in range(1, radius + 1):
        # for this radius value... (both product and range are generators too)
        tmp_coords = product(range(-r, r + 1), repeat=2)
        # only yield new coordinates
        for i, j in tmp_coords:
            if (i, j) != (0, 0) and not coords.get((i, j), False):
                coords[(i, j)] = True
                yield (i, j)


def look_for_closest_that_satisfies(x, y, matrix, func_to_satisfy, max_radius):
    """
    Given initial coordinates (x, y) to look for the closest cell in the grid 'matrix',
    a function that must be satisfied to return and a maximum radius in cells to
    look for, it returns as soon as a cell satisfies the function.

    :param x int: initial index on x
    :param y int: initial index on y
    :param matrix numpy.array: expected 2-dimensional numpy array
    :param func_to_satisfy func: function that returns a boolean when fed a cell of the matrix
    :param max_radius int: number of cells to use as max radius in the radial search

    :returns: first coordinates that satisfy func_to_satisfy or (-1, -1) otherwise
    """
    offset_coords_in_radial_order = create_radial_offsets_coords(max_radius)

    matrix_shape = matrix.shape

    for off_x, off_y in offset_coords_in_radial_order:
        x_to_check = x + off_x
        y_to_check = y + off_y
        # Not allowing to overlap to the other side of the matrix on negatives
        # and also not allowing to check out of the matrix bounds
        if -1 < x_to_check < matrix_shape[0] and -1 < y_to_check < matrix_shape[1]:
            if func_to_satisfy(matrix[x + off_x][y + off_y]):
                return x + off_x, y + off_y
    return -1, -1


if __name__ == '__main__':
    # Example/test
    import numpy as np

    matrix = np.zeros((300, 300))

    matrix[0][0] = 1.0

    def is_bigger_than_0(value):
        return value > 0.0

    # Too far, we wont find it
    print(look_for_closest_that_satisfies(
        100, 100, matrix, is_bigger_than_0, 10))

    # Now we will find it
    print(look_for_closest_that_satisfies(
        10, 10, matrix, is_bigger_than_0, 10))

    # Now we will find it at a higher cost
    print(look_for_closest_that_satisfies(
        300, 300, matrix, is_bigger_than_0, 300))