Simple square grid lookup

Question

I'm drawing a blank on trying to come up with a simple square grid lookup in python and hope someone can give me some pointers here. Let's say I have a 5x5 grid, starting from the center (3,3), I'd like the lookup to step up the radius outputting the peripheral coordinates like this:

 Radius     Output   
   0        [[3,3]]   
   1        [[2,2], [2,3], [2,4], [3,2], [3,4], [4,2], [4,3], [4,4]]   
   2        [[1,1], [1,2], [1,3], [1,4], [1,5], [2,1], [2,5], [3,1], 
             [3,5], [4,1], [4,5], [1,1], [1,2], [1,3], [1,4], [1,5]]

Any pointers will be greatly appreciated!

UPDATE: The code I have at the moment is:

center_coordinate = [3, 3]
completed_locations = [center_coordinate]
radius = 0
max_radius = 3
while radius != max_radius:
    x_grid = [x for x in range(center_coordinate[0] - radius, center_coordinate[0] + radius + 1)]
    y_grid = [y for y in range(center_coordinate[0] - radius, center_coordinate[0] + radius + 1)]
    locations = []
    for x in x_grid:
        for y in y_grid:
            if [x, y] not in completed_locations:
                locations.append([x, y])
                completed_locations.append([x, y])
    radius += 1
    print(radius, locations)

While this does do the job, I am looking for a solution that wouldn't require me to cross check each location as it iterates through.. the actual grid size i'll be working against is 750x750 and this particular module will be called on regularly.

Answer 1

Thanks for the pointer @think-maths. I've adapted my code an appreciate the significant boost to performance. I've included both the codes here as reference for anyone doing something similar (like iterating over a game's tile map ;) ).

def adapted_lookup(center_coordinate, max_radius=50):
    # ADAPTED FROM think-maths
    center_coordinate = [375, 375]
    locations_by_radius = []
    radius = 0
    while radius != max_radius:
        x_grid = [x for x in range(center_coordinate[0] - radius, center_coordinate[0] + radius + 1)]
        y_grid = [y for y in range(center_coordinate[0] - radius, center_coordinate[0] + radius + 1)]
        locations = []
        if len(x_grid) > 1:
            for x in x_grid:
                locations.append([x, y_grid[0]])
                if x == x_grid[0] or x == x_grid[-1]:
                    for y in range(y_grid[1], y_grid[-1]):
                        locations.append([x, y])
                locations.append([x, y_grid[-1]])
        else:
            locations.append([x_grid[0], y_grid[0]])
        locations_by_radius.append([radius, locations])
        radius += 1


def original_lookup(center_coordinate, max_radius=50):
    # ORIGINAL CODE
    locations_by_radius = []
    checked = []
    radius = 0
    while radius != max_radius:
        x_grid = [x for x in range(center_coordinate[0] - radius, center_coordinate[0] + radius + 1)]
        y_grid = [y for y in range(center_coordinate[0] - radius, center_coordinate[0] + radius + 1)]
        locations = []
        for x in x_grid:
            for y in y_grid:
                if [x, y] not in checked:
                    locations.append([x, y])
                    checked.append([x, y])
        locations_by_radius.append([radius, locations])
        radius += 1

Performance according to timeit for a radius of 40 in a 750x750 grid:

Original Lookup Time: 14.5097
Adapted Lookup Time: 0.0020

Answer 2

For such kind of problem where you traverse through grids to form circle then Midpoint circle algorithm is a possibility

For example to demonstrate you can use something like this according to your need to implement your requirement

def midPointCircleDraw(x_centre, y_centre, r): 
    x = r 
    y = 0
    
    print("(", x + x_centre, ", ",  
               y + y_centre, ")",  
               sep = "", end = "")  
    
    
    if (r > 0) : 
      
        print("(", x + x_centre, ", ", 
                  -y + y_centre, ")",  
                  sep = "", end = "")  
        print("(", y + x_centre, ", ",  
                   x + y_centre, ")", 
                   sep = "", end = "")  
        print("(", -y + x_centre, ", ",  
                    x + y_centre, ")", sep = "")  
      
     
    P = 1 - r  
  
    while x > y: 
      
        y += 1
          
       
        if P <= 0:  
            P = P + 2 * y + 1
              
         
        else:          
            x -= 1
            P = P + 2 * y - 2 * x + 1
          
        if (x < y): 
            break
           
        print("(", x + x_centre, ", ", y + y_centre, 
                            ")", sep = "", end = "")  
        print("(", -x + x_centre, ", ", y + y_centre,  
                             ")", sep = "", end = "")  
        print("(", x + x_centre, ", ", -y + y_centre, 
                             ")", sep = "", end = "")  
        print("(", -x + x_centre, ", ", -y + y_centre, 
                                        ")", sep = "")  
          
         
        if x != y: 
          
            print("(", y + x_centre, ", ", x + y_centre,  
                                ")", sep = "", end = "")  
            print("(", -y + x_centre, ", ", x + y_centre, 
                                 ")", sep = "", end = "")  
            print("(", y + x_centre, ", ", -x + y_centre, 
                                 ")", sep = "", end = "")  
            print("(", -y + x_centre, ", ", -x + y_centre,  
                                            ")", sep = "")