Finding n-dimensional neighbors

Question

I am trying to get the neighbors of a cell in an n-dimensional space, something like 8-connected or 26-connected cells, but at any dimensionality provided an n-tuple.

Neighbors that are directly adjacent are easy enough, just +1/-1 in any dimension. The part I am having difficulty with are the diagonals, where I can have any quantity of coordinates differing by 1.

I wrote a function that recurs for each sub-dimension, and generates all +/- combinations:

def point_neighbors_recursive(point):
    neighbors = []
    # 1-dimension
    if len(point) == 1:
        neighbors.append([point[0] - 1])  # left
        neighbors.append([point[0]])  # current
        neighbors.append([point[0] + 1])  # right

        return neighbors

    # n-dimensional
    for sub_dimension in point_neighbors_recursion(point[1:]):
        neighbors.append([point[0] - 1] + sub_dimension)  # left
        neighbors.append([point[0]] + sub_dimension)  # center
        neighbors.append([point[0] + 1] + sub_dimension)  # right

    return neighbors

However this returns a lot of redundant neighbors. Are there any better solutions?

Answer 1

I'll bet that all you need is in the itertools package, especially the product method. What you're looking for is the Cartesian product of your current location with each coordinate perturbed by 1 in each direction. Thus, you'll have a list of triples derived from your current point:

diag_coord = [(x-1, x, x+1) for x in point]

Now, you take the product of all those triples, recombine each set, and you have your diagonals.

Is that what you needed?