how to generate all of the coordinates that are within a manhattan distance R of a given coordinate?-CodePudding

Am working in Python right now, and was trying to find a good solution for this. I can only really see brute forcing it working but cannot wrap my head around it as I cannot work out the conditions that could be used to make sure time isn't wasted looking at coordinates that are not within the manhattan radius. I feel there is some easy solution but it evades me.

my current best solution is generating all coordinates from -r to r on both axis, but this is twice as bad as it would be otherwise.

CodePudding user response：

Here's a simple solution:

def generateManhattanPoints(x, y, r):
    points = []
    for offset in range(r):
        invOffset = r - offset # Inverse offset
        points.append((x   offset, y   invOffset))
        points.append((x   invOffset, y - offset))
        points.append((x - offset, y - invOffset))
        points.append((x - invOffset, y   offset))
    return points

generateManhattanPoints(1, 2, 3)
# [(1, 5), (4, 2), (1, -1), ...]

All the points that are a manhattan-distance R from a center form a star-like shape. This function starts at the 4 tips of the star and then walks across the diagonals.

Image from https://en.wikipedia.org/wiki/Taxicab_geometry

CodePudding user response：

Overkill for 2 dimensions (for which Steggy's elegant answer is preferable), but if you want a solution that works in any dimensions:

import itertools

def sums(n,k):
    '''all nonnegative sums of k terms which sum to n'''
    for combo in itertools.combinations(range(n k-1),k-1):
        s = [combo[0]]
        for i in range(1,k-1):
            s.append(combo[i]-combo[i-1]-1)
        s.append(n k - 2 - combo[k-2])
        yield s

def manhattan_sphere(point,r):
    k = len(point)
    for differences in sums(r,k):
        signed_differences = [[-d,d] if d != 0 else [d] for d in differences]
        for p in itertools.product(*signed_differences):
            yield [x d for x,d in zip(point,p)]
        
def manhattan_dist(p,q):
    return sum(abs(x-y) for x,y in zip(p,q))

#test:
center = [1,0,2]
r = 2
for p in manhattan_sphere(center,r):
    print(p,manhattan_dist(p,center))

Output:

[1, 0, 0] 2
[1, 0, 4] 2
[1, -1, 1] 2
[1, -1, 3] 2
[1, 1, 1] 2
[1, 1, 3] 2
[1, -2, 2] 2
[1, 2, 2] 2
[0, 0, 1] 2
[0, 0, 3] 2
[2, 0, 1] 2
[2, 0, 3] 2
[0, -1, 2] 2
[0, 1, 2] 2
[2, -1, 2] 2
[2, 1, 2] 2
[-1, 0, 2] 2
[3, 0, 2] 2