Efficient method to determine location on a grid(array)

Question

I am representing a grid with a 2D list in python. I would like to pick a point (x,y) in the list and determine it's location...right edge, top left corner, somewhere in the middle...

Currently I am checking like so:

         # left column, not a corner
         if x == 0 and y != 0 and y != self.dim_y - 1:
             pass
         # right column, not a corner
         elif x == self.dim_x - 1 and y != 0 and y != self.dim_y - 1:
             pass
         # top row, not a corner
         elif y == 0 and x != 0 and x != self.dim_x - 1:
             pass
         # bottom row, not a corner
         elif y == self.dim_y - 1 and x != 0 and x != self.dim_x - 1:
             pass
         # top left corner
         elif x == 0 and y == 0:
             pass
         # top right corner
         elif x == self.dim_x - 1 and y == 0:
             pass
         # bottom left corner
         elif x == 0 and y == self.dim_y - 1:
             pass
         # bottom right corner
         elif x == self.dim_x - 1 and y == self.dim_y - 1:
             pass
         # somewhere in middle; not an edge
         else:
             pass

Where I have some function do something after the location is determined

dim_x and dim_y are the dimensions of the list.

Is there a better way of doing this without so many if-else statements? Something efficient would be good since this part of the logic is being called a couple million times...it's for simulated annealing.

Thanks in advance. Also, what would be a better way of wording the title?

Answer 1

# initially:
method_list = [
    bottom_left, bottom, bottom_right,
    left, middle, right,
    top_left, top, top_right,
    ]

# each time:
keyx = 0 if not x else (2 if x == self.dim_x - 1 else 1)
keyy = 0 if not y else (2 if y == self.dim_y - 1 else 1)
key = keyy * 3 + keyx
method_list[key](self, x, y, other_args)

Untested ... but the general idea should shine through.

Update after the goal posts were drastically relocated by "Something efficient would be good since this part of the logic is being called a couple million times...it's for simulated annealing":

Originally you didn't like the chain of tests, and said you were calling a function to handle each of the 8 cases. If you want fast (in Python): retain the chain of tests, and do the handling of each case inline instead of calling a function.

Can you use psyco? Also, consider using Cython.

Answer 2

If I understand correctly, you have a collection of coordinates (x,y) living in a grid, and you would like to know, given any coordinate, whether it is inside the grid or on an edge.

The approach I would take is to normalize the grid before making the comparison, so that its origin is (0,0) and its top right corner is (1,1), then I would only have to know the value of the coordinate to determine its location. Let me explain.

0) Let _max represent the maximum value and _min, for instance, x_min is the minimum value of the coordinate x; let _new represent the normalized value.

1) Given (x,y), compute: x_new = (x_max-x)/(x_max-x_min) and y_new=(y_max-y)/(y_max-y_min).

2) [this is pseudo code]
switch y_new:
  case y_new==0: pos_y='bottom'
  case y_new==1: pos_y='top'
  otherwise: pos_y='%2.2f \% on y', 100*y_new
switch x_new:
  case x_new==0: pos_x='left'
  case x_new==1: pos_x='right'
  otherwise: pos_x='%2.2f \% on x', 100*x_new

print pos_y, pos_x

It would print stuff like "bottom left" or "top right" or "32.58% on y 15.43% on x"

Hope that helps.

Answer 3

def location(x,y,dim_x,dim_y):
    index = 1*(y==0) + 2*(y==dim_y-1) + 3*(x==0) + 6*(x==dim_x-1)
    return ["interior","top","bottom","left","top-left",
            "bottom-left","right","top-right","bottom-right"][index]

Answer 4

I guess if you really want to treat all these cases completely differently, your solution is okay, as it is very explicit. A compact solution might look more elegant, but will probably be harder to maintain. It really depends on what happens inside the if-blocks.

As soon as there is a common handling of, say, the corners, one might prefer to catch those cases with one clever if-statement.

Answer 5

Something like this might be more readable / maintainable. It will probably be a lot faster than your nested if statements since it only tests each condition once and dispatches through a dictionary which is nice and fast.

class LocationThing:

    def __init__(self, x, y):
        self.dim_x = x
        self.dim_y = y

    def interior(self):
        print "interior"
    def left(self):
        print "left"
    def right(self):
        print "right"
    def top(self):
        print "top"
    def bottom(self):
        print "bottom"
    def top_left(self):
        print "top_left"
    def top_right(self):
        print "top_right"
    def bottom_left(self):
        print "bottom_left"
    def bottom_right(self):
        print "bottom_right"

    location_map = {
        # (left, right,   top, bottom)
        ( False, False, False, False ) : interior,
        (  True, False, False, False ) : left,
        ( False,  True, False, False ) : right,
        ( False, False,  True, False ) : top,
        ( False, False, False,  True ) : bottom,
        (  True, False,  True, False ) : top_left,
        ( False,  True,  True, False ) : top_right,
        (  True, False, False,  True ) : bottom_left,
        ( False,  True, False,  True ) : bottom_right,
        }


    def location(self, x,y):
        method = self.location_map[(x==0, x==self.dim_x-1, y==0, y==self.dim_y-1)]
        return method(self)

l = LocationThing(10,10)
l.location(0,0)
l.location(0,1)
l.location(1,1)
l.location(9,9)
l.location(9,1)
l.location(1,9)
l.location(0,9)
l.location(9,0)

When you run the above it prints

top_left
left
interior
bottom_right
right
bottom
bottom_left
top_right

Answer 6

For a fast inner-loop function, you can just bite the bullet and do the ugly: nested if else statements with repeated terms, so that each comparison is only done once, and it runs about twice as fast as an example cleaner answer (by mobrule):

import timeit

def f0(x, y, x_dim, y_dim):
    if x!=0:
        if x!=x_dim: # in the x interior
            if y!=0:
                if y!=y_dim: # y interior
                    return "interior"
                else: # y==y_dim edge 'top'
                    return "interior-top"
            else:
                return "interior-bottom"
        else: # x = x_dim, "right"
            if y!=0:
                if y!=y_dim: # 
                    return "right-interior"
                else: # y==y_dim edge 'top'
                    return "right-top"
            else:
                return "right-bottom"
    else: # x=0 'left'
        if y!=0:
            if y!=y_dim: # y interior
                return "left-interior"
            else: # y==y_dim edge 'top'
                return "left-top"
        else:
            return "left-bottom"

r_list = ["interior","top","bottom","left","top-left",
            "bottom-left","right","top-right","bottom-right"]                 
def f1(x,y,dim_x,dim_y):
    index = 1*(y==0) + 2*(y==dim_y-1) + 3*(x==0) + 6*(x==dim_x-1)
    return r_list[index]

for x, y, x_dim, y_dim in [(4, 4, 5, 6), (0, 0, 5, 6)]:
    t = timeit.Timer("f0(x, y, x_dim, y_dim)", "from __main__ import f0, f1, x, y, x_dim, y_dim, r_list")
    print "f0", t.timeit(number=1000000)
    t = timeit.Timer("f1(x, y, x_dim, y_dim)", "from __main__ import f0, f1, x, y, x_dim, y_dim, r_list")
    print "f1", t.timeit(number=1000000)

Which gives:

f0 0.729887008667  # nested if-else for interior point (no "else"s)
f1 1.4765329361
f0 0.622623920441  # nested if-else for left-bottom (all "else"s)
f1 1.49259114265

So it's a bit better than twice as fast as mobrule's answer, which was the fastest looking code that I knew would work when I posted this. (Also, I moved mobrule's string list out of the function as that sped up the result by 50%.) Speed over beauty?

If instead you want a concise and easy to read solution, I suggest:

def f1(x, y, x_dim, y_dim):
    d_x = {0:"left", x_dim:"right"}
    d_y = {0:"bottom", y_dim:"top"}
    return d_x.get(x, "interior")+"-"+d_y.get(y, "interior")

which is as fast as the others by my timing.